Move the Checkers … Redux

This page is work in progress. Do not expect a complete experience.

This challenge assumes that you have already solved Move the Checkers and Move the Checkers … again. It is much harder and much more open ended than either of those challenges. We will be considering questions which, in my mind, arise naturally from thinking about the two challenges in comparison. These are questions that I did not myself know the answer to when starting to write this page so they are a reflection of my thought process. This doesn't mean that this is the one correct way to think about the two challenges or that there is only one correct answer to these questions. I encourage you to think about questions that have come to your own mind after solving the two challenges and use the ones below as a guideline only.

Compare the two challenges mentioned above. What similarities and differences come to mind? Do all of the differences actually change the nature of the challenge?

No matter your views on similarities and differences, we always have to consider that we are talking about two artificial and arbitrary challenges. There is no deeper reality to be discovered here. All we can hope to do is to train our ability to think precisely about the structures presented to us. The more precise we get, the more we will find that many details are left undefined in the riddle-like presentation and we will have to find suitable definitions for ourselves. First, a bit of nomenclature to make this easier: We will call the initial arrangement of checkers and empty space a starting position and the final arrangement a goal position. Intuitively there has to be a series of valid moves that leads from the starting position to a goal position. We might call this series of moves a solution. But what does this mean precisely? Let's explore systematically.

Often heard advice is to look at small examples to get a feeling for the structure of a problem. This is what we will do next. If you know how to program, this might be a good time to implement a solver for this little problem and experiment with it. In fact, some of the images you are about to see are generated (needlessly) dynamically in your browser by such a solver. The implementation will force you to make your assumptions about the nature of the problem explicit. Look up breadth-first search if you need help to get started.

The two versions of the challenge, as presented, involve six and eight checkers respectively and so we know that there are solutions for starting with six and eight checkers. You will find that a solution starting with four checkers is however not possible. How can we be sure of this?

We know that six and eight checkers are valid starting positions while four checkers are not. What about other numbers? What are the underlying rules of this? What makes a starting position valid?

You will notice that in the challenges with six and eight checkers, if the starting position starts with a black checker, the goal position starts with a white checker and vice-versa. You might already have explored this observation thinking about a previous question. Why does this happen?