The 8-puzzle

I have just received a communication from someone (unknown to me) via LinkedIn, asking about a computer program that I wrote (and continually revised) throughout the 1980s that solved the '8-puzzle'. I replied that I would have to get into my time machine and set it to return 34 years, but first I'll retrieve whatever shreds of memory I can find for the blog.

I came across this puzzle in a book written by David Levy; looking at the list of publications on his wiki page, this was probably 'Computer Gamesmanship: Elements of Intelligent Game Design' , published in the early 80s. One has to remember that I first 'met' a computer at the end of 1982: this was a teletype connected to a phone line that was connected to a PDP-11 computer about 20 miles away. I also had absolutely no background in programming, so this book talked about topics that were far above my ability. The 8-puzzle problem served as an introduction to all kinds of topics in computer science: how to draw a grid on a VT-100 screen, how to get direct input, how to check for legal moves, linked lists, hash tables ... there's a lot in there.

Looking for the 8-puzzle on the Internet now, I see that it's a favourite topic of computer science degree courses, which makes sense. I think that this site gives a good introduction to what the 8-puzzle is, who developed it (I remember it as a plastic toy from my childhood) and how to solve it with the computer. Note that this assignment is numbered COS 226 that probably means that this is an intermediate course in computer science. This site gives another good explanation of the puzzle and how to solve it.

I wish I had access to these web pages back in the day instead of having to stumble in the dark, teaching myself all kinds of techniques. All I had were a few pages in Levy's book and another book about data structures in Pascal, instead of detailed guides.

My program had two modes: user and computer. First the computer would create a random initial configuration, then the user would be given the opportunity to solve the problem, whilst the computer counted how many moves the user required. For my program, this mode taught me about user interface: how to react to user input and how to change the display depending on the input. 

But it was the second mode that was the more interesting: 'teaching' the computer how to solve the puzzle. Levy wrote about the 'minimax' algorithm, but it wasn't until one day I was in the computer science library of Bar Ilan university that I found out what this was. I imagine that I was doing some reserve army service in the lab at Tel Hashomer hospital, as the university was within walking distance (don't forget that I was/am a good walker; this was probably 2 km away). I acted like I had the right to access books and journals, and no one asked me who I was.

Every few months I would have a new idea as to how I could improve the evaluation function of the current configuration (basically, how far the current configuration is from the goal) in order to figure out what the next move should be. I also stored the various configurations for two reasons: I wanted to prevent the computer getting into a loop, and I wanted to look at the configurations myself to see how I would have acted. I remember now that I had a standard configuration that took me something like 37 moves to solve; any program version that took more moves needed to be improved. I also wanted to surprise myself and see whether the computer could solve this test configuration in fewer moves; after all, I'm no expert in this puzzle, and so it would be quite possible that the computer could beat me.

On the left is a picture of the solved 8-puzzle, or as we would call it in computing terms, the goal configuration. I note one major difference from this configuration and my goal configuration (that presumably came from the Levy book): mine had the empty space in the middle, so that the second row would be '4/ /5' and the third row would be '6/7/8'. This may seem like a minor point but it's very important.

Looking at the program code that has been stored here (I wonder how; did I give permission for this?), I am sad to say that although there are comments, they rarely state anything that is not obvious. There is certainly no explanation about the algorithm or how the evaluation function works. 

What Levy called IIRC the move generator (i.e. which tile should be moved next) appears to be implemented in the function makenode. Going back to the first picture of a real 8-puzzle, there are only two moves possible in this configuration: either the 1-tile would be moved down or the 5-tile be moved left. I would think that this latter move would be better then the 5-tile would be in the correct column but in the wrong row. Moving the 1-tile wouldn't appear to do much. But that's why the program has its evaluation function in order to calculate which move is better.

function evaluate (var p:square): integer;
  var
   i, tmp: integer;
   ch: char;
   blank: boolean;
 
  begin
   tmp:= 0;
   i:= 0;
   while i < 9 do
    begin
     i:= i + 1;
     ch:= p[i];
     blank:= ch = ' ';
     if not blank
      then tmp:= tmp + table[(i-1)*9 + ord(ch) - zero]
      else tmp:= tmp + table[i*9];
 
     if blank
      then if i <> 5 then tmp:= tmp + 2
                     else
      else
       case i of
         5:;
         2,4,6,8:
          if p[5] <> ' '
           then if (p[preint[i]] <> prech[ch])
                   and (ch <> prech[p[5]])
                   then tmp:= tmp + 5
                   else
          else
           if p[preint[i]] <> prech[ch]
            then tmp:= tmp + 5;
         1,3,7,9:
          if p[preint[i]] <> prech[ch]
           then tmp:= tmp + 3
       end
    end;
   evaluate:= tmp
 end { evaluate };
 

The above is not spaghetti code: it's actually presented in quite a logical format, but there's no explanation. Earlier in the table there are definitions of tables used in this function, but these definitions are opaque: I don't remember why certain values were chosen or what they do. The name 'prech' implies to me that there function checked which tile preceeded which; apparently this was an effective approach.