The Checkerboard Puzzle

Table of Contents

  1. The puzzle - What this is about
  2. This document - Why I think it is a cool computer project
  3. Implementation - Too-brief description of objects. feel free to skip
  4. The action - Short snippet of code which does the work feel free to skip unless interested in code
  5. Seeing what happens - Step-by-step "thought process" to generate the solution. Take a look.
  6. Seeing what happens, in real time - Link to a cool movie

1 - The puzzle

My colleague Richard Kass posted the following challenge on his website:

Never being one to pass up $5.00, I thought I'd give it a try in summer 2007....

And here is the solution (white lines demark piece boundaries):

2 - This document

Now then, the point I'd like to discuss is not the solution itself, but how I obtained it. A non-technical friend correctly guessed: "You used a computer, that's all!" Well, yes, I used a computer. But, what does that mean? After all, one doesn't place a printout of the puzzle description into a scanner and press "GO." How does one make a computer solve a puzzle such as this one?

As a 40-something physicist who grew up programming in procedural languages such as FORTRAN, I was one of those "self-taught" programmers who, together with collaborators in large experiments, generated towering monsters of code that would teeter just at the edge of non-maintainability and inflexibility. Then came along object-oriented practices and languages like C++, and things changed quickly. Despite the initial protests of us old-timers, the improvements have been immense and the art of programming has gained a new elegance and power.

My younger colleagues live and breathe this new world, and smile indulgently at my less graceful moves. I'm sure this discussion will give them more cause to smile-- I can already see some degree of clunkiness in my implementation-- but still I had such fun solving this puzzle, and believe it instructive in some aspects of OO coding, that I thought it was worth writing up.

This document is in no way any kind of complete discussion, and if you don't know OO coding or C++ you might get little out of sections 3 and 4. (And if you know a lot about those things, you might get little more out of it than a smile.) But it has a nice movie at the end, so keep reading.

3 - Implementation - feel free to skip if not interested in this

All code may be found here

The idea is to solve the puzzle more or less the way a human would, though keeping strictly systematic, and of course with no intuitive leaps which make "by-hand" puzzle-solving so fun.

As with any C++ code, most of the focus is on the classes of objects. We have four classes:

  1. A Space is a square. Spaces are the building blocks of the Pieces and the Board

  2. A Board is simply an 8x8 array of Spaces.

  3. A Piece is made up of some number (~ 6) of Spaces. To solve Richard's puzzle, we instantiate 12 different Pieces and play with them.

  4. The last class of objects is the Move. When we solve a puzzle, we make (instantiate) Moves, we retry (reconfigure) Moves, and we undo (delete) Moves, just as in "real life."

4 - Action - feel free to skip if not interested in this

As often with C++ codes, most of the work goes into the classes themselves, and the "procedural" part is pretty small. It is sometimes amazing that the process of trying something, moving forward, backing up, reconfiguring, undoing, etc, in a recursive way is so relatively small, and that's even with all of my superfluous "cout" statements. Probably my students could make it even tighter.

Here is the relevant snip from SolvePuzzle.c. 

  vector TheMoves;
  Move* FirstMove = new Move(AllPieces,
			     TheBoard.NextAvailableBlackSpace().Column(),
			     TheBoard.NextAvailableBlackSpace().Row());
  TheMoves.push_back(FirstMove);

  int NumConfigsLookedAt=0;
  int NumSuccessMoves=0;
  while (TheMoves.size() < AllPieces.size()+1){
    NumConfigsLookedAt++;
    cout << "Number of moves made is " << TheMoves.size() << endl;
    Move* CurrentMove = TheMoves[TheMoves.size()-1];
    if (CurrentMove->Attempt(&TheBoard) == 0){             // 0 return value means successful attempt
      NumSuccessMoves++;
      cout << "  Move worked -- ";
      if (TheMoves.size()==12){
	cout << " and that's it!!\n";
	break;
      }
      else
	{
	cout << " make the next move " << endl;
	}
      Move* NextMove = new Move(AllPieces,
			   TheBoard.NextAvailableBlackSpace().Column(),
			   TheBoard.NextAvailableBlackSpace().Row());
      TheMoves.push_back(NextMove);
    }
    else{
      cout << "  Move failed -- delete it " << endl;
      delete CurrentMove;
      TheMoves.pop_back();
    }
    assert(TheMoves.size());    // essentially demanding that at least ONE move must be working !!!
  }

  //  done !!

5 - Seeing what happens

For reference, here are the 12 pieces. Refer to this page for more about visualization and the Pieces.

Note that Pieces 4 and 12 are identical to each other, as per the puzzle specification.


1
2
3
4
5
6
7
8
9
10
11
12

What we see below are the first Moves in the solution procedure. Note that only "successful" Moves are shown. (I.e. not ones which immediately produce orphans, or overlap Pieces or stick off Board's edge.) As you see, we work from lower-left corner of Board.

1: Move 1 instantiated P. 1 is placed in lower left space. This is the only rotational orientation which works for P. 1.
2: Move 2 instantiated P. 2 (in the only orientation which works) takes the next open spot.
3: Move 3 instantiated P. 6 next (note that pieces 3,4,5 couldn't fit).
4: Move 4 instantiated P. 4 (P. 3 didn't work)
5: Move 4 modified. Hey!! Isn't this just a repeat of the previous frame? No!- see note.
6: Move 4 modified. P. 4 is discarded, and pieces 5, 7, 8, 9 didn't work. So P. 10 is next.
7: Move 4 modified. All attemtps to continue fail. So P. 10 is discarded. P. 11 doesn't work, so go with P. 12. (See note)

8: Move 4 modified. P. 12, but rotated. (See note)
9: All possibilities exhausted, so Move 4 deleted, and Move 3 modiified: P. 7 replaces P. 6. (See note)
10: Move 4 instantiated P. 4
11: Move 5 instantiated P. 10.
12: Move 5 deleted, and Move 4 modiified: P. 4 rotated (See note)
13: See if you can fill in the narrative from here...!
14:

15:
16:
17:
18:
19:
20:
21:
notes
Notes on Frame 5 (and 7 and 8):

So why do Frames 4 and 5 look the same? Didn't anything happen? Well, actually a lot happenned, but they were all "unsuccessful" Moves, for which I don't show frames.

In particular, each of the eight Pieces (3, 5, 7, 8, 9, 10, 11, 12) not already on the Board were tried-- put in all rotational and translational configurations-- to take the next available place, and all these attempted Moves failed.

Try it for yourself! Imagine taking Pieces 3, 5, 7, 8, 9, 10, 11, and 12, and making one of them the next Piece on the Board. You rotate or anything you want. The machine actually tried a lot between Frames 4 and 5!

OK, so all those things failed. Still, why does frame 5 look like frame 4? Here's the answer: they are not the same, not really! Since the configuration in frame 4 leads only to failure (no next Move is successful), that Move was altered. In particular, Piece 4 was rotated and re-placed on the Board. However, you can see that for this Piece, rotating by 180 degrees just gives the same shape.

Notes on Frames 7 and 8:

So why do Frames 7 and 8 repeat Frame 4 again? This is just because Piece 12 is just the same shape as Piece 4. (Don't ask me, I didn't define the puzzle.)

Notes on Frames 9 and 10:

A Move is deleted in Frame 9: This is important. It is the first time that there are fewer Pieces on the Board than in the previous Frame. The Move first instantiated on Frame 4, has failed. All configurations led to a dead end. Thus, the only thing to do is to modify the previous Move, the one which was instantiated in Frame 3. The modification is that Piece 7 replaces 6.

Note that to do this, the Move first instantiated on Frame 4 had to be completely "undone" (the object was deleted), and a brand-new one created (instantiated). This is much more than a "modification" of the Move. Although I label both of them as "move 4," the Move instantiated on Frame 10 is entirely different than that instantiated on Frame 4. For example, one from Frame 4 could play with the following Pieces still available: 3,4,5,7,8,9,10,11,12. The one from Frame 10 has 3,4,5,6,8,9,10,11,12. Also, in principle, the "next available black space" that they are trying to fill could be different, even though in this case they are not.

6 - Seeing what happens, in real time (movie)

OK, well it turns out that it takes 7550 Frames to tell the whole story, and that's best done in a movie, so click here to see that. You might want to hit "reload" when you get there, to start the movie (just an animated gif) at the beginning.

Click to see the movie
lisa@mps.ohio-state.edu