Appendix B: The Programs
Searching this space differs from more straightforward backtrack
problems such as the 8 Queens,
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
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.
- 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).
|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|
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.