Twenty-Four puzzle, some observations

There is one more special heuristic implemented in Takahashi's solver, Invert Distance heuristic. I did not mention it before because it cannot give better lower bound; its maximal value is 138 with Twenty-Four puzzle. But it probably can be used in optimal solver.

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

We should count all inversions. If i < j and tile i is after tile j, then it is inversion. In given example, InvCount = 105.

Any allowed STM move cannot change InvCount value by more than 3. Any horizontal move never changes InvCount, and vertical move can change InvCount by -3, -1, +1 or +3. So we can divide InvCount by 3 and get minimal number of vertical moves required to go to goal position. 105 / 3 = 35 vertical moves.

In the same way we can count inversions by columns and get minimal number of horizontal moves. In given example, it is 35 also. So lower bound is 35 + 35 = 70 STM.

If InvCount value does not divide by 3 then we can add remainder. If remainder is 1 then we can add 1 because even after InvCount / 3 moves we still cannot reach goal. If remainder is 2 then we can add 2 because it is not possible to make change +-2 in only one move.

So actual formula is InvertDistance = InvCount / 3 + InvCount % 3.

In Twenty-Four case, we can divide by 4 because all possible changes are -4, -2, 0, +2, +4. However, it seems that cannot simply add remainder; if there is remainder then we can only add 1.

Takaken solver also uses the following pattern databases:

AAAB  BCCC
ABBC  ABBC
ABCC  ABBC
BCC   AAA

Each of these databases has size 12,108,096.

Thanks for independent verification. BTW, how you implemented your solver? Do you use associative array to store God's database or you was able to calculate indices?

Did not expect this so soon and with only one WD heuristic. Of course each next ply will be more difficult. Can I ask how quicky grows the number of nodes?

I combined results in MTM metric with those obtained by Bruce Norskog. 9 "fringe" tiles can be solved in at most 38+31=69m, and remaining tiles can be solved as Fifteen puzzle in at most 43m (if all was correct). So upper bound in MTM metric should be 112m.

Keep thinking about lower bound in MTM. Of course one can divide 148 by 4 as one move cannot touch more than 4 tiles. But 37m for 5x5 is not good when we know 43m for 4x4.

After first move, there is 4 choices for each next move. Inequality 8*4^x<25!/2 is true for x<40. It is better that dividing WD by 4 but also not so good.

Of course you can stop your solver any time :) I'll try to write my own solver, I did not yet. Anyway, thanks you.

I tried how it is possible to rotate/reflect box with tiles. Unfortunately, in 4x4 case it is impossible to solve turned 90 degree:

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

But I tried to swap tiles 14 and 15 in position above and takaken's solver gave me 39 moves. Flipped 180 position requires 78 moves; that is, twice more. It was strange for me.

  4  8 12  0
  3  7 11 14
  2  6 10 15
  1  5  9 13
Optimal solution is 39moves.

 13  9  5  1
 15 10  6  2
 14 11  7  3
  0 12  8  4
Optimal solution is 39moves.

In 3x3 puzzle, flipped-180 position requires 28 moves, and turned-90 position requires 14 moves.

 0 8 7     3 6 0
 6 5 4     2 5 8
 3 2 1     1 4 7
 28s*      14s*

This strange relationship observed also in 2x2 puzzle. I cannot understand it. Maybe it is simplest way indeed, and this is true for any NxN puzzle?

I'll call the X-degree flipped NxN goal configuration "NxN_X". For example, 5x5_90 is 90-degree flipped 5x5 goal.

I tried to get solution in 150s, 152s or 154s for 5x5_180 using some intermediate state.

[1]
 4  9 14 19 24
 3  8 13 18 23
 2  7 12 17 22
 1  6 11 16 21
 0  5 10 15 20
5x5_90
square root of 5x5_180
78s*

[2]
 4  9 14 19 24
 3 16 11  6 23
 2 17 12  7 22
 1 18 13  8 21
 0  5 10 15 20
square root of 5x5_180
80s*

[3]
 0  1  2  3  4
 5 18 17 16  9
10 13 12 11 14
15  8  7  6 19
20 21 22 23 24
"inner3x3-flipped180"
42s*

[4]
24 23 22 21 20
19  6  7  8 15
14 11 12 13 10
 9 16 17 18  5
 4  3  2  1  0
"outer-flipped180"
120s*

Configuration [1] was used to find 156s solution. [2] can be used to find 160s solution. [3] and [4] can be combined to get 162s solution; it is possible to save four moves and still get 158s; that is, [1] and [2] gives better solutions.

Without any proof, it seems like square roots of permutations of tiles can be used to get good solutions. Maybe even there is something like square root of "5x5_180" with solution in 77s*, 76s* or 75s* and corresponding solution in 154s, 152s or 150s for "5x5_180". I guess there is beautiful mathematical explanation of this but I cannot find yet.

By the way, "6x6_180" position requires at most 282s. 16 inner tiles can be "flipped" in 96s, and outer tiles can be cycled in 190s. So there is solution in 286s. However, flipping inner 4x4 maneuver (see below) starts with 2U 2L and ends with 2R 2D; it is possible to include these four moves in 190s cycling maneuver and get 282s solution.

 0  1  2  3  4  5
 6 28 27 26 25 11
12 22 21 20 19 17
18 16 15 14 13 23
24 10  9  8  7 29
30 31 32 33 34 35

180-Flipping inner 4x4. Before applying maneuver, blank tile should be in square 0.
(96s)
2U 2L 1D 1R  2U 1L 2D 2L  1U 1R 1D 1L
2U 1R 1U 1R  2D 1L 1U 1R  2D 1L 1U 1L
1U 1R 1U 1L  1D 1R 1U 1R  2D 2R 1U 1L
1U 1L 2D 1L  1U 2R 1D 3L  1U 4R 1D 1L
1D 1L 1U 1L  1U 2R 2D 3L  1U 1R 1D 1L
2U 3R 1D 2L  1U 1R 1D 2R  2D

In 6x6 sliding tile puzzle, 16 inner tiles can be turned 180 degrees in 92 moves. This transformation is equivalent to the following 5x5 configuration:

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

I've used suboptimal solver to get solution in 96s in my earlier post. Optimal solution to configuration above seems to be 92s*.

(92s*, 39m) 2L 4U 2L 3D 2RU 1L 2D 1R 2U 1L 2D 1RDLU 2R 3ULDRULDRULDRULDRULD 1RD 3R

Outer tiles in 6x6 can be turned 180 degrees in 190s, so solution is 190s+92s=282s; however, six moves can be saved. Solution above begins with 2L and ends with 3R; we can include these moves in 190s maneuver that solves outer tiles and finally get 276s suboptimal solution for 6x6 turned 180.

 35 34 33 32 31 30
 29 28 27 26 25 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
(276s, 76m)
5RD                                                                   // preparation moves
2L 4U 2L 3D 2RU 1L 2D 1R 2U 1L 2D 1RDLU 2R 3ULDRULDRULDRULDRULD 1RD   // flipping inner tiles
2L 5URDLURDLURDLURDLURDLURDLURDLURDLURD                               // solving outer tiles

Turned 90-degree 6x6 configuration requires 141s*. This was found using manhattan solver. I'll give one of 120914 141s* solutions.

34591 (141s*, 35m) 5LDR 4UL 3DRU 2L 4D 3R 5U 4L 5D 4R 5ULDRUL 4DR 3UL 2DR 3UL 4D 5R 4U 5LDR

Repeating 90-degree rotation twice gives obviously 282s which is not optimal as we know 276s. So in arbitrary NxN puzzle, repeating twice 90-degree rotation does not necessarily lead to optimal solution.

The following position also requires 141s*. Outer tiles rotated clockwise, while inner tiles rotated counterclockwise.

 30 24 18 12  6  0
 31 10 16 22 28  1
 32  9 15 21 27  2
 33  8 14 20 26  3
 34  7 13 19 25  4
 35 29 23 17 11  5
210 (141s*, 43m) 5UR 2D 1LU 3LDRULDR 2U 1RDLU 2L 1D 2RU 3LD 2R 1U 2RD 5LURDLURDLURDLURD

90-degree rotated positions seems to be very simple for manhattan solver. I've solved 7x7 puzzle 90-degree rotated position in 222s* using only manhattan heuristic. Here is last found solution.

 42 35 28 21 14  7  0
 43 36 29 22 15  8  1
 44 37 30 23 16  9  2
 45 38 31 24 17 10  3
 46 39 32 25 18 11  4
 47 40 33 26 19 12  5
 48 41 34 27 20 13  6
47040 (222s*, 49m) 6UR 5D 4LUR 5D 6LURDLU 5R 1DR 5D 6LURDLU 5RD 4LURDL 3UR 2DLUR 3DL 4URDLU 5RD 6LURD

The following position requires 226s.

  6 13 20 27 34 41 48
  5 36 29 22 15  8 47
  4 37 30 23 16  9 46
  3 38 31 24 17 10 45
  2 39 32 25 18 11 44
  1 40 33 26 19 12 43
  0  7 14 21 28 35 42
369798 (226s*, 57m) 6L 1D 5R 3DLUR 4DLU 1LDRU 4RDL 3UR 2DLU 3RD 4L 3U 1LDR 2U 4RDL 2U 1L 3D 6RULDRULDRULDRULDRULDR

I like to think of a transformation (call it h) on a puzzle as the square root of another transformation (call it g) on the puzzle if h² = g.

With an nxn tile puzzle, we can only compose a transformation with itself if that transformation leaves the empty square in the same place after the transformation as before. If we allow the transformations g & h to include rotating the puzzle (to compensate for certain changes in the location of the empty square), then the transformation that rotates the tile arrangement 90 degrees can be viewed as a square root of the transformation that rotates the arrangement of the tiles 180 degrees using my definition of square root. (The rotation of the puzzle as a whole will not be counted as a move even though we regard it as part of the transformation.)

I note that square roots by my definition are not generally unique. A transformation can have many square roots (or none at all). If h is a square root of g, and g has an optimal maneuver of M moves, then clearly M/2 is a lower bound for the number of moves required to perform the transformation h. But h may require more than M/2 moves. It might even require more than M moves.

Viewing the puzzle as just a permutation of 24 tiles and an empty square, the permutation that moves every pieces 90 degrees around the puzzle fits my definition of a square root. The problem is that moves on the 24 puzzle depend upon where the empty square is. So squaring a permutation is not generally possible simply by repeating the same moves. In fact, squaring a permutation may result in an illegal position. For instance, from the solved state (of the 24-puzzle), move tile #1, then tile #6. This produces the permutation (0,6,1) in cycle notation. As this is a 3-cycle, clearly (0,1,6) is both a square and a square root of (0,6,1), and similarly (0,6,1) is both a square and a square root of (0,1,6). But note that (0,1,6) is an unreachable position.

So while a square root can possibly provide a good solution for a position, one can not always arrive at a good solution this way. A given position does not necessarily have square roots. A square root as a pure permutation may not always be a reachable permutation. If a position does have one or more square roots, there is no guarantee these will be nearly twice as close to solved as the original, and may even be farther from solved.

Thanks for your explanation. Suppose we have transformation X that accepts tile arrangement with blank tile in the upper left corner, performs some number of disjoint 2-cycles of tiles and then rotates resulting tile arrangement 90 degrees clockwise. Let R90 be counterclockwise rotation of the whole puzzle (this is not counted as move). Then transformation X R90 performs only some number of disjoint 2-cycles of tiles. Then Y = X R90 X R90³ performs "clean" 180-degree rotation of the whole tile arrangement because all 2-cycles that are performed by transformation X performs twice by transformation Y. That is, by your definition transformation X is square root of transformation that rotates tile arrangement 180 degrees.

I will give example of maneuver X for 4x4 tile puzzle.

X = 3U 2L 1D 1L 1U 1R 3D 2R 3U 3L 2D 3R 2U 3L 3D 2R 3U 2L 3D

 Initial state          After X          After X R90
    0  1  2  3       8 12  4  0           0  1  3  2
    4  5  6  7      13  9  5  1           4  5  6  7
    8  9 10 11      14 10  6  3          12  9 10 15
   12 13 14 15      11 15  7  2           8 13 14 11

(0-based goal)                    (0)(2,3)(8,12)(11,15)

By your definition, transformation T is square root of transformation that rotates nxn puzzle 180 degrees if it has the following properties:
1. T accepts any tile arrangement with blank tile in square (0;0) (i.e., upper left corner).
2. T leaves blank square in square (n-1;0) (upper right corner).
3. Transformation (T R90)² does nothing.

If I understand you correctly, it seems like any such square root can be obtained using formula (T R90) = P, where P is product of some number of disjoint 2-cycles (however, 0 should not be in any of these cycles). In the example above, T = X, and (T R90) = (0)(2,3)(8,12)(11,15).

I tried to count all such square roots of transformation that rotates 5x5 puzzle 180 degrees. Let m be the number of disjoint 2-cycles that are performed by transformation T. We should select exactly (2*m) tiles from 24 existing physical tiles; there is 24! / (24 - 2 * m)! ways to do this. However, order of two tiles that are in the same 2-cycle does not matter so we can divide by 2^m. Also, order of cycles does not matter so we can divide by (m!).
Finally, there is 24! / (24 - 2 * m)! / 2^m / m! transformations that performs exactly m 2-cycles on 5x5 tile puzzle. It is possible to perform from 0 to 12 2-cycles on 5x5 puzzle.

 m    # of ways to select exactly m disjoint 2-cycles of tiles
 0    24!  /  (24 - 0)!   / 1      / 0!            =                  1
 1    24!  /  (24 - 2)!   / 2      / 1!            =                276
 2    24!  /  (24 - 4)!   / 4      / 2!            =             31,878
 3    24!  /  (24 - 6)!   / 8      / 3!            =          2,018,940
 4    24!  /  (24 - 8)!   / 16     / 4!            =         77,224,455
 5    24!  /  (24 - 10)!  / 32     / 5!            =      1,853,386,920
 6    24!  /  (24 - 12)!  / 64     / 6!            =     28,109,701,620
 7    24!  /  (24 - 14)!  / 128    / 7!            =    265,034,329,560
 8    24!  /  (24 - 16)!  / 256    / 8!            =  1,490,818,103,775
 9    24!  /  (24 - 18)!  / 512    / 9!            =  4,638,100,767,300
 10   24!  /  (24 - 20)!  / 1024   / 10!           =  6,957,151,150,950
 11   24!  /  (24 - 22)!  / 2048   / 11!           =  3,794,809,718,700
 12   24!  /  (24 - 24)!  / 4096   / 12!           =    316,234,143,225

 total                                             = 17,492,190,577,600

So there is 17,492,190,577,600 such transformations T that (T R90) = P, where P is product of disjoint 2-cycles. We can change R90 by reflection through vertical axis (left-right). Let this reflection be S. Then (T S) = P, where P is product of disjoint 2-cycles. Calculations are the same, and we can get another 17,492,190,577,600 "square roots".

Not all these square roots are reachable puzzle arrangements, as you mention. It depends on reachability of tile arrangement that can be obtained by transformation R90 (or S, if we use reflection instead of rotation counterclockwise). In 5x5 puzzle, both R90 and S transformations lead to reachable tile arrangements; so we can perform only any even number of 2-cycles of physical tiles to preserve reachability of resulting square root; that is, 0, 2, 4, 6, 8, 10 or 12 2-cycles. Summing only these rows in table, we can find the number of reachable square roots. This is 8,792,390,355,904.

Squaring (s t) does not produce (s t s' t'), so in my view (s t) would not be a square root of (s t s' t'). Of course, one can infer the same kind of distance relationships between (s t) and (s t s' t') as between (s f) and (s f)². So such a position could be just as useful in determining a bound on the would-be "square" position as a square root (by my definition) would be.

I acknowledge that in the example of (s f), that (s f)² is not exactly the same as (s f s f'), but both really represent the same intrinsic state of the puzzle (just that one has the puzzle in a non-standard orientation), so I am willing to think of (S f) as a sort of "virtual" square root of (s f s f').

It seems to me Tom's definition of "square root" would imply for a group puzzle, that every legal position of the puzzle would be a square root of the identity. I only would consider order-1 and order-2 positions to be square roots of the identity. I would consider a group puzzle to have an average of exactly 1 square root per position.

I've used the takaken solver before. I've used it to find out the single-tile metric distances for the multi-tile metric antipodes, for example. So I've been aware of the Walking Distance heuristic, but I didn't really know what it was exactly. So my thanks to stannic for providing additional information about the Walking Distance heuristic. I think I understand how to calculate it now.

I looked at your antipodes in MTM. First two of them is very symmetrical. First is reflection of goal about main diagonal, and second is rotation 180 of first. It is also strange for me.

Note that the first antipode is the same as the solved state except rows and columns are transposed.

Now take the 2nd antipode, which is the same position rotated 180 degrees. Make one multitile move sliding the tiles numbered 13, 14, and 15 up. Now rotate the puzzle 90 degrees counterclockwise. The configuration should now look like this.

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

Now apply a 43-move maneuver that would solve the first antipode. This will transpose the rows and columns of the above configuration, giving this:

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

 depth       new      total
     1         1          2
     2         2          4
     3         3          7
     4         7         14
     5        12         26
     6        32         58
     7        51        109
     8       124        233
     9       190        423
    10       450        873
    11       669       1542
    12      1538       3080
    13      2170       5250
    14      4839      10089
    15      6454      16543
    16     14039      30582
    17     17520      48102
    18     37031      85133
    19     43146     128279
    20     88805     217084
    21     96196     313280
    22    192532     505812
    23    194824     700636
    24    379743    1080379
    25    359507    1439886
    26    680999    2120885
    27    607734    2728619
    28   1120603    3849222
    29    944886    4794108
    30   1694006    6488114
    31   1360108    7848222
    32   2369139   10217361
    33   1816212   12033573
    34   3067879   15101452
    35   2261336   17362788
    36   3702816   21065604
    37   2623265   23688869
    38   4148672   27837541
    39   2844873   30682414
    40   4350752   35033166
    41   2872722   37905888
    42   4216272   42122160
    43   2699250   44821410
    44   3823128   48644538
    45   2350552   50995090
    46   3171751   54166841
    47   1879601   56046442
    48   2445261   58491703
    49   1383052   59874755
    50   1701761   61576516
    51    910910   62487426
    52   1078879   63566305
    53    542962   64109267
    54    616621   64725888
    55    279543   65005431
    56    306588   65312019
    57    114860   65426879
    58    126372   65553251
    59     41125   65594376
    60     42833   65637209
    61      5053   65642262
    62      5528   65647790
    63      1316   65649106
    64      1236   65650342
    65        81   65650423
    66        48   65650471
    67        13   65650484
    68         9   65650493
    69         1   65650494
    70         1   65650495