Some mathematical and algorithmic results on a simple puzzle game

I once came across this simple puzzle, or game.

You have a board of 7 squares in a single row, three black, and three red pieces. At the initialization of the game, the three black pieces are placed on the first (leftmost) three squares, and the three red pieces on the last (rightmost) three squares. This leaves one square in the middle.

The aim is to get all the red pieces onto the left side, and the black pieces on the right side, or in other words to reverse the position of all the pieces. This is done by executing a sequence of two possible moves:

One, a piece may move onto an empty square adjacent to it.

Two, a piece may hop over a piece of the opposite color adjacent to it, provided that the square on the other side of the second piece is empty.

Furthermore a move may only bring a piece closer to its destination; that is, it is not allowed to backtrack.

This particular instance of the problem (of three pieces each and seven squares) can be completed in 15 moves:

While this sequence completes the puzzle in 15 moves, it is not so obvious that this is the shortest sequence, that there is no shorter sequence that completes the puzzle in fewer than 15 moves. It is possible to prove a generalized result mathematically.

A formula for the number of moves

Let us generalize the game. We define an n-game to be an instance of the puzzle, with n pieces of each color separated by an empty square. For an n-game, the board contains squares.

Proposition: to complete an n-game, exactly moves are required.

In order for the n black pieces to completely trade places with the n red pieces, each black piece must hop over, or be hopped over by n red pieces.

Consider the pieces to be paired up as follows:

In the sequence of the game, each piece trades places with its partner. (Note that this is correct because the order of pieces of the same color cannot change).

It can be seen that the relative displacement between two members of a pair is . This is because each piece travels squares to get to its destination. In other words a piece travels squares relative to its partner.

A move by either member of a pair adds a relative displacement of 1, while a hop adds a relative displacement of 2.

We have already shown that each pair must have, between them, n hops. This is equivalent to a relative displacement of 2n. Two additional moves are required to bring the relative displacement up to . Therefore, moves are required for a pair to exchange places.

As there are n pairs in the game, the total number of moves required to complete the game is , as desired.

Implementation of a solver

Using the technique of a recursive depth-first search, it is a fairly easy programming exercise to write a solver for this puzzle. The solver produces the actual sequence of moves to complete an n-game.

The source code, in C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Number of tokens on each side
#define N 3

// Destination board
char endbd[2*N+1];

// Board representation
char bd[2*N+1];

// Moves found
char **mvs;

// Flag to indicate if recursion has finished
char cont = 1;

// Perform dfs given n byte array
void dfs(int nmvs){
    int i, l;
    char* tm = malloc(20);

    // Found, dump move list
    if(!memcmp(bd,endbd,N+1)){
        for(i=0;i<nmvs;i++) printf("%d. %s\n",i+1,mvs[i]);
        cont = 0;
    }

    if(!cont) return;

    // Check for 1-moves
    for(i=0;i<2*N;i++){
        if(bd[i]!=1) continue;

        // Try moving a square
        if(bd[i+1]==0){

            // Generate notation for piece move
            l=sprintf(tm,"%d -> %d",i+1,i+2);

            // Copy to move list
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);

            // Continue search
            bd[i]=0;
            bd[i+1]=1;
            dfs(nmvs+1);

            // Reset to previous state
            bd[i]=1;
            bd[i+1]=0;
        }

        // Try hopping
        if(i<2*N-1 && bd[i+1]==2 && bd[i+2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i+3);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i+2]=1;
            dfs(nmvs+1);
            bd[i]=1;
            bd[i+2]=0;
        }
    }

    // Check for 2-moves
    for(i=1;i<2*N+1;i++){
        if(bd[i]!=2) continue;
        if(bd[i-1]==0){
            l=sprintf(tm,"%d -> %d",i+1,i);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-1]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-1]=0;
        }
        if(i>1 && bd[i-1]==1 && bd[i-2]==0){
            l=sprintf(tm,"%d -> %d",i+1,i-1);
            mvs[nmvs]=malloc(l+1);
            strcpy(mvs[nmvs],tm);
            bd[i]=0;
            bd[i-2]=2;
            dfs(nmvs+1);
            bd[i]=2;
            bd[i-2]=0;
        }
    }
}

int main(){

    // Board representation. 1's move right, 2's move left.
    // Initialize board here.
    int i;
    for(i=0;i<N;i++){
        bd[i]=1;
        endbd[i]=2;
    }
    bd[++i]=0;
    endbd[i]=0;
    for(;i<2*N+1;i++){
        bd[i]=2;
        endbd[i]=1;
    }

    mvs = malloc(1000*sizeof(char*));
    dfs(0);
    return 0;
}

For instance, the sequence of moves for :

1. 3 -> 4
2. 5 -> 3
3. 6 -> 5
4. 4 -> 6
5. 2 -> 4
6. 1 -> 2
7. 3 -> 1
8. 5 -> 3
9. 7 -> 5
10. 6 -> 7
11. 4 -> 6
12. 2 -> 4
13. 3 -> 2
14. 5 -> 3
15. 4 -> 5