Home »

Fifteen Puzzle MTM

Submitted by B MacKenzie on Sat, 07/05/2014 - 07:38.
I wrote a fifteen puzzle simulation back in 2010 which I recently went back to and updated before submitting it as freeware to the Apple App Store.

Playing around, I then plugged my model into my coset solver framework and performed a states at depth enumeration in the multi-tile metric out to depth 23:

XV Puzzle Enumerator Client(bdm.local)

XV Coset Solver
	Fixed tokens in subgroup: 0, 1, 2, 3, 4, 8, 12, 15.
	518,918,400 cosets of size 20,160

Cosets solved since launch: 165,364,141
Average time per coset: 0:00:00.001

Server Status:
XV Puzzle Enumerator Server
Enumeration to depth: 23

Snapshot: Thursday, June 12, 2014 at 11:11:29 AM Central Daylight Time

 Depth             Reduced             Elements
   0                     1                    1 
   1                     3                    6 
   2                    11                   18 
   3                    29                   54 
   4                    87                  162 
   5                   253                  486 
   6                   752                1,457 
   7                 2,213                4,334 
   8                 6,379               12,568 
   9                18,205               36,046 
  10                51,785              102,801 
  11               145,489              289,534 
  12               405,728              808,623 
  13             1,118,586            2,231,878 
  14             3,043,537            6,076,994 
  15             8,153,139           16,288,752 
  16            21,464,200           42,897,301 
  17            55,475,870          110,898,278 
  18           140,272,410          280,452,246 
  19           346,202,190          692,243,746 
  20           831,610,844        1,662,949,961 
  21         1,938,788,875        3,877,105,392 
  22         4,370,165,315        8,739,560,829 
  23         9,490,811,983       18,980,345,944 

 Sum        17,207,737,884       34,412,307,411 

518,918,400 of 518,918,400 cosets solved

These results took about ten hours running on 12 cores spread over three computers. The program takes about 3.5 minutes to solve an average coset completely. This multiplies out to 1700 core-years to completely enumerate the states at depth for the puzzle, which is a bit disappointing.

In 2010 Bruce Norskog reported here that together with Morley Davidson of Kent State he had found that the diameter of the fifteen puzzle in the multi-tile metric is 43. He did not report any states at depth data, however. Perhaps the report of my humble efforts might prompt them to provide the full enumeration if it is available. I have checked my numbers out to depth 16 with a head on breadth first enumeration, so I am fairly confident in the above results. It would nice to have independent corroboration however.

» 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.

Confirmed the non-reduced counts

Submitted by stannic on Sat, 05/06/2017 - 20:52.
=================================================================
depth         states     cumulative        reduced     cumulative
-----------------------------------------------------------------
    0              1              1              1              1
    1              6              7              3              4
    2             18             25              9             13
    3             54             79             27             40
    4            162            241             81            121
    5            486            727            261            382
    6           1457           2184            731           1113
    7           4334           6518           2254           3367
    8          12568          19086           6306           9673
    9          36046          55132          18693          28366
   10         102801         157933          52002          80368
   11         289534         447467         149023         229391
   12         808623        1256090         409379         638770
   13        2231878        3487968        1143760        1782530
   14        6076994        9564962        3084890        4867420
   15       16288752       25853714        8324659       13192079
   16       42897301       68751015       21784945       34977024
   17      110898278      179649293       56551443       91528467
   18      280452246      460101539      142472925      234001392
   19      692243746     1152345285      352423791      586425183
   20     1662949961     2815295246      844516622     1430941805
   21     3877105392     6692400638     1970928257     3401870062
   22     8739560829    15431961467     4435822132     7837692194
   23    18980345944    34412307411     9636312082    17474004276
   24    39548054325    73960361736    20057689111    37531693387
=================================================================

Above are MTM counts to depth 24. With symmetry reduction, these took less than 100 CPU hours. Computing to depth 20 took about 1.5 hours. My reduced counts differ from yours since I defined 'cosets' by fixing only three tiles (the 'empty tile' and two physical tiles adjacent to it in the goal configuration; there are 3360 'cosets' each of size 13!/2). I can confirm the symmetry-reduced counts to depth 15 by modifying the program to use your definition of 'cosets'.

In STM, computing to depth 30 took slightly less than 1.5 hours and produced the expected non-reduced distribution.

-stannic

» login or register to post comments

partial confirmation...

Submitted by Bruce Norskog on Sat, 07/05/2014 - 20:39.

I can confirm the results in the "Elements" column up to depth 16 (42,897,301). However, the breadth-first search that we performed to find the diameter was not for MTM itself, but for a related metric I call "horizontal move metric" (HMM). HMM is like MTM, except only the horizontal moves are counted, not the vertical ones. Because an optimal MTM path always alternates horizontal and vertical moves, a position with distance 2n (n being an integer) in MTM will have a distance of n in HMM. A position at distance n in HMM, however, may have a distance of 2n-1, 2n, or 2n+1 in MTM. Hence, I don't believe that I can generate precise numbers for MTM knowing only the HMM numbers.

» login or register to post comments

Thanks

Submitted by B MacKenzie on Sun, 07/06/2014 - 07:27.

Bruce,

Thanks for the confirmation.

So, what you performed was a breadth first enumeration of the HMM. In this every horz. move generates four nodes, one terminal, when combined with a vert. move. The MTM antipodes were then found by optimally solving the HMM antipodes in the MTM. That's neat.

» login or register to post comments