[ Update: please visit http://www.benzedrine.ch/grid-puzzle.html
further information plus program source code available. ]
Solving Mikero's brainwrenching grid puzzle with a computer program
Daniel Hartmeier
June, 28th 2000
On Friday, June 23rd 2000, Mike Goldshteyn alias mikero challenged me
with a puzzle in IRC EFNET #c++. He has posted the puzzle to the USENET
newsgroup rec.puzzles (search for Subject: Mikero's brainwrenching
grid puzzle on www.deja.com/usenet/). For a complete description of
the puzzle, see http://www.wwa.com/~mikeg/rules.html
The problem looked fairly easy to me at first, and I began writing a
program that would solve any grid. Soon I had to realize that it isn't
as simple as it looks. The obvious approach of trying all possiblities
fails because of limited computing power and memory. A straight-
forward recursive search overflows the stack nearly immediately. Using
a custom stack does only put off that fate.
My first program kept a list of moves. I inserted every starting point
at the beginning. The program repeatedly took one move out of this list
and insert all moves that could possibly result from it (up to four).
If a move visited all points, I compared the score (which was summed
up during the path) with a current minimum. After all paths terminated,
the minimum would equal the perfect solution. I added checks to prune
senseless branches: where the sum was already larger than the current
minimum, or the program was looping between the same points (this isn't
trivial, since multiple visits to the same city are required sometimes),
etc. But how much I optimized this program, I could barely solve a
4x4 or even a 5x5 grid. Frustrated, I nearly gave up.
Watching the moves the program created, I realized that it took a large
time to just reach a single move that visited all points. Finding the
best one out of thousands takes forever if finding only one takes already
half an hour. This gave me the idea for the following program, which
finds the perfect solution for 6x6 grids within minutes on a humble
PII-233.
For the first part, forget about cities, moves and paths. Let's look
only at bridges.
1) Definition of spanning tree
I call a set of bridges in a grid that connect all cities a spanning tree.
In an n*n grid, there are 2*n*(n-1) bridges in total, but only n*n-1
are needed to make a spanning tree. Without proof I'll assume that the
perfect solution will be a spanning tree with exactly n*n-1 bridges.
2) Bits representing spanning trees
In the case of an 8x8 grid, there are 112 bridges. A spanning tree
requires only 63 bridges. How can we easily generate all possible
spanning trees?
Imagine a data type of 112 bits. Create an arbitary start value that
has 63 bits set (and 49 not set). If you swap a one and a zero bit
in that value, you'll get another value with exactly 63 bits set.
From the starting value, you can reach any other value by repeatedly
swapping every combination of bits.
3) Detecting loops
Not every value with exactly 63 bits set is a spanning tree. Some
bridges can form a loop and result in unconnected cities. We therefore
need an algorithm that identifies spanning trees. I'm using a simple
maze algorithm: start in an arbitary city, facing an arbitary direction.
If possible, walk straight ahead. If that's not possible, turn left,
right or back (in that order). After a number of steps, you'll end up
in the starting city, looking in the starting direction. If you have
visited all cities during your journey, you have a spanning tree.
4) Generating all possible spanning trees
We could generate all possible values in ascending order by swapping
ones only with more significant zeros (starting with the lowest
possible value). But since it isn't feasible to process all possible
spanning trees (there are far too many of them), I generate values
in non-sequential order and score them as I go. To prevent endless loops
(for instance swapping the same pair of bits again and again) and double
values, we can store the generated values in a container that contains
only unique entries.
5) Scoring a spanning tree
We can now generate all possible spanning trees, among which will be
the perfect solution with the minimal score. The following example is
a spanning tree for a 6x6 grid:
A--B--C--D E--F
| |
G--H--I J K--L
| | | | |
M N O--P Q R
| | |
S T--U V--W--X
| | | | |
Y Z a b--c d
| | | |
e--f g--h--i--j
How can we compute the minimal path of a single spanning tree?
Imagine that we have the following function:
take as argument a city and one of the bridges leading away from this
city. Return two values: the minimal score it takes to go over that
bridge and visit all cities on the other side of the bridge
a) without returning to the city where we left
b) returning to the city where we left
Without proof I'll assume that the perfect solution will start and end
in leaves (cities that are only connected to one bridge). Try to produce
an example that doesn't start or end in a leaf and can't be optimized by
starting and ending in a leaf instead. No such case exists. Or I'm wrong.
Now call the function I've defined above with a leaf (and its only bridge)
as argument. Result a) will be the minimal score that is possible when
starting from that leaf. Call the function for all leaves of the grid,
and the minimum of those return values will be the minimal score for the
spanning tree. Quite simple. But how do we implement such a function?
6) The score function
Using recursion, this function can be implemented pretty easily. As you
will see, the maximum recursion won't be deeper than n*n, so we won't
run out of stack.
If the town on the other side of the bridge we're crossing (let's call
it peer) is a leaf, the results are clear:
a) cost of bridge
b) cost of bridge * 2
If the peer is connected to exactly two bridges (including the one we're
coming from), we call the function recursively and return:
a) cost of bridge + a) returned by recursive call
b) cost of bridge * 2 + b) returned by recursive call
If the peer is connected to more than two bridges (let's call it branch),
the results are a little more complicated to calculate:
first, call the function recursively for all bridges of the branch
(except the one we're coming from), storing the results.
b) is easy: if we have to return back to the city we're coming from,
we have to return from all visits to peers. Therefore, we return
the sum of all b) returned by the recursive calls plus twice the
cost of the bridge we were just crossing.
a) If we don't need to return, we can terminate in any leaf we
like. We have to return from all but one visits. Since we want to
minimize our score, we choose the bridge to not return from so that:
b) of the city we don't return from + sum of a) of the other
cities is minimal.
We return this sum plus the cost of the bridge we were just crossing.
This function will indeed return the minimal score of a spanning tree
starting in a leaf. Calling it for all leaves gives us the minimal score
of the spanning tree. Now we can score all the spanning trees as we
generate them.
7) The priority queue
Assuming that relocating one bridge of a spanning tree will not completely
ruin its score, we can use a priority queue to focus on enhancing spanning
trees with good scores.
Instead of using a dumb list to store the spanning trees, we store them
sorted by score (lowest score first). We take the spanning tree from
the top, generate all spanning trees with one bridge difference (rejecting
loops and double entries), score them and insert them into the queue.
After an element has been handled, it is no longer needed, except for
preventing double entries. We change its score to a large value and
therefore move it to the end of the list. During the process, we keep
a copy of the element with the lowest score so far.
8) Results
I was amazed how quickly the program converges and finds very low
solutions. Even if it takes a long time (too long to be of practical
use) to find the global minimum for sure, it finds very low scores
within seconds even for 8x8 grids (possibly those are, in fact, the
global minima, but I can't be sure).
For instance, the following path represents a solution for Mike's
8x8 grid:
A--B--C D--E F--G--H
| | | | | |
I J K L--M N--O P
| | | | |
Q R--S--T U--V--W X
| |
Y--Z--a b--c--d--e f
| | | |
g h--i j k l--m n
| | | | | | |
o p q--r s--t--u v
| | | |
w x y--z--A B--C D
| | | | | |
E--F G--H--I--J K--L
Score : 263
Moves : 68
Path : EDLMUVWONFGHPXfnvDLKCBJIHGyzAskstutlmedcbjrqihpxFEwogYZaZRSTSKCBJBAIQ
Try to beat it. I'd be interested in any methods you apply to either
find lower scores faster or guarantee a global minimum within
reasonable time.
9) Source code
Right now, my C++ source code is an ugly hack. I'll rewrite the code
in compliance with some standards of profession and publish it here.
I'm also trying to improve the algorithms and data structures to
increase speed and decrease memory usage.
If you want to experiment with the current source, drop me a line
and I'll send you a copy. But you'll have to refrain from bitching
about missing const-correctness etc. in that version. ;-)
10) Conclusion
I'm aware that I have made some assumptions that I didn't prove
(my graph theory skills are sub-optimal). So, if you can prove any of
them wrong (one counter example is enough, of course) or even prove
one correct (which is harder), please let me know.
In my opinion, this is a very interesting puzzle, and I have learned
many things while writing this program. I'm sure I will find different
and better methods to solve it in the future.
I'd like to thank Mike for introducing me to the problem and for his
patient explanations. He is working on a program of his own, which
surpasses mine in many aspects. Visit his page (mentioned at the
beginning of this text) for more details.