One-dimensional Checkers

Stu posted a seemingly simple puzzle on his blog the other day, along with a challenge to write a program to solve it. It looked like a simple puzzle, so it should be a matter of minutes to whip out a C program to solve it. Well, here it is, three days later and I finally have something to report. Here's the original description of the problem:

Make a line of 7 places, fill the left 3 with red pieces, the right 3 with white pieces and leave the centre place empty. The aim is to interchange the red and white pieces. A piece may move into the adjacent empty place or hop over a piece of the opposing colour to land in the empty place. Hopped pieces stay on the board. Winner is whoever takes the LEAST number of moves to do this. How many do YOU need?

Simple enough, so I wrote a program to solve it and it didn't work. What's the deal here? So I sat down with some coins and solved it by hand and realized, oh, you can't solve it without making backwards moves. Hmmph. The instructions don't specifically prohibit backwards moves, but the game is called CHECKERS, and backwards moves aren't allowed until you get a king, and you are not going to get a king here because there are no enemy checkers to crown you with since they never come off the board.

Okay, we'll expand the program to allow backwards moves, and it immediately runs out of stack space. Bah. What's going on? Oh. If you allow pieces to move backwards, you can reverse your last move so you end up where you started. If you don't keep track of where you've been, you can spend your whole life moving one piece back and forth between the same two spots. As my program uses recursion (the main subroutine calls itself for every move), we quickly ran off the end the world.

Fine. We'll keep track of all the moves we've made. Then whenever we consider a new move, we check all our previous moves to see if we've been there before. If we have, we disallow that move and look for another possibility.

This version blows up too. Working the puzzle by hand it seems like it only takes dozen moves to solve it. I've given my program room to store 100 moves. I thought that would be enough. Guess I was wrong. Fine. Bump it up to 1000 and try again. This time it works, though it takes 102 moves, many of which led to dead ends. But it does solve the puzzle.

So far I've been using a simplistic, brute force approach. We try all possible moves, one at a time. For each move, we then try to solve the new arrangement. If that path doesn't pan out, we try the next move, and so on. In this version of the program, I treated red and white markers equally. I gave no preference to one direction or the other.

Now the question is: can I reduce the number of moves required to solve the puzzle? How about if we reorder our possible moves to give preferential treatment to moves that go in the right direction? Bingo! Now we are down to 27 moves. There were 7 additional moves that led nowhere and were discarded. Solving it by hand takes 19 moves, so we aren't doing too bad.

The computer solution requires several backwards moves, but no backwards jumps, so I went in and modified the code to disallow the backwards jumps. The solution came out the same, but one of the dead end moves was eliminated.

I don't know how much more work it would take to enable the program to come up with an optimum solution. One way would be to use brute force: explore all possible solutions and keep the one with the fewest number of moves. A better method would somehow have to look at the board as a whole and determine which of the possible moves would be the best. I don't have an algorithm for that yet.

Source code for the final solution here. The getchar() at the end of the program allows you to run the program from Windows and see the results in the DOS box before the program terminates and the DOS box vanishes.

Update September 2016 replaced missing picture.