15 puzzle solver: Difference between revisions
Content added Content deleted
Line 243:
There is a straightforward method for dealing with problems of this sort, the Red Tide. Imagine a maze and pouring red-dyed water into the "entry" - eventually, red water issues forth from the exit, or, back pressure will indicate that there is no such path. In other words, from the starting position find all possible positions that can be reached in one step, then from those positions, all possible positions that can be reached in one step from them, and so on. Eventually, either the stopping position will be reached, or, there will be no more new (still dry) positions to inspect. What is needed is some way of recording whether a position has been marked red or not, and an arrangement for identifying positions that are on the leading edge of the tide as it spreads. Keeping as well some sort of information identifying the path followed by each droplet, so that when a droplet spreads to the end position, its path from the source can be listed.
One could imagine an array FROM whose value for a given position identifies the position from which a step was taken to reach it. The value could be a number identifying that position or be a (sixteen element) list of the placement of the tiles possibly encoded into one number. An index for FROM would span the values zero to fifteen, and there would be sixteen dimensions... Alternatively, an array MOVE would record the move that led to its element's positiion: four possibilities would require just two bits for each element. But 16<sup>16</sup> is about 10<sup)20</sup> Avogadro's constant is 6.0221415x10<sup>23</sup> Oh well.
Since there are only 16! possible board layouts, only about a millionth of the array would be in use (16!/16**16 = 0.0000011342267) which is rather a stiff price to pay for a convenient relationship between a board layout and the corresponding location in the array. Actually, calculating a sixteen-dimensional location in an array is not so trivial and earlier compilers would not allow so many dimensions anyway. An alternative calculation might serve. This is the method of "hash tables", whereby, given a key (here, the values of the tiles in the sixteen places of the board), calculate a number, H, by some expedient and use that to index into a table. Entries are added sequentially to the table of positions but the hash number for a position is arbitrary so an array is used: INDEX(H) for the first position stored is one, and for the second position with its value of H, INDEX(H) is two, and so on, Two different positions may well yield the same hash number in a variant of the "birthday paradox", so the value of INDEX(H) is really a pointer to the start of a linked-list of table entries for different positions that all have the same hash number. The length of such chains is expected to be short because the hash number selects within a large INDEX array. Searching should be swift as for a given position, either INDEX(H) will be zero (meaning that the position is unknown), or, there will be one or two entries to probe to see if their position matches.
Because a board position involves sixteen numbers, each in the range of zero to fifteen, it is irresistable to have the board layout described by <code>INTEGER*1 BOARD(16)</code> since eight-bit integers can be defined, though not four-bit integers, alas. Further, an EQUIVALENCE statement can make this storage area the same place that an array <code>INTEGER*4 BORED(4)</code> occupies: no data transfer operations are needed for four 32-bit integers to hold the contenet of sixteen 8-bit integers. Next, the calculations <code>BRD(1) = BORED(1)*16 + BORED(2)</code> and <code>BRD(2) = BORED(3)*16 + BORED(4)</code> will squeeze two four-bit fields into one eight-bit pair, and moreover, do so four pairs at a time in parallel. Thus, array BRD in two 32-bit integers describes a position. A 64-bit integer could be involved instead of two 32-bit integers, but the hash calculation uses BRD(1)*BRD(2) to encourage a good mix. In ''The Art of Computer Programming'', Prof. Knuth advises that the wild hash number be reduced to the range 0:M - 1 by taking the remainder, modulo M, where M is a (large) prime number. The index array then is a fixed size, <code>INDEX(0:M - 1)</code> The output shows these calculations for two entries; notably the ordering of the bytes is peculiar, this being a "little-endian" cpu.
Accordingly, a table entry is defined by <code>TYPE AREC</code> with a NEXT (to link to the next table entry in a chain) and a BRD array to describe the board layout the entry is for. The payload for this problem consists of a PREV which identifies the entry from which this position was reached, and MOVE which identifies the move that had been made to do so.
The initial idea was to work from the given starting position, ascertaining all positions that could be reached in one step, then from each of those the positions reachable by a second step, and so on, until the "solved" state is reached. This is somewhat like the "all possible paths" of Quantum Electrodynamics when considering photon paths. Necessarily, on contact the linked-list of PREV entries will be a minimum-length path. Loops are precluded by passing over any candidate new position that has already been reached and so already has an entry in the table. In some games, loops are not possible, or are truncated by a special rule as in chess, when on the third attainment of a position a draw is declared. Then a remark in the Phix solution prompted the realisation that the flow could start from the "solved" position and stop on attainment of the specified position; the linked list via PREV could be reported in reverse order to go from the specified position back to the solved position. Some games are not symmetrical, as in chess where a pawn can only advance, but in this game, a move from A to B is just as allowable as a move from B to A - indeed, when checking the moves from a position, the reverse of the move that led to that position is skipped - it would just lead to a position that is already in the table and so be passed over. Similarly, the table does not record the possible moves from a position (there being two, three or four of them) but only the one move that led to the position. While there might be two, three, or four such moves possibe, only one is recorded, the one that got there first.
Starting a Red Tide from the "solved" or ZERO position has the advantage that if the table is retained, a new run for a different start position would take advantage of the previous effort. A table based around moves from one start position would be of little use when given a different start position.
Alas, the Red Tide ran into too much dry sand. A sixteen-dimensional volume has a ''lot'' of space in which it can possess a surface. The revised plan was to spread a Red Tide from the ZERO position and at the same time spread a Blue Tide from the specified start position, hoping that they would meet rather sooner. In ''Numerical Methods that Work (Usually)'', F. S. Acton remarks upon "Perverse Formulations", such as "... who insists on solving a boundary-value problem in ordinary differential equations via initial-value techniques may get away with it for a while, but ..." One can easily imagine pouring red paint onto the floor in one place, and blue paint in another place: most of the extension of the puddles is in directions that will not meet. With a single puddle, very little of the expansion is towards the target. Details are shown in the results.
Implementing this plan had its problems. Since the INDEX array is accessed randomly it should be in memory, but alas if it is large (and now there are two of them) the Compaq Visual Fortran 6.6 F90/95 compiler complains "total image size exceeds max (268435456): image may not run" - but if it is not so large, when many entries are made the hash separation will be heavily overloaded and the chains of entries with equal hash codes will not be short. One could possibly mess about with allocatable arrays as a different storage scheme is used for them, but instead, a disc file for the index array as well as a stash file for the entries. This also would mean that the stash and its index could survive for another run, otherwise if the index data were in memory only, some scheme would be needed to save the index, or to redevelop the index from the stash file on a restart. Both the stash and index files require random access, but the stash file grows sequentially. The index file however has to start full-sized, with all values zero. The obvious ploy of writing zero values to the file as a sequential file works well enough, but on re-opening the index file for random access, there are complaints about accessing a non-existing record. By initialising the file via random access, writing a zero to record one, two, three, etc. sequentially, no such complaint appeared and everything worked. But the initialisation was ''very'' slow, taking many minutes. Oddly, writing a zero to the ''last'' record without doing anything to intervening records not only worked but did so rapidly. It appeared that the intervening records were not prepared by the I/O subsystem at all, as very little I/O action took place. At a guess, only if a filesystem's allocation block was written to was that block made into a proper file piece with all zero values.
During these developments, a mistype produced an odd result. With F90, many array operations became possible, and accidentally, I typed <code>WRITE (WRK,REC = array) ''etc''</code> but omitted to specifying which element of the array was to be used. A positive interpretation of this construction would be to hope that the I/O list (the ''etc'') would be written to multiple records of I/O unit WRK, to array(1), array(2), and so on without re-evaluation of the I/O list. Alas, a file containing 19MB of zeroes resulted. Obviously some mistake. Similarly, one could hope that <code>WRITE (OUT,66) stuff</code> where OUT(1) = 6 (for standard output), and OUT(2) = 10 (a disc file, logging what has been written) would save on repeating WRITE statements, but alas, compatibility with older Fortran requires that such a statement places its output into the storage occupied by array OUT. This might be avoided by a variant form, <code>WRITE (UNIT = OUT,66) stuff</code> to signify that I/O unit numbers are being given, but alas, the compiler doesn't agree.
A great deal of computer effort could be avoided if the search could be given good guidance. For instance, a function that for any given position, gives the minimum number of moves needed to reach the ZERO position from it. Thus, from the start position, evaluate the function for each of the positions that can be reached via the available moves (at most, four), and select that one with the smallest value; repeat until at ZERO. Such a function certainly exists, though our ingenuity may not bring it forth. Perhaps some thought may do so. Perhaps not any time soon. But in any case, there is a definite procedure for generating such a function, and it is simple. Analyse all the board positions (they are finite in number) as in the Red Tide process, for each entry retaining the number of moves needed to reach that position from ZERO. Clearly, this is computable by a Turing Machine and so the function is computable, and so exists.
Such a guide function is rather like a "distance" function, so along these lines, when a minimum-step move sequence is found, the distances of each position from ZERO are calculated by various distance functions and the results shown in the output. Notably, function ZDIST calculates an encodement of the board position by referring to the layout of the ZERO position. It relies on the first square of a position having sixteen possible values, then the second square has fifteen and so on down; the number of possible layouts is 16! rather than 16**16. Given the list of values of the squares in the ZERO sequence, values that have been taken are marked off (in array AVAIL) and the count of possibilities remaining as each square is identified reduces. The ZDIST number is like an encodement of an integer from its digits, but with a successively-reducing base.
As an experiment, when the Red Tide procedd was poured to completion for a board of three rows and four columns, every position in the stash was presented to ZDIST and the result written out. Again, the filesystem presented difficulties: reading the stash file as a sequential file failed! So, a slog through reading specified record numbers, one after the other, taking half an hour. The head and tail values are 0, 105, 1, 328449, 609, 632, 4, 3271809, 3312009, ... 287247191, 446727869, 287039663. That last is entry 23950800 which is 12!/2: every possible attainable position has been tested and stored in the stash (once each), since a parity condition means that half the layout combinations have one parity and half the other, the possible moves being unable to change the parity. Alas, the ZDIST figures do not show anything so simple as odd/even for this. Every value should be unique, but in the past it has suspiciously often been easy to find a proof of a desired situation, so a test: sort the values and check. UltraEdit ran for a long time, then reported that there was insufficient memory to maintain an "undo" list. Very well. And then it wiped the file! Fortunately, the stash was still intact. On restarting in Linux the "sort" utility was available, and after some impressive running of all six cpus at 100% in cyclic bursts, I was looking at a file in a mad order: 0, 1, 10, 100, 1000, 10000, ... Apparently some sort of "word" order. As usual, the "man" information was brief and vague, but option "g" for "general number" looked likely, and so in sorted order: 0, 1, 4, 8, 9, 11, 12, 13, ... 479001589, 479001590, 479001593, 479001594, 479001597, 479001598. And 12! = 479001600. All values were unique.
The ZDIST function would be a candidate for a hash function, as it looks to give a good spray. But it requires rather more computation. It is always possible to calculate a "perfect" hash function, one that not only gives a distinct integer value for every possible key but also produces no gaps, so if there are N keys, there are N hash values in the range 1:N (or 0:N - 1) and the mapping is one to one. There even exist "hyper perfect" hash functions, that possess useful ordering properties: an example is the conversion of dates to a day number, which is one-to-one, without gaps, and ordered by date. However, the calculation of such perfection may be lengthy, so a fast hash is preferable, except for special cases.
In the event, when running, TaskInfo showed that almost all of the time was spent in the filesystem's I/O procedures, no "user time" was visible. The hash was fast, but the I/O was slow. Probably because the disc file was scattered in blocks across the disc device (actually a solid-state drive) and finding the appropriate block took a lot of messing about. In the past, a large disc file would be in one or very few pieces on the actual disc, with a straightforward direct calculation between a record number and disc's corresponding cylinder, surface, track and sector. These days, the operating system uses "spare" memory to hold the content of recently-used disc blocks, but alas, each index file is 781MB, and the stash files are over 3,000MB. Some systems have many gigabytes of memory, but this one has 4GB.
===The Code===
Line 835 ⟶ 861:
===The Results===
The step sequence is shown along with a board layout, followed by various methods of calculating a position's distance from ZERO, the solved state. All are such that Dist(ZERO) = 0, but, they do not show an obvious direction to follow. Some steps along the path to ZERO raise the distance to ZERO.
====Specified Problem====
<pre>
To play 'slide-square' with 4 rows and 4 columns.
Line 1,047 ⟶ 1,074:
</pre>
====Another Example====
Taking the first example from [[15_puzzle_solver/20_Random]] shows that with the red tide expansion in hand, only the new blue tide is poured into the maze:
<pre>
Line 1,304 ⟶ 1,332:
45 moves: RDDLULDRURDLLLUURRULLDRDLURRDRULURDLDLDRULULU
</pre>
The first and second move sequences start the same, until position 314204 (the sixteenth move) and then advance D to 612120 or U to 612122. In the first case the Euclidean distance falls while the encoded distance rises but in the second case the Euclidean distance rises while the encoded distance falls. If there might be any guidance to be found in these figures, it is not immediately obvious. But, after an increase, the next step achieves a large reduction, beyond the previous distance. Humm.
====Maximum Separation====
Just how far away can a position be from ZERO? Alas, 16! is rather large, but lesser board sizes can be perused to completion in a reasonable time. Changing the values in <code>NR</code> and <code>NC</code> is easy, though some other changes are helpful. The hash calculation that is nicely balanced for the 4x4 board doesn't give good spray for a lesser board, but an ad-hoc change to <code>BRD(1)*9 + BRD(2)</code> works well enough. The blue tide is plugged by suppressing its code, and the red tide flows until it can flow no more. For these runs, the output is slightly edited to omit redundant information such as that referring to the blue tide which isn't flowing.
<pre>
To play 'slide-square' with 3 rows and 4 columns.
Tide Red
Preparing a stash in file SlideSolveR3C4.123456789AB0.dat
... with an index in file SlideSolveR3C4.123456789AB0.ndx
199999991 zero values for an empty index.
1 2 3 4 5 6 7 8 9 A B 0 is the board layout in INTEGER*1
4030201 8070605 B0A09 0 is the board layout in INTEGER*4
48372615 B0A090 ..interleaved into two INTEGER*4
8AA0F74D combined.
-1969162419 as a decimal integer.
ABS(MOD(-1969162419,199999991)) + 2 = 169162502 is the record number for the first index entry.
| Tidewrack Boundary Positions| Positions | Primary Probes Index Use |Memory of Time Passed
Surge| First Last Count| Checked Deja vu%| Made Max.L Avg.L| Used% Load%| CPU Clock
1| 1 1 1| 2 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:57:19.187am.
2| 2 3 2| 4 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.1secs 16.62% 7:57:19.281am.
3| 4 7 4| 9 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:57:19.296am.
4| 8 16 9| 20 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 7:57:19.312am.
5| 17 36 20| 37 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 7:57:19.312am.
6| 37 73 37| 64 1.56| 1 1 1.000| 0.000 0.000| 0.0secs 0.2secs 0.00% 7:57:19.468am.
7| 74 136 63| 125 2.40| 3 1 1.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:57:19.515am.
8| 137 258 122| 241 3.73| 9 1 1.000| 0.000 0.000| 0.0secs 0.1secs 0.00% 7:57:19.609am.
9| 259 490 232| 451 4.43| 20 1 1.000| 0.000 0.000| 0.0secs 0.1secs 0.00% 7:57:19.671am.
10| 491 921 431| 827 5.56| 46 1 1.000| 0.001 0.001| 0.0secs 0.1secs 0.00% 7:57:19.796am.
11| 922 1702 781| 1481 6.01| 89 1 1.000| 0.002 0.002| 0.0secs 0.2secs 15.32% 7:57:20.000am.
12| 1703 3094 1392| 2671 6.63| 177 1 1.000| 0.003 0.003| 0.0secs 0.4secs 8.33% 7:57:20.375am.
13| 3095 5588 2494| 4770 6.88| 328 1 1.000| 0.005 0.005| 0.1secs 1.0secs 11.12% 7:57:21.359am.
14| 5589 10030 4442| 8502 7.62| 652 1 1.000| 0.009 0.009| 0.4secs 1.8secs 21.06% 7:57:23.140am.
15| 10031 17884 7854| 15135 8.17| 1237 2 1.001| 0.016 0.016| 0.6secs 2.8secs 22.90% 7:57:25.937am.
16| 17885 31783 13899| 26554 8.81| 2351 1 1.000| 0.028 0.028| 0.9secs 5.0secs 17.65% 7:57:30.984am.
17| 31784 55998 24215| 46180 9.48| 4409 2 1.000| 0.049 0.049| 1.9secs 7.4secs 26.21% 7:57:38.375am.
18| 55999 97800 41802| 79668 10.67| 8584 2 1.000| 0.084 0.084| 3.1secs 11.7secs 26.87% 7:57:50.062am.
19| 97801 168967 71167| 135867 11.76| 16270 3 1.001| 0.144 0.144| 5.1secs 15.7secs 32.40% 7:58:05.734am.
20| 168968 288855 119888| 228379 13.14| 30689 2 1.001| 0.243 0.244| 9.4secs 21.4secs 43.75% 7:58:27.125am.
21| 288856 487218 198363| 377240 14.32| 55757 2 1.002| 0.404 0.405| 15.0secs 26.5secs 56.39% 7:58:53.671am.
22| 487219 810424 323206| 612123 15.74| 100162 2 1.002| 0.660 0.663| 21.7secs 42.4secs 51.16% 7:59:36.093am.
23| 810425 1326202 515778| 977833 17.06| 176608 3 1.003| 1.060 1.069| 32.7secs 59.2secs 55.29% 8:00:35.296am.
24| 1326203 2137202 811000| 1533678 18.63| 306896 3 1.005| 1.674 1.693| 56.0secs 91.9secs 60.91% 8:02:07.203am.
25| 2137203 3385213 1248011| 2358532 20.07| 522581 4 1.008| 2.592 2.635| 85.7secs 2.1mins 67.00% 8:04:15.062am.
26| 3385214 5270492 1885279| 3554164 21.71| 877235 4 1.012| 3.930 4.026| 2.1mins 3.4mins 60.44% 8:07:40.187am.
27| 5270493 8052888 2782396| 5239108 23.47| 1452058 5 1.017| 5.824 6.031| 3.1mins 4.4mins 70.93% 8:12:05.062am.
28| 8052889 12062610 4009722| 7534021 25.39| 2357673 5 1.025| 8.412 8.842| 4.4mins 6.8mins 64.81% 8:18:50.843am.
29| 12062611 17683964 5621354| 10540894 27.45| 3736777 5 1.037| 11.814 12.666| 5.9mins 8.7mins 67.49% 8:27:35.375am.
30| 17683965 25331836 7647872| 14308274 29.65| 5757092 5 1.052| 16.090 17.699| 8.1mins 12.1mins 66.43% 8:39:42.640am.
31| 25331837 35397636 10065800| 18773730 32.03| 8547647 6 1.072| 21.203 24.079| 10.4mins 14.8mins 70.68% 8:54:28.562am.
32| 35397637 48158049 12760413| 23759506 34.47| 12146155 7 1.097| 27.009 31.864| 13.2mins 19.0mins 69.20% 9:13:31.234am.
33| 48158050 63728835 15570786| 28870409 37.06| 16437759 8 1.126| 33.226 40.950| 15.7mins 21.8mins 72.16% 9:35:16.421am.
34| 63728836 81900441 18171606| 33626342 39.63| 20990966 9 1.157| 39.543 51.100| 18.8mins 31.2mins 60.26% 10:06:28.671am.
35| 81900442 102200317 20299876| 37402396 42.28| 25357818 9 1.193| 45.566 61.894| 21.7mins 43.3mins 50.19% 10:49:46.296am.
36| 102200318 123787565 21587248| 39666978 44.94| 28674025 11 1.222| 51.062 72.814| 24.1mins 55.6mins 43.32% 11:45:22.359am.
37| 123787566 145628724 21841159| 39956652 47.68| 30596301 10 1.253| 55.742 83.268| 24.9mins 62.8mins 39.61% 12:48:08.968pm.
38| 145628725 166535629 20906905| 38122360 50.42| 30382490 10 1.269| 59.612 92.717| 24.8mins 65.3mins 37.94% 1:53:27.953pm.
39| 166535630 185434986 18899357| 34311262 53.20| 28383116 11 1.286| 62.576 100.747| 22.4mins 61.1mins 36.70% 2:54:31.156pm.
40| 185434987 201493321 16058335| 29019233 55.99| 24579603 12 1.283| 64.796 107.133| 19.0mins 52.2mins 36.48% 3:46:40.171pm.
41| 201493322 214265924 12772603| 23016150 58.66| 19948189 10 1.281| 66.330 111.891| 14.8mins 40.7mins 36.41% 4:27:20.140pm.
42| 214265925 223781141 9515217| 17041788 61.37| 14979073 11 1.262| 67.361 115.182| 10.9mins 29.0mins 37.55% 4:56:23.062pm.
43| 223781142 230364322 6583181| 11772739 63.96| 10506946 10 1.249| 67.994 117.304| 7.0mins 19.0mins 37.17% 5:15:21.000pm.
44| 230364323 234607075 4242753| 7532690 66.76| 6789748 11 1.222| 68.366 118.555| 4.3mins 11.3mins 37.93% 5:26:38.500pm.
45| 234607076 237110948 2503873| 4439978 69.59| 4054719 10 1.206| 68.558 119.231| 2.3mins 6.1mins 37.47% 5:32:47.218pm.
46| 237110949 238461216 1350268| 2371273 72.87| 2185279 10 1.176| 68.651 119.552| 70.6secs 2.9mins 39.92% 5:35:44.015pm.
47| 238461217 239104461 643245| 1130010 76.08| 1055623 10 1.160| 68.689 119.687| 29.4secs 74.9secs 39.21% 5:36:58.890pm.
48| 239104462 239374764 270303| 466424 80.21| 440280 10 1.125| 68.702 119.734| 10.8secs 26.0secs 41.36% 5:37:24.921pm.
49| 239374765 239467075 92311| 161691 83.23| 154374 8 1.111| 68.705 119.747| 3.4secs 7.6secs 45.08% 5:37:32.546pm.
50| 239467076 239494191 27116| 44973 88.02| 43422 11 1.071| 68.706 119.750| 0.8secs 1.5secs 56.82% 5:37:34.031pm.
51| 239494192 239499581 5390| 9553 88.33| 9259 6 1.074| 68.706 119.750| 0.1secs 0.4secs 33.32% 5:37:34.453pm.
52| 239499582 239500696 1115| 1625 94.71| 1593 5 1.028| 68.706 119.750| 0.0secs 0.0secs104.17% 5:37:34.468pm.
53| 239500697 239500782 86| 167 89.22| 162 3 1.049| 68.706 119.750| 0.0secs 0.0secs 97.66% 5:37:34.484pm.
54| 239500783 239500800 18| 18 100.00| 18 1 1.000| 68.706 119.750| 0.0secs 0.0secs 5:37:34.484pm.
The boundary has not surged to new positions!
The now-static boundary has 18
Record Stash Move | Board layout | Max|d| Sum|d| Euclidean Encoded vs Zero
239500783 Red D |0869/B725/43A1| 7 44 14.765 466581807
239500784 Red D |0869/B7A1/4325| 9 58 18.601 466582214
239500785 Red R |8759/43A2/0B61| 9 48 16.310 302860487
239500786 Red R |4325/8761/0BA9| 9 38 15.362 127427903
239500787 Red R |0821/B3A5/4769| 9 48 15.811 464885186
239500788 Red D |0B21/3765/48A9| 9 38 14.765 475738105
239500789 Red R |4321/8B65/07A9| 9 42 15.362 127389739
239500790 Red D |0861/B325/47A9| 9 48 15.811 466336825
239500791 Red D |0829/B365/47A1| 6 36 12.410 465127617
239500792 Red R |0829/B7A5/4361| 7 44 14.765 465130767
239500793 Red R |4321/8769/0BA5| 9 30 11.832 127387607
239500794 Red R |B821/37A5/0469| 10 58 19.799 424935162
239500795 Red R |4361/8725/0BA9| 9 42 15.362 128113223
239500796 Red R |4321/B765/08A9| 9 40 15.297 127402699
239500797 Red U |8369/4725/0BA1| 9 38 14.283 288340727
239500798 Red U |8329/476A/0B51| 9 36 14.213 287247191
239500799 Red R |0321/8765/4BA9| 9 30 11.832 446727869
239500800 Red R |8321/4765/0BA9| 9 38 15.362 287039663
No progress!
</pre>
Whereas for four rows and three columns,
<pre>
To play 'slide-square' with 4 rows and 3 columns.
Tide Red
Preparing a stash in file SlideSolveR4C3.123456789AB0.dat
... with an index in file SlideSolveR4C3.123456789AB0.ndx
199999991 zero values for an empty index.
1 2 3 4 5 6 7 8 9 A B 0 is the board layout in INTEGER*1
4030201 8070605 B0A09 0 is the board layout in INTEGER*4
48372615 B0A090 ..interleaved into two INTEGER*4
8AA0F74D combined.
-1969162419 as a decimal integer.
ABS(MOD(-1969162419,199999991)) + 2 = 169162502 is the record number for the first index entry.
| Tidewrack Boundary Positions | Positions | Primary Probes Index Use |Memory of Time Passed
Surge| First Last Count| Checked Deja vu%| Made Max.L Avg.L| Used% Load%| CPU Clock
1| 1 1 1| 2 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:50:20.203pm.
2| 2 3 2| 4 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.1secs 12.50% 7:50:20.328pm.
3| 4 7 4| 9 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 7:50:20.328pm.
4| 8 16 9| 20 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:50:20.343pm.
5| 17 36 20| 37 0.00| 0 0 0.000| 0.000 0.000| 0.0secs 0.1secs 0.00% 7:50:20.421pm.
6| 37 73 37| 64 1.56| 1 1 1.000| 0.000 0.000| 0.0secs 0.0secs 0.00% 7:50:20.437pm.
7| 74 136 63| 125 2.40| 3 1 1.000| 0.000 0.000| 0.0secs 0.2secs 8.31% 7:50:20.625pm.
8| 137 258 122| 241 3.73| 9 1 1.000| 0.000 0.000| 0.0secs 0.1secs 50.40% 7:50:20.687pm.
9| 259 490 232| 451 4.43| 20 1 1.000| 0.000 0.000| 0.0secs 0.1secs 49.87% 7:50:20.781pm.
10| 491 921 431| 827 5.56| 46 1 1.000| 0.001 0.001| 0.1secs 0.2secs 63.59% 7:50:20.953pm.
11| 922 1702 781| 1481 6.01| 89 1 1.000| 0.002 0.002| 0.1secs 0.3secs 35.06% 7:50:21.265pm.
12| 1703 3094 1392| 2671 6.63| 177 1 1.000| 0.003 0.003| 0.2secs 0.6secs 41.63% 7:50:21.828pm.
13| 3095 5588 2494| 4770 6.88| 328 1 1.000| 0.005 0.005| 0.5secs 1.5secs 36.19% 7:50:23.296pm.
14| 5589 10030 4442| 8502 7.62| 648 1 1.000| 0.009 0.009| 0.8secs 2.2secs 34.50% 7:50:25.515pm.
15| 10031 17884 7854| 15135 8.17| 1237 1 1.000| 0.016 0.016| 1.3secs 3.9secs 33.60% 7:50:29.421pm.
16| 17885 31783 13899| 26554 8.81| 2344 1 1.000| 0.028 0.028| 2.2secs 5.9secs 36.77% 7:50:35.328pm.
17| 31784 55998 24215| 46180 9.48| 4397 1 1.000| 0.049 0.049| 3.1secs 9.5secs 32.73% 7:50:44.781pm.
18| 55999 97800 41802| 79668 10.67| 8574 2 1.000| 0.084 0.084| 6.0secs 14.5secs 41.25% 7:50:59.328pm.
19| 97801 168967 71167| 135867 11.76| 16154 2 1.000| 0.144 0.144| 9.3secs 20.5secs 45.46% 7:51:19.812pm.
20| 168968 288855 119888| 228379 13.14| 30520 2 1.000| 0.243 0.244| 14.7secs 27.9secs 52.72% 7:51:47.671pm.
21| 288856 487218 198363| 377240 14.32| 55395 2 1.001| 0.404 0.405| 18.5secs 33.0secs 56.18% 7:52:20.656pm.
22| 487219 810424 323206| 612123 15.74| 99611 2 1.002| 0.660 0.663| 22.4secs 41.7secs 53.62% 7:53:02.359pm.
23| 810425 1326202 515778| 977833 17.06| 175049 2 1.003| 1.062 1.069| 35.9secs 61.9secs 57.96% 7:54:04.250pm.
24| 1326203 2137202 811000| 1533678 18.63| 305322 3 1.004| 1.676 1.693| 55.4secs 94.5secs 58.68% 7:55:38.718pm.
25| 2137203 3385213 1248011| 2358532 20.07| 519257 4 1.007| 2.596 2.635| 87.8secs 2.3mins 63.69% 7:57:56.562pm.
26| 3385214 5270492 1885279| 3554164 21.71| 872963 3 1.010| 3.936 4.026| 2.2mins 3.4mins 63.19% 8:01:21.109pm.
27| 5270493 8052888 2782396| 5239108 23.47| 1445680 4 1.016| 5.833 6.031| 3.2mins 4.8mins 66.44% 8:06:08.906pm.
28| 8052889 12062610 4009722| 7534021 25.39| 2348797 4 1.024| 8.426 8.842| 4.5mins 6.9mins 65.49% 8:13:00.218pm.
29| 12062611 17683964 5621354| 10540894 27.45| 3734408 5 1.036| 11.829 12.666| 6.4mins 9.1mins 70.67% 8:22:04.328pm.
30| 17683965 25331836 7647872| 14308274 29.65| 5746564 5 1.051| 16.110 17.699| 8.3mins 12.3mins 67.88% 8:34:21.375pm.
31| 25331837 35397636 10065800| 18773730 32.03| 8552447 6 1.071| 21.220 24.079| 10.9mins 15.7mins 69.40% 8:50:02.062pm.
32| 35397637 48158049 12760413| 23759506 34.47| 12145305 7 1.096| 27.027 31.864| 13.8mins 19.5mins 70.96% 9:09:32.671pm.
33| 48158050 63728835 15570786| 28870409 37.06| 16448462 7 1.125| 33.238 40.950| 16.7mins 23.2mins 71.94% 9:32:46.109pm.
34| 63728836 81900441 18171606| 33626342 39.63| 21022994 9 1.158| 39.540 51.100| 20.1mins 32.4mins 62.17% 10:05:09.859pm.
35| 81900442 102200317 20299876| 37402396 42.28| 25358874 8 1.192| 45.562 61.894| 21.9mins 44.7mins 49.02% 10:49:50.296pm.
36| 102200318 123787565 21587248| 39666978 44.94| 28734429 10 1.224| 51.028 72.814| 25.6mins 56.6mins 45.33% 11:46:25.156pm.
37| 123787566 145628724 21841159| 39956652 47.68| 30572287 11 1.252| 55.720 83.268| 27.1mins 64.5mins 41.99% 0:50:52.171am.
38| 145628725 166535629 20906905| 38122360 50.42| 30446707 10 1.273| 59.558 92.717| 26.6mins 66.4mins 40.12% 1:57:16.468am.
39| 166535630 185434986 18899357| 34311262 53.20| 28341786 10 1.283| 62.543 100.747| 23.7mins 62.2mins 38.16% 2:59:28.250am.
40| 185434987 201493321 16058335| 29019233 55.99| 24605484 10 1.285| 64.750 107.133| 20.0mins 53.8mins 37.26% 3:53:15.640am.
41| 201493322 214265924 12772603| 23016150 58.66| 19903099 11 1.276| 66.306 111.891| 15.5mins 41.1mins 37.86% 4:34:19.671am.
42| 214265925 223781141 9515217| 17041788 61.37| 14979317 10 1.262| 67.337 115.182| 11.3mins 29.2mins 38.48% 5:03:33.937am.
43| 223781142 230364322 6583181| 11772739 63.96| 10478430 12 1.241| 67.985 117.304| 7.4mins 19.1mins 38.79% 5:22:39.250am.
44| 230364323 234607075 4242753| 7532690 66.76| 6785656 11 1.220| 68.358 118.555| 4.4mins 11.4mins 38.96% 5:34:04.359am.
45| 234607076 237110948 2503873| 4439978 69.59| 4041159 10 1.197| 68.558 119.231| 2.4mins 6.2mins 38.76% 5:40:15.031am.
46| 237110949 238461216 1350268| 2371273 72.87| 2182892 11 1.172| 68.652 119.552| 70.1secs 3.0mins 39.48% 5:43:12.625am.
47| 238461217 239104461 643245| 1130010 76.08| 1051526 10 1.149| 68.691 119.687| 30.2secs 76.2secs 39.66% 5:44:28.812am.
48| 239104462 239374764 270303| 466424 80.21| 439307 10 1.118| 68.705 119.734| 11.2secs 26.3secs 42.40% 5:44:55.125am.
49| 239374765 239467075 92311| 161691 83.23| 153927 9 1.102| 68.708 119.747| 3.6secs 7.9secs 45.63% 5:45:03.000am.
50| 239467076 239494191 27116| 44973 88.02| 43358 9 1.067| 68.709 119.750| 0.8secs 1.7secs 44.15% 5:45:04.734am.
51| 239494192 239499581 5390| 9553 88.33| 9231 6 1.062| 68.709 119.750| 0.1secs 0.3secs 52.87% 5:45:05.000am.
52| 239499582 239500696 1115| 1625 94.71| 1598 4 1.029| 68.709 119.750| 0.0secs 0.0secs100.81% 5:45:05.031am.
53| 239500697 239500782 86| 167 89.22| 161 3 1.043| 68.709 119.750| 0.0secs 0.0secs 5:45:05.031am.
54| 239500783 239500800 18| 18 100.00| 18 1 1.000| 68.709 119.750| 0.0secs 0.0secs 5:45:05.031am.
The boundary has not surged to new positions!
The now-static boundary has 18
Record Stash Move | Board layout | Max|d| Sum|d| Euclidean Encoded vs Zero
239500783 Red D |09A/B78/456/321| 9 52 17.720 471375815
239500784 Red L |A90/78B/456/123| 9 60 19.494 391824450
239500785 Red L |BA0/789/546/321| 10 56 18.974 435370175
239500786 Red D |BA0/789/452/361| 10 56 18.493 435370041
239500787 Red R |07A/98B/456/123| 9 56 18.221 464077890
239500788 Red R |09A/B87/465/321| 9 52 17.833 471380879
239500789 Red R |09A/B87/546/321| 9 52 17.833 471380975
239500790 Red R |09A/B87/564/312| 10 54 18.547 471380998
239500791 Red L |970/B8A/465/123| 9 60 19.287 344730714
239500792 Red L |AB0/789/546/123| 9 60 19.950 395453370
239500793 Red L |BA0/879/265/341| 10 56 18.601 435410157
239500794 Red R |09A/B78/546/123| 9 56 18.868 471375930
239500795 Red L |AB0/789/456/132| 9 58 19.339 395453251
239500796 Red R |09A/B78/465/123| 9 56 18.868 471375834
239500797 Red D |AB0/798/456/123| 9 60 19.950 395458290
239500798 Red L |AB0/789/456/213| 10 60 19.950 395453252
239500799 Red L |BA0/789/456/123| 10 60 19.950 435370050
239500800 Red R |0BA/789/456/123| 9 56 18.868 478915650
No progress!
</pre>
Reducing to a 3x3 board encouraged a reduction in the size of the index. The run took about ten seconds.
<pre>
To play 'slide-square' with 3 rows and 3 columns.
Tide Red
Preparing a stash in file SlideSolveR3C3.123456780.dat
... with an index in file SlideSolveR3C3.123456780.ndx
199991 zero values for an empty index.
1 2 3 4 5 6 7 8 0 is the board layout in INTEGER*1
4030201 8070605 0 0 is the board layout in INTEGER*4
48372615 0 ..interleaved into two INTEGER*4
89F056BD multiplied together in INTEGER*4
-1980737859 as a decimal integer.
ABS(MOD(-1980737859,199991)) + 2 = 26997 is the record number for the first index entry.
|Tidewrack Boundary Positions| Positions | Primary Probes Index Use
Surge| First Last Count|Checked Deja vu%| Made Max.L Avg.L| Used% Load%
1| 1 1 1| 2 0.00| 0 0 0.000| 0.002 0.002
2| 2 3 2| 4 0.00| 0 0 0.000| 0.004 0.004
3| 4 7 4| 8 0.00| 0 0 0.000| 0.008 0.008
4| 8 15 8| 16 0.00| 0 0 0.000| 0.016 0.016
5| 16 31 16| 20 0.00| 0 0 0.000| 0.026 0.026
6| 32 51 20| 40 2.50| 1 1 1.000| 0.045 0.045
7| 52 90 39| 65 4.62| 3 1 1.000| 0.076 0.076
8| 91 152 62| 124 6.45| 8 1 1.000| 0.134 0.134
9| 153 268 116| 164 7.32| 12 1 1.000| 0.210 0.210
10| 269 420 152| 304 5.92| 18 1 1.000| 0.353 0.353
11| 421 706 286| 430 7.91| 38 1 1.000| 0.549 0.551
12| 707 1102 396| 792 5.56| 53 1 1.000| 0.919 0.925
13| 1103 1850 748| 1114 8.08| 97 2 1.010| 1.427 1.437
14| 1851 2874 1024| 2048 7.57| 189 1 1.000| 2.357 2.384
15| 2875 4767 1893| 2799 10.25| 356 2 1.006| 3.578 3.640
16| 4768 7279 2512| 5024 10.73| 738 2 1.019| 5.721 5.882
17| 7280 11764 4485| 6599 14.56| 1365 2 1.023| 8.338 8.701
18| 11765 17402 5638| 11276 15.49| 2734 3 1.042| 12.610 13.466
19| 17403 26931 9529| 13867 21.55| 4630 3 1.054| 17.228 18.905
20| 26932 37809 10878| 21756 21.89| 8302 4 1.087| 23.956 27.402
21| 37810 54802 16993| 24289 29.56| 11793 4 1.102| 30.204 35.958
22| 54803 71912 17110| 34220 30.01| 18451 4 1.151| 38.089 47.934
23| 71913 95864 23952| 33912 40.36| 21895 6 1.165| 44.097 58.047
24| 95865 116088 20224| 40448 40.55| 27617 6 1.205| 50.513 70.071
25| 116089 140135 24047| 33131 52.98| 25580 7 1.200| 54.289 77.860
26| 140136 155713 15578| 31156 53.27| 24657 5 1.208| 57.539 85.140
27| 155714 170273 14560| 19530 67.88| 16842 6 1.157| 58.883 88.277
28| 170274 176547 6274| 12548 68.84| 10945 5 1.137| 59.684 90.233
29| 176548 180457 3910| 4926 84.57| 4615 6 1.068| 59.840 90.613
30| 180458 181217 760| 1520 85.46| 1424 4 1.064| 59.888 90.723
31| 181218 181438 221| 265 99.25| 264 1 1.000| 59.888 90.724
32| 181439 181440 2| 4 100.00| 4 1 1.000| 59.888 90.724
The boundary has not surged to new positions!
The now-static boundary has 2
Record Stash Move |Board plan| Max|d| Sum|d| Euclidean Encoded vs Zero
181439 Red D |647/850/321| 6 32 12.247 220175
181440 Red U |867/254/301| 8 32 13.038 311247
No progress!
</pre>
Thus, for a 3x3 board the greatest separation is thirty-two steps to two positions, while the 3x4 and 4x3 boards both have eighteen positions fifty-two steps away from ZERO.
=={{header|F_Sharp|F#}}==
| |||