Appendix B: The Programs

Searching this space differs from more straightforward backtrack problems such as the 8 Queens, Pentominoes, or Squarematch, which can use depth-first recursive algorithms.

To determine a shortest path here, a breadth-first search is needed. All the length n paths must be enumerated before going to length n+1, because a state that would be reached on click n+1 (or later) might also be reached on click n elsewhere in the tree. Furthermore, a depth first search might reach all the states (unlikely, but possible) without backtracking, where obviously some states would have shorter paths than those.

This implies storing data for all paths simultaneously, which is possible for the 6561 states of the 4×2, but less practical on a home PC for the 531,441 states of the 4×3, let alone the more than 43 million of the 4×4.

In addition, the no-double click rule means that part of a state description is how you got there. It is not sufficient to merely record that a state has been reached. Since it is, in general, possible to enter any state by clicking any square (except those that are blue, which are just one-third of the total), information must be kept for states × squares.

For each possible state, I kept

The square which was first clicked to reach this state. (3-4 bits/1 byte)
The predecessor state of each square clicked to reach this state. (13, 20, or 26 bits (2, 3,or 4 bytes) for 8, 12, or 16 squares, representing states in base 3 .)
The level at which each square was clicked to enter this state.(3-4 bits/1 byte)

Together with the breadth-first requirement, this makes the memory usage of the algorithm very high, and represents a major impediment to investigation of larger boards.

Squares	Bytes/state	States	Total Memory
8	1+(2+1)×8	6561	0.2 MB
12	1+(3+1)×12	531,441	26 MB
16	1+(4+1)×16	43,046,721	3483 MB

Of course, with each row of four squares multiplying the number of states by 81, the time element grows rapidly as well. On my 1999-era Celeron with 64MB running Windows 98, it takes about 200 ms to fully search a 4×2 board from one starting state. The total for either the Unrestricted or Hybrid methods to search all 3321 unique states is about 11 minutes. Adding another row would increase this to about 15 hours (× 2), which is available, using night time hours and such, but when I made an attempt at 4×3 (and did find some all-white solutions), I could not go past 6 clicks before running into memory problems. That would make the time much longer, if it worked at all.

The keeping of the predecessor state is only needed for reconstructing and displaying paths, so could be foregone, and some of the other data could be packed (at the expense of time). Furthermore, I used Java; a more barebones environment would use less memory (or make more available to the application) and be faster. Still, the 4×4 may require several applications of Moore's Law before it can be attacked.