Home »

Twenty-Four puzzle, some observations

Submitted by stannic on Sun, 07/24/2011 - 01:39.

Hello all. I am new on this great forum. My first post is about Twenty-Four puzzle, larger version of classic Fifteen. I walked around sliding tile puzzles for quite some time. At some point I decided that what I have is too much for me alone, but enough to write about it here.

Many small puzzles have been solved long ago. There is some information in OEIS: A151944 (about MxN puzzles), A087725 (about NxN puzzle). AFAIK largest solved STP is 4x4 puzzle (classic Fifteen). It was known that 80 single-tile moves required and sufficient, and recently Bruce Norskog wrote on this forum about 43 multi-tile moves.

Next NxN puzzle is 5x5 "Twenty Four". The number of states is 25!/2 = 7,755,605,021,665,492,992,000,000. It is too many to do full analysis in near future. I searched for lower and upper bounds. In 1996, Richard E. Korf and Larry A. Taylor in paper "Finding Optimal Solutions to the Twenty-Four puzzle" showed that 114 single-tile moves are needed. In 2000, Filip Karlemo and Patric Ostergard showed that 210 single-tile moves are sufficient. I was not able to find any better bounds on the web.

Also, it turned out that in most cases single-tile metric (STM) was used by researchers, and probably there is no known upper and lower bounds for 5x5 in multi-tile metric (MTM) yet.

As for lower bound in STM, there is puzzle state with Manhattan distance of 116 moves. Let goal state be the following:

 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

Then the following instance has manhattan heuristic of 116 moves:

24 23 22 21 20
19 18 17 16 15
14 13  0 11 10
 9  8  7 12  5
 4  3  2  1  6

Moreover, it seems like I can show that the following "turned 180-degree" state requires at least 140 STM. So lower bound in STM metric should be 140 moves.

24 23 22 21 20
19 18 17 16 15
14 13 12 11 10
 9  8  7  6  5
 4  3  2  1  0

To prove this, I used good heuristic developed by Ken'ichiro Takahashi (takaken). Maybe I'll outline idea of this heuristic in separate topic later. However, there is an explanation written by the author (unfortunately, it is in Japanese language) on Takahashi's web site. He developed new Walking Distance (WD) and implemented it in his "15 puzzle Optimal solver". I just used his ideas with 5x5 puzzle. WD heuristic gives for "turned 180-degree" configuration lower bound of 140 moves.

Also the same "turned 180-degree" puzzle configuration requires at most 156 STM. Note that we can turn the whole box with all tiles 180 degrees and get goal state. If we first turn box 90 degrees clockwise and then again 90 degrees clockwise, effect should be the same. But if we turn goal 90 degrees we get much simpler configuration that can be solved optimally in 78 STM. Then we can perform this move sequence twice to turn 180 degrees and so get 78+78=156 moves. So optimal solution for this particular instance is between 140 STM and 156 STM.

4x4 STM God's number is 80, and "turned 180-degree" instance is very close to hardest case (78 STM); so I believe God's number for 5x5 puzzle will be about 160 STM.

I wrote program that searches for suboptimal solutions for sliding tile puzzles. On Jaap's website, he describes multi-phase algorithm to solve large puzzles. My program uses his algorithm with some additional improvements. I cannot write about it in this topic for reasons of brevity. Shortly, this is four-stage suboptimal solver.

About 2,000 random instances have been solved in STM metric with time limit of 10 seconds per instance. Minimal length was 77 moves, maximal length was 152 moves, average length was 118.4 moves.

About 2,000 random instances have been solved in MTM metric with the same time limit of 10 seconds. Minimal length was 47 moves, maximal length was 85 moves, and average length was 69.4 moves.

About 1,000,000 of random 5x5 instances have been solved in 160 STM or less. (Search stops when solution in 160 moves or fewer found). All instances were solved; minimal length was 79 moves, average length was 138.1 moves, and average time per instance was about 5 milliseconds.

Finally, about half million random instances have been solved in 90 or fewer multi-tile moves. Minimal length was 51 moves, average length was 85.4 moves, and average time was about 7 milliseconds.

My solver is four-stage. It is possible to create three-stage solver. For example, first phase solves five tiles in first row, second phase solves first column, and third phase is 4x4 puzzle and can be solved with IDA*.

Many thanks to this forum for its existence.

Many thanks to Jaap for his patience. I received a lot of help from him, as well as on his website.

The Walking Distance heuristic was developed by Ken'ichiro Takahashi.

Thanks to Google Translate service. Neither English nor Japanese is not my native language.

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

some regularities in maximum WD values

Submitted by stannic on Tue, 01/10/2012 - 21:35.

I just noticed some interesting regularities in this table posted by Rokicki.

In Nx2 case, maximum walking distance value is 2N-1. In Nx3 case, maximum walking distance value is 4N+2. I do not know if this will be continued exactly.

In Nx4 case, regularity slightly breaks: maximum WD value is 8N+5 for 2≤N≤3 and 8N+3 for 4≤N≤9.

In Nx5 and other cases, regularity almost disappears.

w h  d   w h  d   w h  d
- - --   - - --   - - --
2 2  3   2 3 10   2 4 21
3 2  5   3 3 14   3 4 29
4 2  7   4 3 18   4 4 35
5 2  9   5 3 22   5 4 43
6 2 11   6 3 26   6 4 51
7 2 13   7 3 30   7 4 59
8 2 15   8 3 34   8 4 67
9 2 17   9 3 38   9 4 75
» login or register to post comments

2xN case. Nx2 has Hamiltonian path

Submitted by stannic on Wed, 01/11/2012 - 03:51.

In 2xN case, maximum WD value seems to be (N-1)×(2N-1).

 w h  d
 - - --
 2 2  3 = 1x3
 2 3 10 = 2x5
 2 4 21 = 3x7
 2 5 36 = 4x9
 2 6 55 = 5x11
 2 7 78 = 6x13

In Nx2 case, maximum WD value is indeed 2N-1. The antipode is the following configuration:

Nx2 WD puzzle
------------------------
BBBBBBBBBB => AAAAAAAAA.
AAAAAAAAA.    BBBBBBBBBB
------------------------

There is only one unique shortest solution to this problem, and this solution is Hamiltonian path through all configurations of the Nx2 walking distance puzzle. By the way, there are exactly 2N configurations.

Edit: more details are in this thread.

» login or register to post comments

4x5 Last Row Permutation

Submitted by stannic on Tue, 08/30/2011 - 14:11.

Consider the 4x5 sliding tile puzzle (width 4). In initial position, tiles 16,17,18,19 are in bottom row in one of 4! = 24 permutations; slot is in one of 4 locations in second row from the bottom. In solved position, tiles 16,17,18,19 are solved, and slot is in one of 4 locations in second row from the bottom. Example is given below.

  locations    initial position   solved position
  0  1  2  3      .  .  .  .         .  .  .  .
  4  5  6  7      .  .  .  .         .  .  .  .
  8  9 10 11      .  .  .  .         .  .  .  .
 12 13 14 15      0  .  .  .         0  .  .  .
 16 17 18 19     19 17 18 16        16 17 18 19

The following table gives length of the optimal solution in STM metric for each of 4! * 4^2 = 384 cases. In initial position, slot is in location start; in solved position, slot is in location stop. There are only two 28s* cases; one is given as example above, and another is its horizontal reflection.

 -------------------------------------------------------------
       start   12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15
        stop   12 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15
 -------------------------------------------------------------
 16 17 18 19    0  1  2  3  1  0  1  2  2  1  0  1  3  2  1  0
 16 17 19 18   16 15 14 15 15 14 13 14 14 13 14 13 15 14 13 14
 16 18 17 19   14 13 14 15 13 14 13 14 14 13 14 13 15 14 13 14
 16 18 19 17   16 15 16 17 15 14 15 16 14 13 14 15 13 12 13 14
 16 19 17 18   16 15 14 13 15 14 13 12 16 15 14 13 17 16 15 14
 16 19 18 17   20 19 18 19 19 18 17 18 18 17 18 17 19 18 17 18
 17 16 18 19   14 13 14 15 13 14 13 14 14 13 14 15 15 14 15 16
 17 16 19 18   22 21 20 19 21 22 21 20 20 21 22 21 19 20 21 22
 17 18 16 19   14 15 16 17 13 14 15 16 12 13 14 15 13 14 15 16
 17 18 19 16   22 23 24 25 21 22 23 24 20 21 22 23 19 20 21 22
 17 19 16 18   22 23 22 23 21 22 23 22 22 23 22 21 23 22 23 22
 17 19 18 16   22 23 22 23 21 22 21 22 20 21 20 21 21 22 21 22
 18 16 17 19   14 13 12 13 15 14 13 14 16 15 14 15 17 16 15 16
 18 16 19 17   22 21 22 23 23 22 23 22 22 23 22 23 23 22 21 22
 18 17 16 19   18 17 18 19 17 18 17 18 18 17 18 19 19 18 19 20
 18 17 19 16   22 21 22 23 21 20 21 22 22 21 22 23 21 20 21 22
 18 19 16 17   24 23 24 25 23 24 23 24 24 23 24 23 25 24 23 24
 18 19 17 16   26 25 26 27 25 24 25 26 24 23 24 25 25 24 25 26
 19 16 17 18   22 21 20 19 23 22 21 20 24 23 22 21 25 24 23 22
 19 16 18 17   22 21 20 21 23 22 21 22 22 21 20 21 23 22 21 22
 19 17 16 18   22 21 22 21 21 20 21 20 22 21 22 21 23 22 23 22
 19 17 18 16   28 27 26 27 27 26 25 26 26 25 26 27 27 26 27 28
 19 18 16 17   26 25 24 25 25 24 23 24 26 25 24 25 27 26 25 26
 19 18 17 16   26 25 26 27 25 24 25 26 26 25 24 25 27 26 25 26
 -------------------------------------------------------------

The following table is for MTM metric.

 -------------------------------------------------------------
       start   12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15
        stop   12 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15
 -------------------------------------------------------------
 16 17 18 19    0  1  1  1  1  0  1  1  1  1  0  1  1  1  1  0
 16 17 19 18   11 11 10 10 11 11 10 10 10 10 10  9 10 10  9 10
 16 18 17 19   11 10 10 11 10 10  9 10 10  9 10 10 11 10 10 11
 16 18 19 17   12 11 12 12 12 11 12 12 13 12 13 12 12 11 12 11
 16 19 17 18   12 12 13 12 11 11 12 11 12 12 13 12 12 12 12 11
 16 19 18 17   15 14 14 14 14 14 13 14 14 13 14 13 14 14 13 14
 17 16 18 19   10  9 10 10  9 10 10 10 10 10 11 11 10 10 11 11
 17 16 19 18   14 14 13 14 14 14 13 13 13 13 14 14 14 13 14 14
 17 18 16 19   11 12 12 12 12 13 12 12 11 12 11 11 12 13 12 12
 17 18 19 16   15 16 16 16 15 16 16 16 15 16 16 16 15 15 15 15
 17 19 16 18   14 14 14 14 13 13 14 14 14 14 13 13 14 14 14 14
 17 19 18 16   16 17 16 17 15 16 16 16 16 16 15 16 16 16 15 16
 18 16 17 19   11 12 11 12 12 13 12 13 12 12 11 12 12 12 11 12
 18 16 19 17   14 13 14 14 14 13 14 14 14 14 13 14 14 14 13 14
 18 17 16 19   14 13 14 14 13 14 13 14 14 13 14 14 14 14 14 15
 18 17 19 16   16 16 16 17 15 15 16 16 16 16 16 17 16 16 15 16
 18 19 16 17   16 15 16 16 15 16 16 16 16 16 16 15 16 16 15 16
 18 19 17 16   18 18 18 19 17 17 18 18 17 17 17 18 18 17 17 18
 19 16 17 18   15 15 15 15 16 16 16 15 16 16 16 15 16 16 16 15
 19 16 18 17   16 15 16 16 17 16 16 16 16 16 15 15 17 16 16 16
 19 17 16 18   16 15 16 16 16 15 16 16 16 16 16 15 17 16 17 16
 19 17 18 16   19 19 19 20 19 19 19 19 19 19 19 19 20 19 19 19
 19 18 16 17   18 17 17 18 18 17 17 17 18 18 17 17 19 18 18 18
 19 18 17 16   20 19 19 20 19 19 20 19 19 20 19 19 20 19 19 20
 -------------------------------------------------------------
» login or register to post comments

Anyone interested in the new

Submitted by stannic on Wed, 08/24/2011 - 19:10.

Anyone interested in the new metrics to the sliding tile puzzles?

Two possible metrics are STM (single-tile moves) and MTM (multi-tile moves). One can consider instead maximal allowed amount of move; for metric STM, maximal amount is 1 because we can move only one tile per move; for MTM, maximal amount is positive infinity.

The following table gives the God's number for some small puzzles with different maximal amount of move. In all cases, blank square started in corner.

 ----------------------------
        max.amount of move
 size   1   2   3   4   5   6
 ----------------------------
 2x2    6   -   -   -   -   -
 3x2   21  20   -   -   -   -
 3x3   31  24   -   -   -   -
 4x2   36  28  25   -   -   -
 4x3   53  38  33   -   -   -
 4x4   80   ?  43   -   -   -
 5x2   55  38  36  36   -   -
 6x2   80  55  46  42  41   -
 ----------------------------
» login or register to post comments

"Coset" solver for 15-puzzle

Submitted by rokicki on Tue, 08/23/2011 - 17:47.
I'm experimenting with a "Coset" solver for the 15-puzzle. (From there I'll probably move on to 2x9 or 3x6.) So far it seems to work very well; in about ten hours I can find solutions for the vast majority of positions in 80 or fewer moves. The problem now is dealing with the leftover positions.

For that I need a very efficient batch optimal or suboptimal solver. I'll probably write my own.

It's not as pretty as the one for Rubik's Cube, because this puzzle is not a group, and thus the concept of a Schreier coset graph doesn't really apply. And for instance the "cosets" with a blank are different in a fundamental way from the "cosets" without a blank.

My goal is to figure out the minimum CPU time that is needed to prove that the 15-puzzle has no distance-81 positions. I'm fairly certain I can do it in well under 24 CPU hours.

Note that I am *not* finding the full state space distance distribution, and I am *not* necessarily finding all antipodes. Just showing there are no distance-81 positions.
» login or register to post comments

The set graph

Submitted by stannic on Tue, 08/23/2011 - 18:48.

I am not sure why concept of the Schreier coset graph does not apply (at least, in practical sense). Puzzle isn't a group, but we can still consider "cosets". In set graph, these "cosets" are vertices, and edges are moves; so we should be able to determine possible moves in any given coset. For Fifteen puzzle, in phase 1 we can solve fringe tiles. There is 7 fringe tiles, and one "blank tile" (slot); one can include locations of all these 8 tiles in "relabeled puzzle" position. The "coset space" is 16!/8!=518,918,400. It is larger because of necessity of "blank tile" but still fits in memory.

Let G be set of all positions, H be subset of G of all positions with solved fringe tiles and blank tile. The bitmap on H should contain entry for each position with solved fringe tiles and blank; that is, 8!/2 = 20,160 entries. There is really a problem with prepasses; we cannot simply do moves in H because slot is fixed in H. This is similar to the difference between corner-group coset solver and Kociemba-group coset solver with Rubik's Cube.

» login or register to post comments

Fringe

Submitted by rokicki on Tue, 08/23/2011 - 19:02.
I'm using just four tiles (the top four tiles) in my fringe, but yes the idea is the same. I don't use the blank as part of my "coset" state, which gives me a prepass (and of course all the speed comes from the prepass).

We can consider "cosets", but the adjacency of "cosets" is problematic, since the "coset" definition does not include the blank location. Without "coset" adjacency, optimizations based on "adjacent" cosets is a problem.

Take for example the "1234" "coset"; this has a maximum depth of 53. If we had adjacency, then any "coset" within 27 moves of this could be immediately ignored.

So how far is the "1238" "coset" from the "1234" coset? (With the Rubik's cube of course, adjacent cosets were fully adjacent; every coset had neighbors, and the neighbors were exactly one move away from each other.)

Now, I do use the fact that the "-238" "coset" is at most one move from the union of the "x238" coset (for x=1..15); I don't actually solve "cosets" like "-238" at this point (but I do solve them based on leftover positions from the "x238" cosets that are at distance 80 and have the blank positioned correctly.)
» login or register to post comments

4x4 puzzle antipodes in STM

Submitted by stannic on Fri, 08/19/2011 - 15:40.

Here is all 80s* configurations of 4x4 Fifteen Puzzle for anyone interested. 13 of 17 positions are from "Harnessing Computational Resources for Efficient Exhaustive Search" (R. Gasser, 1995); remaining 4 positions are from "The Parallel Search Bench ZRAM and its Applications" (A. Brungger, A. Marzetta, K. Fukuda, J. Nievergelt). I've checked these positions with takaken solver, and it confirmed all to be 80s*; times given in the right column. There is no other antipodes; "Large-Scale Parallel Breadth-First Search" (R. Korf, P. Schultze, 2005) shows the distance distribution with only 17 80s* positions.

      0-based goal state (0 1 2 ... 13 14 15)    0-terminated goal (1 2 3 ... 14 15 0)    takaken solver

 1    (15 10 8 12 11 14 9 13 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 3 7 2 5 4 8 6 1)  1461 sec
 2    (15 10 8 12 11 14 9 13 7 2 5 1 3 6 4 0)    (0 12 10 13 15 11 14 9 3 7 2 5 4 8 6 1)   715 sec
 3    (15 11 8 12 14 10 9 13 2 6 1 4 3 7 5 0)    (0 11 9 13 12 15 10 14 3 7 6 2 4 8 5 1)  2296 sec
 4    (15 11 8 12 14 10 9 13 2 6 4 5 3 7 1 0)    (0 15 9 13 11 12 10 14 3 7 6 2 4 8 5 1)  2349 sec
 5    (15 11 8 12 14 10 9 13 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 3 7 6 2 4 8 5 1)  2037 sec
 6    (15 11 8 12 14 10 9 13 6 7 5 1 3 2 4 0)    (0 12 14 13 15 11 9 10 3 7 6 2 4 8 5 1)  1627 sec
 7    (15 11 8 12 14 10 9 13 7 2 5 1 3 6 4 0)    (0 12 10 13 15 11 14 9 3 7 6 2 4 8 5 1)  1226 sec
 8    (15 11 8 12 14 10 9 13 7 6 2 1 3 5 4 0)    (0 12 11 13 15 14 10 9 3 7 6 2 4 8 5 1)  2975 sec
 9    (15 11 8 12 14 10 13 9 2 7 5 1 3 6 4 0)    (0 12 10 13 15 11 9 14 7 3 6 2 4 8 5 1)  2239 sec
10    (15 11 9 12 14 10 8 13 6 2 5 1 3 7 4 0)    (0 12 9 13 15 11 14 10 3 8 6 2 4 7 5 1)  2490 sec
11    (15 11 9 12 14 10 13 8 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 8 3 6 2 4 7 5 1)  1800 sec
12    (15 11 9 12 14 10 13 8 6 7 5 1 3 2 4 0)    (0 12 14 13 15 11 9 10 8 3 6 2 4 7 5 1)  1255 sec
13    (15 11 13 12 14 10 8 9 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 7 8 6 2 4 3 5 1)  1262 sec
14    (15 11 13 12 14 10 8 9 7 2 5 1 3 6 4 0)    (0 12 10 13 15 11 14 9 7 8 6 2 4 3 5 1)   661 sec
15    (15 11 13 12 14 10 9 5 2 6 8 1 3 7 4 0)    (0 12 9 13 15 8 10 14 11 7 6 2 4 3 5 1)  2998 sec
16    (15 14 8 12 10 11 9 13 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 3 7 5 6 4 8 2 1)  1485 sec
17    (15 14 13 12 10 11 8 9 2 6 5 1 3 7 4 0)    (0 12 9 13 15 11 10 14 7 8 5 6 4 3 2 1)   778 sec
» login or register to post comments

It took me some time to write

Submitted by kociemba on Tue, 10/04/2011 - 14:16.
It took me some time to write an optimal fifteen puzzle solver, but now it seems to work. I implemented takakens heuristic and the static 7-8 additive pattern database as described in the papers of Korf. I ran the 17 antipode positions above and they all took 80 moves - as it should be.
The times to solve the 17 positions is about 24 s altogether.

The program needs about 570 MB of memory to run, if the pruning tables are already created.
Random positions are solved at a rate of about 3.8 ms on average.
» login or register to post comments

Though the WD heuristic has w

Submitted by kociemba on Sun, 10/16/2011 - 06:11.
Though the WD heuristic has with 70 a bigger maximal pruning value than the 7-8-pattern data base, the program runs faster if I only use the 7-8-database (together with the diagonally reflected 7-8 database.
The 17 antipodes are solved in 21 s and a random position takes 3.1 ms on average.
» login or register to post comments

It's interesting

Submitted by stannic on Mon, 10/17/2011 - 02:55.

Can you check how many time needed your program to solve the following positions with / without / with only WD? Positions are given for 0-terminated goal.

  1  5  9 13      0 12  8  4
  2  6 10 14     15 11  7  3
  3  7 11 15     14 10  6  2
  4  8 12  0     13  9  5  1

First of two positions was hard for takaken's solver. On his website, he says that instance was solved in 77565sec (about 21 hr 33 min). With additional improvements, time was 12416 sec (3 hr 27 min).

Of course PDBs should be better because they use very large tables.

» login or register to post comments

Optimal solver program

Submitted by kociemba on Sat, 10/22/2011 - 05:51.
I have written a graphical interface for my solver. It supports drag and drop of tiles, different heuristics, generating one solution or all optimal solutions.
The most powerful heuristics, the 78 pattern database will presumably run only on a 64 bit windows with more than 4 GB of RAM, because during table creation 2.5 GB of memory are required which may be too much in a 32 bit windows environment.
You can download the program at

http://kociemba.org/fifteen/fifteenpuzzle.zip
» login or register to post comments

Both positions need 72 moves.

Submitted by kociemba on Mon, 10/17/2011 - 05:53.
Both positions need 72 moves.
First position takes 12.4 s with only 7-8 PDB and 13.9 s with 7-8 PDB + WD.
Second position needs 28.8 s with only 7-8 PDB and 32.3 s with 7-8 PDB + WD.

WD only was 19119 s for first position, second was 74192 s.
» login or register to post comments

24 puzzle new lower bound: 152

Submitted by rokicki on Thu, 08/18/2011 - 11:25.
My 5x5 optimal solver, after almost ten days, has finally finished a ply-150 search on the 5x5 turned 180 degrees without a solution. Thus, the new lower bound on the 24-puzzle is 152.
» login or register to post comments

Half-depth search

Submitted by stannic on Wed, 08/31/2011 - 13:41.

Just observations. We know solution in 156s for turned 180 puzzle state. This solution goes through intermediate puzzle state.

Suppose we run search from 5x5 turned 180 degrees. At depth 78s, we will find turned 90 degrees (and many other puzzle states).

Suppose we run search from 5x5 goal state. Then at depth 78s we'll find the same puzzle states but all turned 180.

That is: if we run search from goal state and at depth d found puzzle state X, then we will find turned 180 degrees X at depth d if we run search from turned 180 degrees.

Thus, if we run search from 5x5 turned 180 degrees and at depth, say, 77s find two states each of which can be obtained from another by rotation 180 degrees, then there is solution in 154s for 5x5 turned 180 degrees.

Can this help or it is the same problem?

- Bulat
<my nickname> at_ymail_point_com

» login or register to post comments

Asymptotical bounds

Submitted by stannic on Thu, 08/18/2011 - 21:14.

I noticed one interesting thing. For (n2-1)-puzzle, diameter is Theta(n3). I tried k*43=80 because 4x4 can be solved in 80s and get k=1.25. Then k*53=156.25. On the other side, k*33=33.75. I do not know if this was known already.

» login or register to post comments

Yep

Submitted by rokicki on Fri, 08/19/2011 - 01:25.
Just a minor nit. This puzzle is not a group so we should probably not say "diameter".

The diameter of a graph is the distance between the two most distant points. But because the puzzle is not a group, the maximum distance for each starting slot position may be different.

We could argue that maximum distance probably occurs when the slot is at a corner, but I'm not sure it would be easy to prove.

Richard Korf uses "radius", but I'm not sure that's correct either. The eccentricity of a vertex is the maximum distance to any other vertex; the radius is the minimum eccentricity over all nodes (and the diameter is the maximum).
» login or register to post comments

Yes, of course; in general, w

Submitted by stannic on Fri, 08/19/2011 - 16:03.

Yes, of course; in general, we can list all possible pairs of squares in which blank tile starts and stops. For any given pair, we can find transformation that takes the maximum number of moves.

I think it is not hard to disprove that antipodes should have slot at a corner; single unique 3x3 puzzle antipode position has slot at the side. However, all STM antipodes have blank square in the corner.

In MTM, there is antipodes with slot in one of inner squares. Multi-tile metric seems to be more unpredictable. It is much closer to the Rubik's cube.

Edit: Instead of "...all STM antipodes...", should be "...all 4x4 puzzle STM antipodes...".

» login or register to post comments

Results from Richard Korf (2008)

Submitted by rokicki on Mon, 08/15/2011 - 18:29.
In "Linear-Time Disk-Based Implicit Graph Search", published in the Journal of the ACM, Richard Korf provides the following results: 
Size Tiles Radius     Total States      Max Width Depth Ratio
2x2     4     6                 12               2  2  6.000
2x3     5    21                360              44 14  8.182
2x4     7    37             20,160           1,999 24 10.085
3x3     8    31            181,440          24,047 24  7.545
2x5     9    55          1,814,400         133,107 36 13.361
3x4    11    53        239,500,800      21,841,159 36 10.966
2x6    11    80        239,500,800      13,002,649 49 18.419
------------------------------------------------------------
2x7    13   108     43,589,145,600   1,862,320,864 66 23.406
3x5    14    84    653,837,184,000  45,473,143,333 42 14.486
4x4    15    80 10,461,394,944,000 784,195,801,886 53 13.340
2x8    15   140 10,461,394,944,000 367,084,684,402 85 28.499
The ones below the line are new.

He does not provide the actual distribution in the paper, but I would be surprised if this data is not available on request.

I am in the process of confirming these numbers.

Next interesting sizes are probably 3x6 and 2x9; these have a significant number of states.

» login or register to post comments

Verified first 9 rows

Submitted by rokicki on Wed, 08/17/2011 - 13:18.
I've checked the first nine rows of that table, and found three errors.

The Radius of the 2x4 should be 36.

The Depth of the 3x5 should be 52.

The Ratio of the 3x5 should be 14.379.

Here are the distance distributions for the first nine rows: 

  - 2x2 2x3  2x4   3x3    2x5      2x6      3x4        2x7         3x5
  0   1   1    1     1      1        1        1          1           1
  1   2   2    2     2      2        2        2          2           2
  2   2   3    3     4      3        3        4          3           4
  3   2   5    6     8      6        6        9          6           9
  4   2   6   10    16     11       11       20         11          21
  5   2   7   14    20     19       20       37         20          42
  6   1  10   19    39     30       36       63         37          89
  7   -  12   28    62     44       60      122         67         164
  8   -  12   42   116     68       95      232        117         349
  9   -  16   61   152    112      155      431        198         644
 10   -  23   85   286    176      258      781        329        1349
 11   -  25  119   396    271      426     1392        557        2473
 12   -  28  161   748    411      688     2494        942        5109
 13   -  39  215  1024    602     1106     4442       1575        9110
 14   -  44  293  1893    851     1723     7854       2597       18489
 15   -  40  396  2512   1232     2615    13899       4241       32321
 16   -  29  506  4485   1783     3901    24215       6724       64962
 17   -  21  632  5638   2530     5885    41802      10535      112445
 18   -  18  788  9529   3567     8851    71167      16396      223153
 19   -  12  985 10878   4996    13205   119888      25515      378761
 20   -   6 1194 16993   6838    19508   198363      39362      740095
 21   -   1 1414 17110   9279    28593   323206      60532     1231589
 22   -   - 1664 23952  12463    41179   515778      92089     2364342
 23   -   - 1884 20224  16597    58899   811000     138969     3847629
 24   -   - 1999 24047  21848    83582  1248011     207274     7246578
 25   -   - 1958 15578  28227   118109  1885279     307725    11506172
 26   -   - 1770 14560  35682   165136  2782396     453000    21233764
 27   -   - 1463  6274  44464   228596  4009722     664240    32854049
 28   -   - 1076  3910  54597   312542  5621354     964874    59293970
 29   -   -  667   760  65966   423797  7647872    1392975    89146163
 30   -   -  361   221  78433   568233 10065800    1992353   157015152
 31   -   -  190     2  91725   755727 12760413    2832063   228894783
 32   -   -   88     - 104896   994641 15570786    3988528   392648931
 33   -   -   39     - 116966  1296097 18171606    5586275   553489877
 34   -   -   19     - 126335  1667002 20299876    7756511   922382155
 35   -   -    7     - 131998  2119476 21587248   10698721  1253605100
 36   -   -    1     - 133107  2660415 21841159   14621717  2023948293
 37   -   -    -     - 128720  3300586 20906905   19840724  2642914623
 38   -   -    -     - 119332  4038877 18899357   26676629  4120279612
 39   -   -    -     - 106335  4877286 16058335   35605683  5148314561
 40   -   -    -     -  91545  5804505 12772603   47083756  7724532034
 41   -   -    -     -  75742  6810858  9515217   61775128  9199799154
 42   -   -    -     -  60119  7864146  6583181   80280617 13246457713
 43   -   -    -     -  45840  8929585  4242753  103437923 14989319785
 44   -   -    -     -  33422  9958080  2503873  131954019 20670772402
 45   -   -    -     -  23223 10902749  1350268  166799476 22175539691
 46   -   -    -     -  15140 11716813   643245  208715971 29256857608
 47   -   -    -     -   9094 12356080   270303  258659945 29720831702
 48   -   -    -     -   5073 12791679    92311  317168280 37494316617
 49   -   -    -     -   2605 13002649    27116  384949885 36040261784
 50   -   -    -     -   1224 12981651     5390  462104381 43456588792
 51   -   -    -     -    528 12723430     1115  548743615 39489966889
 52   -   -    -     -    225 12245198       86  644208445 45473143333
 53   -   -    -     -     75 11572814       18  747728714 39013132880
 54   -   -    -     -     20 10738102        -  857838218 42843777396
 55   -   -    -     -      2  9772472        -  972826409 34634595224
 56   -   -    -     -      -  8720063        - 1090524780 36201542605
 57   -   -    -     -      -  7623133        - 1208492639 27498739245
 58   -   -    -     -      -  6526376        - 1324294771 27279157652
 59   -   -    -     -      -  5459196        - 1435166611 19394857005
 60   -   -    -     -      -  4457799        - 1538445477 18188522435
 61   -   -    -     -      -  3546306        - 1631318167 12035839867
 62   -   -    -     -      -  2749552        - 1711407623 10609974233
 63   -   -    -     -      -  2068975        - 1776313778  6480164672
 64   -   -    -     -      -  1510134        - 1824122769  5324826466
 65   -   -    -     -      -  1064591        - 1853119548  2963664642
 66   -   -    -     -      -   720002        - 1862320864  2241211464
 67   -   -    -     -      -   464913        - 1851238359  1114401509
 68   -   -    -     -      -   284204        - 1820042135   760520424
 69   -   -    -     -      -   165094        - 1769350453   327445752
 70   -   -    -     -      -    89649        - 1700564453   195462601
 71   -   -    -     -      -    45758        - 1615557458    69272233
 72   -   -    -     -      -    21471        - 1516675570    34371729
 73   -   -    -     -      -     9583        - 1406502343     9207635
 74   -   -    -     -      -     3829        - 1288154452     3495571
 75   -   -    -     -      -     1427        - 1164716069      621091
 76   -   -    -     -      -      430        - 1039257451      163627
 77   -   -    -     -      -      129        -  914718314       17629
 78   -   -    -     -      -       33        -  793783415        3599
 79   -   -    -     -      -       12        -  678934877         280
 80   -   -    -     -      -        2        -  571912137          75
 81   -   -    -     -      -        -        -  474232181          12
 82   -   -    -     -      -        -        -  386713150           5
 83   -   -    -     -      -        -        -  309907682           2
 84   -   -    -     -      -        -        -  243779436           1
 85   -   -    -     -      -        -        -  188010782           -
 86   -   -    -     -      -        -        -  142009132           -
 87   -   -    -     -      -        -        -  104838064           -
 88   -   -    -     -      -        -        -   75576381           -
 89   -   -    -     -      -        -        -   52999438           -
 90   -   -    -     -      -        -        -   36159280           -
 91   -   -    -     -      -        -        -   23830790           -
 92   -   -    -     -      -        -        -   15194456           -
 93   -   -    -     -      -        -        -    9260117           -
 94   -   -    -     -      -        -        -    5426429           -
 95   -   -    -     -      -        -        -    3003444           -
 96   -   -    -     -      -        -        -    1590744           -
 97   -   -    -     -      -        -        -     784126           -
 98   -   -    -     -      -        -        -     369889           -
 99   -   -    -     -      -        -        -     159376           -
100   -   -    -     -      -        -        -      65645           -
101   -   -    -     -      -        -        -      23761           -
102   -   -    -     -      -        -        -       8357           -
103   -   -    -     -      -        -        -       2499           -
104   -   -    -     -      -        -        -        779           -
105   -   -    -     -      -        -        -        198           -
106   -   -    -     -      -        -        -         43           -
107   -   -    -     -      -        -        -          8           -
108   -   -    -     -      -        -        -          1           -
» login or register to post comments

Antipodes

Submitted by rokicki on Wed, 08/17/2011 - 13:20.
Here are the antipodes for these sizes. (I had to correct an entry in the OEIS based on these results.) I have verified the depth of the first seven antipodes with a completely separate optimal solver. (The remainder are fairly difficult to verify.) 
2x2:
 0 3
 2 1
2x3:
 4 5 0
 1 2 3
2x4:
 0 7 2 1
 4 3 6 5
3x3:
 6 4 7
 8 5 0
 3 2 1

 8 6 7
 2 5 4
 3 0 1
2x5:
 0 9 3 7 1
 5 4 8 2 6

 0 5 3 2 1
 9 4 8 7 6
2x6:
  0 11  4  3  2  1
  6  5 10  9  8  7

  0  6  4  3  8  1
 11  5 10  9  2  7
3x4:
  8  7  5  9
  4  3 10  2
  0 11  6  1

  8  3  6  9
  4  7  2  5
  0 11 10  1

  8  3  2  1
  4  7  6  5
  0 11 10  9

  8  3  2  9
  4  7  6 10
  0 11  5  1

  4  3  6  1
  8  7  2  5
  0 11 10  9

  4  3  2  5
  8  7  6  1
  0 11 10  9

  4  3  2  1
  8  7  6  9
  0 11 10  5

  4  3  2  1
  8 11  6  5
  0  7 10  9

  4  3  2  1
 11  7  6  5
  0  8 10  9

 11  8  2  1
  3  7 10  5
  0  4  6  9

  0  3  2  1
  8  7  6  5
  4 11 10  9

  0  8  6  9
 11  7 10  1
  4  3  2  5

  0  8  6  9
 11  7  2  5
  4  3 10  1

  0  8  2  9
 11  7 10  5
  4  3  6  1

  0  8  6  1
 11  3  2  5
  4  7 10  9

  0  8  2  1
 11  3 10  5
  4  7  6  9

  0  8  2  9
 11  3  6  5
  4  7 10  1

  0 11  2  1
  3  7  6  5
  4  8 10  9
2x7:
  7  6 12  4  3  9  1
  0 13  5 11 10  2  8
3x5:
  7  6 13 12  5
  2  1  8  0 14
 11  4  3 10  9
» login or register to post comments

0-terminated vs 0-based?

Submitted by stannic on Wed, 08/17/2011 - 15:20.

All 18 3x4 positions are antipodes if your goal is 0-terminated (1 2 3 4 5 6/7 8 9 10 11 0).

Also, both 2x6 positions are antipodes (at distance 80s from 0-terminated goal).

First seven antipodes also antipodes only with 0-terminated goal position.

3x5 position can be solved in 40s* if your goal is 0-terminated. If your goal is 0-based then the same 3x5 position can be solved in 50s*. So it is not antipode?

I tried 2x7 position with SUB-optimal solver, and it finds 110s. It seems to me it is antipode.

» login or register to post comments

2x6 and 80s

Submitted by rokicki on Wed, 08/17/2011 - 15:48.
How did you compute the 80s solutions so fast? My general walking-distance solver is still spinning at a distance of 76. Are you using more pruning tables than just walking distance?

Also, the 3x5 solution will probably not finish with my solver.

Thanks for checking and finding the error!

-tom
» login or register to post comments

80s solutions

Submitted by stannic on Wed, 08/17/2011 - 16:07.

Heh, I calculated God's database, there is only 12!/2 = 239,500,800 reachable positions in 2x6.

With 3x5, I used suboptimal solver to get 84s. I think this horizontally reflected position to be antipode, and you confirm it!

I am very interested in how you calculated distribution for 2x7 and 3x5. 2x7 puzzle has 14!/2 = 43,589,145,600 positions; even if you have sufficient amount of RAM (about 10 GB?), how you calculated 3x5 with 15!/2=653,837,184,000 positions in about two or three days?

» login or register to post comments

Read Korf's paper

Submitted by rokicki on Wed, 08/17/2011 - 16:17.
Korf's 2008 paper referenced above lists all the techniques I used.

I did not finish implementing all of his techniques yet, but I did implement delayed duplicate detection, hash-based duplicate detection, and "used bits". I also did not use as efficient a representation as his, I did not eliminate sterile nodes, and I wrote out the duplicates to disk rather than eliminating the duplicates before writing to disk. I also did not use multithreading.

So I have some ways to go to catch up with his technology.

It's a good paper, well worth the read. It should be in your University library. Or you can purchase it online. Or, you can probably send email directly to Professor Korf and ask him for a copy (but of course I can't speak for him on his willingness or even legal ability to send out personal copies).

If absolutely necessary as a personal favor I might be able to make a xerox and physically mail it to you.
» login or register to post comments

Oops

Submitted by rokicki on Wed, 08/17/2011 - 15:45.
"0" represents the slot; all goals are "1 2 3...". You're right, the 3x5 antipode is wrong. That's because I computed it in "5x3" orientation, and then displayed it in "5x3" orientation. The actual antipode is interesting: 
  5  4  3  2  1
 10  9  8  7  6
  0 14 13 12 11
Sorry for the error! I'll edit the posting. Oops, can't once it has a reply! So the error will stand.
» login or register to post comments

Obvious error

Submitted by rokicki on Wed, 08/17/2011 - 16:37.
I should have seen that antipode was wrong by inspection. That antipode had the slot in the middle, so it had four neighbors, yet there were only two positions in the penultimate entry of the distance distribution.

It's still amazing to me how long-tailed these distance distributions are.
» login or register to post comments

Typos

Submitted by rokicki on Mon, 08/15/2011 - 20:17.
This table has typos in it (in my copy of the Journal article). I am working to determine which numbers are wrong and where the errors are from.

The "2x4" "Radius" should be "36", not "37".

The "3x5" "Depth" should not be "42" (I'm guessing 52 but have not verified this yet.)

» login or register to post comments

2xN puzzles

Submitted by stannic on Mon, 08/15/2011 - 19:52.

Anton Kulchitsky wrote here:

A very exact low estimate for the 2xN puzzle is (2N+1)*N = 1+2+3+...+2N
(it is exact for 2x3, 2x4, 2x5 and differ by 2 with 2x6).

For 2x7 puzzle, (2*7+1)*7 = 105, and Richard Korf gives 108. For 2x8 puzzle, (2*8+1)*8 = 136, and I see in table you posted 140.

If his formula indeed is correct then lower bound for 2x9 is 171s.

» login or register to post comments

Next interesting sizes

Submitted by stannic on Mon, 08/15/2011 - 19:28.

But I really never think about solving all puzzles. When I started this thread I want to write about WD heuristic and applying it to the 5x5 puzzle but this thread tends to become new hard puzzle eventually.

Seriously, I have some questions, and I think it is not so bad to ask here.

First, I have never studied the theory of groups in the mathematical sense. My knowledge in this area is quite shallow and are based largely on common sense and very puzzle-related. Most of the information I learned from the Jaap's Puzzle Page, Kociemba's website and this forum.

In Kociemba's algorithm, we first get into the group H = <U,D,L2,R2,F2,B2>. This group has 8!*8!*4!/2 = 19,508,428,800 elements. In second phase we cannot leave this group. So, we cannot change some properties of the cube (this is orientations of pieces and set of edge cubies that are in middle slice). We can get any position from group H by applying moves from set S = {U,D,L2,R2,F2,B2} to the solved state (identity). By applying to solved state moves from set S followed by some fixed move sequence, we can get positions from some coset of H. Is it correct?

Assuming that this is correct, one question is how to speak about it with Fifteen puzzle instead of Rubik's cube. Fifteen puzzle is not a group (move may not be possible). But general idea is the same?

For example, set F (first letter of "Fifteen") consists of all 9!/2 = 181,440 positions in which 7 "fringe tiles" are solved. In other words, this is 3x3 sub-puzzle.

Given any random 4x4 configuration, we can solve it in two stages just as in Kociemba's algorithm. We first get into set F by doing any possible moves; that is, we solve fringe tiles. We always can solve remaining tiles without leaving set F (this is similar to the fact that we can obtain all cube positions from group H by doing only U,D,L2,R2,F2,B2).

Suppose that squares of the Fifteen puzzle are numbered from 0 to 15. Let M(i,j) be set of all maneuvers that starts in square i (in puzzle configuration that has blank square i) and ends in square j (in puzzle configuration that has blank tile in square j). For example, if we apply some maneuver from set M(0,15) to the goal configuration then resulting configuration will have blank square 15. Also, we cannot apply any maneuver from set M(i,j) to the puzzle configuration that has blank square k if i != k.

By applying to the solved Fifteen state many different maneuvers from set M(0,i) without leaving set F, and then applying some fixed maneuver from set M(i,j) that leaves set F, we can obtain "coset of F", some set of configurations that differs only by permutation of non-fringe tiles. There are 9!/2 = 181,440 elements in any such "coset", and there are 57,657,600 = 16!/9! such "cosets". I want to know if there is some mathematical terms to say about these "cosets".

Next, suppose we want to get upper bound of the Fifteen Puzzle. Is it possible to solve the whole "cosets of F" as was done with Rubik's cube in 20f* proof (if I correctly understand this)? Given some "coset", we have only one fixed arrangement of fringe tiles in all configurations from this "coset". We can search for all optimal and sub-optimal solutions of fringe tiles in this fixed arrangement; each time we get into set F, we can set one bit in bitvector. There is 9!/2 = 181,440 configurations in set F; so bitvector has 181,440 bits.

» login or register to post comments

Groups and Two-Phase technique

Submitted by rokicki on Mon, 08/15/2011 - 20:23.
Sorry if I've helped take this thread so far afield of your original topic; if you prefer I'd be happy to open a new topic for this sort of general discussion of the mxn tile puzzles, walking distance, and such.

I believe the general idea of the two-phase algorithm can indeed be applied to the 15 puzzle, as you write, both in terms of solving individual positions and in terms of solving cosets. The difficulty however is that the 15 puzzle has such a long tail; this might make things a bit more difficult. However, just as in the coset solver we used for Rubik's Cube, you can use "prepass" moves in bulk to calculate suboptimal solutions for large numbers of positions at once, and with this, allow yourself to quickly determine the radius of the puzzle.

For the 15-puzzle, some of the "cosets" will be *much* easier than others, and can be dispensed with very quickly. Others will require more search.
» login or register to post comments

Sorry if I've helped take thi

Submitted by stannic on Mon, 08/15/2011 - 21:02.

Sorry if I've helped take this thread so far afield of your original topic.

Oh no, I thank you for your help in making this thread a kind of general discussion!

As for coset approach, I am reading this paper. Definitely I should study it to understand some details. For example, I still cannot get the purpose of "prepass".

» login or register to post comments

Search for upper bounds for 5x5 in MTM

Submitted by stannic on Sat, 08/13/2011 - 09:29.

I plan to search for upper bound of 5x5 tile puzzle in multi-tile metric (MTM). In single-tile metric (STM), I know upper bound of 210s. There may be some recent better bounds, however.

It is possible to get upper bound of 112m using result of 43 moves obtained by Bruce Norskog. More precisely, it is possible to reduce 5x5 to 5x4 in at most 38m, and it is possible to reduce 5x4 to 4x4 in at most 31m. So, simple upper bound is 38m+31m+43m=112m. One can obtain 110m using some cancellations.

However, I believe there is better choice of subgoals. The space of third stage in the solution above is 16!/2=10,461,394,944,000, while second stage has only 20!/15!=1,860,480 states. Maybe it is better to have substages of roughly equal space.

I wrote program that takes as input definition of subgoal and maximal amount of move and calculates God's distribution. It does not use any disk files, however. Now I check it on some simple puzzles. Currently, it cannot work with subpuzzles of space >= 2^32. Also, it does not use of any symmetries.

» login or register to post comments

More walking distance values

Submitted by rokicki on Wed, 08/10/2011 - 19:48.
I've generalized my walking distance generator, and have computed walking distance tables for the "easy" positions. This gives us new lower bounds for some mxn tile puzzle sizes. 
w h  d  md    states a  lb gn
- - -- --- --------- - --- --
2 2  3   3         4 1   6  6
2 3 10   6        33 2  15 21
2 4 21  13       480 2  28 36
2 5 36  20     11010 2  45 55
2 6 55  31    367560 2  66 80
2 7 78  42  16854390 2  91
2 8     57              91
2 9     72              91
3 2  5   5         6 1
3 3 14  10       105 3  28 31
3 4 29  21      4324 1  47 53
3 5 46  32    352560 3  68
3 6 69  49  50388240 3  95
3 7     66              96
3 8     89             123
3 9    112             150
4 2  7   7         8 1
4 3 18  14       255 4
4 4 35  29     24964 2  70 80
4 5 58  44   5977015 1 101
4 6     67             118
4 7     90             149
4 8    121             188
4 9    152             227
5 2  9   9        10 1
5 3 22  18       525 5
5 4 43  37    107712 2
5 5 70  56  65650495 1 140
5 6     85             165
6 2 11  11        12 1
6 3 26  22       966 6
6 4 51  45    377872 1
6 5 80  68 525320120 8
7 2 13  13        14 1
7 3 30  26      1638 7
7 4 59  53   1135240 1
8 2 15  15        16 1
8 3 34  30      2610 8
8 4 67  61   3022888 1
9 2 17  17        18 1
9 3 38  34      3960 9
9 4 75  69   7307608 1
The columns are: 
w:  width
h:  height
d:  maximum walking distance
md:  Manhattan distance for all-flipped
states:  size of the walking distance table
a:  count of antipodes
lb:  new lower bound for w x h puzzle
gn:  God's number (when known) for w x h puzzle
In particular, this sets a new lower bound of 101 for the 4x5 puzzle and a lower bound of 95 for the 3x6 puzzle. Both of these are as of yet unsolved (to my knowledge) and they are significantly easier than the 5x5 puzzle. (I don't believe the 3x5 puzzle has been solved, either, with a starting position of a corner; this one is certainly solvable with current technology.) The generalized program still needs some improvements; with a better indexing scheme, it should be possible to compute additional entries in the above table. Also, I need to modify the program to display the antipodes.
» login or register to post comments

Upper bounds

Submitted by stannic on Thu, 08/11/2011 - 17:17.

Any 5x4 instance can be solved in 138s. 58s is sufficient to reduce 5x4 to 4x4; 80s is sufficient to solve 4x4. Upper bound in MTM is 74m with the same reduction to 4x4.

Any 5x3 instance can be solved in 92s. Reduction from 5x3 to 3x3 requires 61s; 3x3 can be solved in 31s. The same reduction gives upper bound of 55m in MTM metric.

The following 5x3 instance cannot be solved in 76s or less. My program current on 78s. It can be solved in 84s, however.

 4  3  2  1  0
 9  8  7  6  5
14 13 12 11 10
» login or register to post comments

Lower bound is 80s

Submitted by stannic on Fri, 08/12/2011 - 04:05.

No solution in 78s or shorter for the configuration above. So lower bound in STM is 80s for 3x5. Depth 78 took about five hours. Factor is about 5x.

I searched for information about various "not so hard" puzzles that can be solved today. On 3x5 puzzle, diameter is 84s (Richard E. Korf, Best-First Frontier Search with Delayed Duplicate Detection). However, in this analysis blank tile started from center square.

So upper bound is 87s for case with blank square in the corner.

The same paper says that 2x7 puzzle was solved, and diameter was 108s.

» login or register to post comments

lower bound 82s for 3x5

Submitted by stannic on Sat, 08/13/2011 - 04:57.

No solution in 80s. So lower bound for 3x5 is 82s.

» login or register to post comments

WD "solver"

Submitted by rokicki on Thu, 08/11/2011 - 16:33.
Since I've been unable so far to build a full walking-distance (WD) table for some of the larger sizes not in that table above, instead I built a WD "solver" that uses the Manhattan distance as a pruning metric. I've been running the all-flipped positions through this solver for the sizes 4x6, 5x6, 6x6, and 5x7.

So far, for 4x6 I've shown that the WD diameter is at least 81; for the 5x6, at least 97; for the 6x6, at least 115; for the 5x7, at least 130.

This gives a new lower bound on the 6x6 of at least 230; on the 4x6 of at least 132; and on the 5x6 of at least 177.

On the 7x7, we get a WD diameter of at least 176, which gives a lower bound on this size of at least 352.
» login or register to post comments

Confirmation for 5x4

Submitted by stannic on Wed, 08/10/2011 - 20:06.

I can confirm results for 5x4 puzzle. I tried optimal solver for this puzzle using WD heuristic. Even this puzzle is rather hard. I tried 180-degree turned 5x4 position with single additional 18-19 swap. By the way, your lower bound of 101s for 5x4 is not correct because turned 180 degrees position cannot be reached because of parity.

However, I just rerun my 5x4 solver and it cannot find solution in less than 107s for the following.

18 19 17 16 15
14 13 12 11 10
 9  8  7  6  5
 4  3  2  1  0
» login or register to post comments

Bounds

Submitted by rokicki on Thu, 08/11/2011 - 11:49.
The following five bounds in the above table can be called into question by parity arguments: 3x4, 3x8, 4x5, 4x7, and 4x9.

For 3x4, 3x8, and 4x5, due to multiple antipodes that have different parity in one or the other walking distance, the bound is indeed correct.

For 4x7 and 4x9, we used the Manhattan distance for one of the orientations. For these, we can swap the blank with the number two over, changing the parity of the position but not the blank, and not decreasing the Manhattan distance. (Indeed, I should be using larger Manhattan distances for some of the values in the above table, since positioning the blank other than at its 180 degree swapped position can actually increase the Manhattan distance for that row.)
» login or register to post comments

Very nice! Thanks!

Submitted by rokicki on Wed, 08/10/2011 - 20:13.
Fascinating. You're correct; my lower bounds in that table may not be attainable due to parity issues if the antipodes are not able to be combined. I'll investigate that.

So you've got a new lower bound of 107 for the 5x4, that's excellent!
» login or register to post comments

Attempt to solve the 180 flip position in < 156

Submitted by rokicki on Tue, 08/09/2011 - 21:44.
So, I modified my optimal solver to only permit right-hand turns (so, for instance, no U -> L transitions are permitted). I then ran it on the 180 flip position, and it found 12,225 different solution sequences of length 156. (This includes the 56 * 56 distinct ways to do a 90 degree rotate followed by another 90 degree rotate).

I've been solving the positions reached by prefixes of these solutions, trying to determine if any of the suffixes, when the restriction on the turns is lifted, might have a shorter solution (and thus, then, the 180 degree flipped position has a distance of less than 156.)

I've finished with all suffixes of length 124 or less, with no success. I'm currently working on suffixes of length 126 (thus, those reached by only 30 moves).

The lack of success makes me think it might be more likely that this position is actually at distance 156. In order to prove that I will probably have to make substantial improvements to my optimal solver.

-tom
» login or register to post comments

Right-hand turns

Submitted by stannic on Sat, 08/13/2011 - 15:51.

BTW, is there a way to build God's database for this kind of puzzle? One possible solution is to include additional state information, previous move. This additional information can be used in indexing. But in this case we should have at least 4 times larger database.

» login or register to post comments

I believe you're correct; the

Submitted by rokicki on Sat, 08/13/2011 - 19:05.
I believe you're correct; the only reasonable way is to include the direction of the previous move. It's not 100% dense, however (since for edge and corner slot positions there are fewer previous moves) but it does make the state space larger.

Of course, the normal walking distance is still a valid heuristic, just maybe not very effective.
» login or register to post comments

Pattern databases

Submitted by stannic on Wed, 08/10/2011 - 20:26.

I also have optimal solver for 5x5. Currently it is very, very slow. My program is about 20x slower than your; I'll improve it.

I compared counts of nodes with only WD heuristic and with WD heuristic and pattern databases. I used the following partition scheme (6-tile additive PDBs).

.AAAA
AABBB
BBBCC
CCCCD
DDDDD

It seems like PDBs can improve solver when solving random instances. I tried one random instance; couns of nodes was about 4x less than those without using PDBs.

However, I tried turned 180-degree position, and difference in nodes is about 3%. My program was even slower with PDBs.

» login or register to post comments

All optimal (STM) solutions for 5x5_90

Submitted by stannic on Tue, 08/09/2011 - 06:23.

Maybe 90-degree flipped goal has shorter solution that many other "square roots" because all tiles is in correct "structure" although they are not in correct squares. For example, any two tiles that should be in neighbour squares in goal state are in neighbour squares in 90-degree flipped; that is, tiles already grouped. This is just observations, however.

Below listed all optimal in STM metric solutions for 90-degree flipped goal. There is 56 solutions. I used almost the same format to record maneuvers as Bruce Norskog in his solver (The Fifteen Puzzle can be solved in 43 "moves"). Maneuver consists of pairs such as 3L or 2U. 3L means that we should move three tiles leftward; 2U means to move two tiles up. I used also abbreviations such as 2URD = 2U 2R 2D to make maneuvers shorter and more readable.

 20 15 10  5  0
 21 16 11  6  1
 22 17 12  7  2
 23 18 13  8  3
 24 19 14  9  4

  1 (78s*, 23m) 3URDL 4URDLUR 3DL 2URD 3LU 4RDLURD
  2 (78s*, 23m) 3UR 2D 3LU 4RDLURD 3LU 2RD 3LU 4RDLURD
  3 (78s*, 23m) 3UR 2DLUR 3DL 4URDLUR 3D 4L 3U 4RDLURD
  4 (78s*, 25m) 3UR 2DLURD 3LU 4RDLURD 3L 1UL 3U 4RDLURD
  5 (78s*, 23m) 3UR 2DLU 3RD 4LURDLU 3RDLU 4RDLURD
  6 (78s*, 23m) 3UR 2DL 3UR 4DLURDL 3UR 2D 3LU 4RDLURD
  7 (78s*, 23m) 3U 4R 3D 4LURDLU 3RD 2LURD 3LU 4RDLURD
  8 (78s*, 25m) 3U 1RU 3R 4DLURDL 3UR 2DLURD 3LU 4RDLURD
  9 (78s*, 23m) 4U 3R 4D 3L 4URDLUR 3DL 2URDL 3UR 4DLURD
 10 (78s*, 23m) 4U 3RDLU 4RDLURD 3LU 2RDL 3UR 4DLURD
 11 (78s*, 23m) 4U 3RD 2LUR 3DL 4URDLUR 3DLUR 4DLURD
 12 (78s*, 23m) 4U 3RD 2LURD 3LU 4RDLURD 3L 4U 3R 4DLURD
 13 (78s*, 25m) 4U 3RD 2LURDL 3UR 4DLURDL 3U 1RU 3R 4DLURD
 14 (78s*, 23m) 4U 3RD 2LU 3RD 4LURDLU 3RD 2L 3UR 4DLURD
 15 (78s*, 23m) 4U 3RD 2L 3UR 4DLURDL 3UR 2DL 3UR 4DLURD
 16 (78s*, 25m) 4U 3R 1DR 3D 4LURDLU 3RD 2LURDL 3UR 4DLURD
 17 (78s*, 23m) 4URDL 3URDL 4URDLUR 3DL 2URD 3LU 4RD
 18 (78s*, 23m) 4URDL 3UR 2D 3LU 4RDLURD 3LU 2RD 3LU 4RD
 19 (78s*, 23m) 4URDL 3UR 2DLUR 3DL 4URDLUR 3D 4L 3U 4RD
 20 (78s*, 25m) 4URDL 3UR 2DLURD 3LU 4RDLURD 3L 1UL 3U 4RD
 21 (78s*, 23m) 4URDL 3UR 2DLU 3RD 4LURDLU 3RDLU 4RD
 22 (78s*, 23m) 4URDL 3UR 2DL 3UR 4DLURDL 3UR 2D 3LU 4RD
 23 (78s*, 23m) 4URDL 3U 4R 3D 4LURDLU 3RD 2LURD 3LU 4RD
 24 (78s*, 25m) 4URDL 3U 1RU 3R 4DLURDL 3UR 2DLURD 3LU 4RD
 25 (78s*, 23m) 4URDLU 3R 4D 3L 4URDLUR 3DL 2URDL 3UR 4D
 26 (78s*, 23m) 4URDLU 3RDLU 4RDLURD 3LU 2RDL 3UR 4D
 27 (78s*, 23m) 4URDLU 3RD 2LUR 3DL 4URDLUR 3DLUR 4D
 28 (78s*, 23m) 4URDLU 3RD 2LURD 3LU 4RDLURD 3L 4U 3R 4D
 29 (78s*, 25m) 4URDLU 3RD 2LURDL 3UR 4DLURDL 3U 1RU 3R 4D
 30 (78s*, 23m) 4URDLU 3RD 2LU 3RD 4LURDLU 3RD 2L 3UR 4D
 31 (78s*, 23m) 4URDLU 3RD 2L 3UR 4DLURDL 3UR 2DL 3UR 4D
 32 (78s*, 25m) 4URDLU 3R 1DR 3D 4LURDLU 3RD 2LURDL 3UR 4D
 33 (78s*, 25m) 4URDLUR 3D 1LD 3L 4URDLUR 3DL 2URDLU 3RD
 34 (78s*, 23m) 4URDLUR 3D 4L 3U 4RDLURD 3LU 2RDLU 3RD
 35 (78s*, 23m) 4URDLUR 3DL 2UR 3DL 4URDLUR 3DL 2U 3RD
 36 (78s*, 23m) 4URDLUR 3DL 2URD 3LU 4RDLURD 3LURD
 37 (78s*, 25m) 4URDLUR 3DL 2URDLU 3RD 4LURDLU 3R 1DR 3D
 38 (78s*, 23m) 4URDLUR 3DL 2URDL 3UR 4DLURDL 3U 4R 3D
 39 (78s*, 23m) 4URDLUR 3DL 2U 3RD 4LURDLU 3RD 2LU 3RD
 40 (78s*, 23m) 4URDLUR 3DLUR 4DLURDL 3UR 2DLU 3RD
 41 (78s*, 25m) 4URD 3L 1UL 3U 4RDLURD 3LU 2RDLUR 3DL 4URD
 42 (78s*, 23m) 4URD 3LU 2R 3DL 4URDLUR 3DL 2UR 3DL 4URD
 43 (78s*, 23m) 4URD 3LU 2RD 3LU 4RDLURD 3LU 2R 3DL 4URD
 44 (78s*, 25m) 4URD 3LU 2RDLUR 3DL 4URDLUR 3D 1LD 3L 4URD
 45 (78s*, 23m) 4URD 3LU 2RDLU 3RD 4LURDLU 3R 4D 3L 4URD
 46 (78s*, 23m) 4URD 3LU 2RDL 3UR 4DLURDL 3URDL 4URD
 47 (78s*, 23m) 4URD 3LURD 4LURDLU 3RD 2LUR 3DL 4URD
 48 (78s*, 23m) 4URD 3L 4U 3R 4DLURDL 3UR 2DLUR 3DL 4URD
 49 (78s*, 25m) 4UR 3D 1LD 3L 4URDLUR 3DL 2URDLU 3RD 4LURD
 50 (78s*, 23m) 4UR 3D 4L 3U 4RDLURD 3LU 2RDLU 3RD 4LURD
 51 (78s*, 23m) 4UR 3DL 2UR 3DL 4URDLUR 3DL 2U 3RD 4LURD
 52 (78s*, 23m) 4UR 3DL 2URD 3LU 4RDLURD 3LURD 4LURD
 53 (78s*, 25m) 4UR 3DL 2URDLU 3RD 4LURDLU 3R 1DR 3D 4LURD
 54 (78s*, 23m) 4UR 3DL 2URDL 3UR 4DLURDL 3U 4R 3D 4LURD
 55 (78s*, 23m) 4UR 3DL 2U 3RD 4LURDLU 3RD 2LU 3RD 4LURD
 56 (78s*, 23m) 4UR 3DLUR 4DLURDL 3UR 2DLU 3RD 4LURD
found 56 solutions.
» login or register to post comments

I also calculated the 56 solu

Submitted by rokicki on Tue, 08/09/2011 - 12:07.
I also calculated the 56 solutions to this position, hoping against hope that there might be a potential move cancellation.

Unfortunately, all the moves appear to be "right turns", and thus all sequences start with U and end with D, so when composing the sequence with the same rotated, there are no cancellations.

I then tried to find the shortest solutions to the rotated-180 position that consisted only of right turns. I found no such solutions of length less than 156.
» login or register to post comments

Counts out to depth 24

Submitted by rokicki on Mon, 08/08/2011 - 15:45.
I wrote a quick and dirty program to push the counts for the 24-puzzle out to a distance of 27. This won't help with a lower bound much because it's pretty clear this puzzle has a long tail in the distance distribution, much like the 15-puzzle. This run took 9 hours. I can probably push it out another few levels if anyone is interested. 
 d       at d       <= d
-- ---------- ----------
 0          1          1
 1          2          3
 2          4          7
 3         10         17
 4         26         43
 5         64        107
 6        159        266
 7        366        632
 8        862       1494
 9       1904       3398
10       4538       7936
11      10238      18174
12      24098      42272
13      53186      95458
14     123435     218893
15     268416     487309
16     616374    1103683
17    1326882    2430565
18    3021126    5451691
19    6438828   11890519
20   14524718   26415237
21   30633586   57048823
22   68513713  125562536
23  143106496  268669032
24  317305688  585974720
25  656178756 1242153476
26 1442068376 2684221852
27 2951523620 5635745472
» login or register to post comments

Verified up to depth 14

Submitted by stannic on Tue, 08/09/2011 - 07:01.

Here is numbers without accounting cycles in search tree. Only trivial cycles (LR, RL, UD, DU) was counted. I hope this table is correct; I never did such calculations before. Up to depth 6 counts are the same, and at depth 6 there is one identity (LURDLU = ULDRUL); it seems to be correct. I used two 5x5 matrices, one for previous depth counts by positions of blank square, and other for new depth.

 depth          positions           cumulative
   0                    1                    1
   1                    2                    3
   2                    4                    7
   3                   10                   17
   4                   26                   43
   5                   64                  107
   6                  160                  267
   7                  372                  639
   8                  888                 1527
   9                 1996                 3523
  10                 4872                 8395
  11                11324                19719
  12                27608                47327
  13                63524               110851
  14               154560               265411
  15               355836               621247
  16               866008              1487255
  17              1993748              3481003
  18              4854112              8335115
  19             11181004             19516119
  20             27216632             46732751
  21             62666404            109399155
  22            152545216            261944371
  23            351287868            613232239
  24            855126456           1468358695
  25           1969145140           3437503835
  26           4793422368           8230926203
  27          11038257644          19269183847
  28          26869921784          46139105631
  29          61875104900         108014210531
  30         150620083968         258634294499
  31         346845023580         605479318079
  32         844310380984        1449789699063
  33        1944255717908        3394045416971
  34        4732821388768        8126866805739
  35       10898629867660       19025496673399
  36       26530081408760       45555578082159
  37       61092812938468      106648391020627
  38      148715706572992      255364097593619
  39      342458942111868      597823039705487
  40      833633596506552     1431456636212039
  41     1919671041238516     3351127677450555
  42     4672975658429856     8024103335880411
  43    10760814742109228    18784918077989639
  44    26194605187737080    44979523265726719
  45    60320298037642820   105299821303369539
  46   146835201178579584   252135022481949123
  47   338128525775992476   590263548257941599
  48   823092252954271672  1413355801212213271
  49  1895396782894748372  3308752584106961643
  50  4613885817983419744  7922638402090381387
» login or register to post comments

Calculated as well

Submitted by rokicki on Tue, 08/09/2011 - 12:06.
I also calculated this using a different technique.
I got the same numbers, exactly.

Using this technique, we find a lower bound of 67 moves, which is of course way lower than the existing lower bound of 150. Like the 15 puzzle, this puzzle apparently has a long tail.
» login or register to post comments