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