Forth for Enlightenment, part seven of ten, Backwords 3

At this point, a diversion to playing the game is in order. If you examine the program, you might notice that when the program ends, it always says "You win!". You could quit before winning, but the game isn't that difficult. You always win. Compare that to a simple eye-hand coordination game like Tetris. There, you always lose. Always. With this positive reinforcement, one might expect that players would never stop playing.

There's a very simple algorithm for coming up with a solution to any problem. And, it turns out that 2 * n - 3 (on the HP-28, that's n 2 * 3 -) moves are required, as a maximum, and usually fewer. And when i learned this game so many ages ago, that's about all i knew about it. I had to figure out what the algorithm was. And it's pretty simple.

Note that if you get the last symbol, the "i" into the right most position, you should never have to move it again. So, if you build the string backwards one symbol at a time, you're done. What you do is search for "i", reverse it to the left most position. Then with "9", reverse it to the right most position. Then search for "h" and do the same. This seems to take two reverses per digit, so for a string with n symbols, you should have to perform 2 * n moves. But when you get to the first symbol, a in this case, it's already where you need it. So that's two moves you don't need, or 2 * n - 2. The remaining exercise is to figure out what other move you don't need. In any case, often, when you search for a symbol, it's already in the first position, so you don't need to get it there. Sometimes it's already in the position you need it to go to, so you save both moves. So the formula gets you a maximum number of moves. It may be fewer.

One might ask if there are optimum solutions that don't follow this algorithm. And there are. And in my opinion, that's where the real fun for this game lies. I've written optimal solution finders in C and Perl. And even the Perl version can find all optimal solutions for puzzles of length 9 in an hour on a modern computer. The C version can do it in under a second. How many puzzles of length 9 are there? Here's how to figure this out. If you're looking for a random puzzle, the first position can be any of 9 symbols. But having chosen one of these, there are only 8 symbols to choose from for the next symbol. So the first two symbols can be 9 * 8. Continue this way until the last symbol, from which there is only one left. The answer turns out to be 9! - that is 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362,880. I'd like to say that this was computed with my factorial program, but it had already been deleted. So the built in FACT function was used instead. Blame it on the low total memory area of the HP-28C.

Once one has an optimal solution generator, then one can compare the simply algorithm performance to the optimal solutions. In this table, Moves is that number of moves required. Optimal is the number of games with that many moves, and Auto is the number of games with that many moves using the simple algorithm. You can see that zero moves (starting with the solution) through two moves have the same number of games. That's because for those games, the optimal solution is the same as the easy solution. But there are no games where the optimal solutin requires more than ten moves. This table is for games of length nine.

Moves	Optimal	Auto
0	1	1
1	8	8
2	56	56
3	391	252
4	2278	980
5	10666	2968
6	38015	7798
7	93585	16836
8	132697	31396
9	79379	48636
10	5804	63868
11	0	68432
12	0	59233
13	0	39268
14	0	18108
15	0	5040

My evolution for puzzle solvers for this game over the years is interesting in it's own right. The first solvers were brute force with minor optimizations. They were written in C, but ran on machines that required hours of CPU time to solve a single puzzle. It would take years to generate all solutions of length 9. Modern computers are easily 10,000 times faster, so it would only be days now. But an idea came to me for solving all puzzles of length 9. One started with the solution. Each possible last move was generated, and that puzzle with the final solution move was recorded. Then, each of those puzzles was subjected to a single move as well. If the puzzle had already been recorded, the solution was ignored. Otherwise the puzzle and the move to get to a solved puzzle was recorded. This proceeded until all puzzles were recorded. In the early 1980's 362,880 puzzles would not fit into RAM except on large and expensive machines. For home machines the answers had to be stored on disk, and searched. By the late 1980's, everything could be kept in RAM even on home machines. But then my buddy Karl came up with an algorithm that could get an optimal solution to a single puzzle essentially instantly. It was so fast that it was quicker to generate puzzle solutions independently than all at once. And, no significant data needed to be stored. Further, with it's principals, one could solve any puzzle by hand, and quickly. Now that this has happened, i don't play the game very much. It's peculiar, but one of the goals of writting these puzzle solvers is to render the game less interesting. And this is done by attempting new techniques, and using the computer to prove that they are, in fact, essentially perfect. In this case, the computer didn't teach me the techniques, however. I have other, more complicated games, where the computer's brute force searching has lead to strategies that can be learned from study of the computer's play.