solving the SHIFT puzzle

Introduction

The SHIFT puzzle is sometimes called the most difficult puzzle in the world.
Below are reduced pictures of the SHIFT puzzle in the initial- and in the final, solved, state.


initial state		solved state

The puzzle consists of a board with 10 blocks called A..I and X
The goal is to shift the blocks (which may not overlap) until the red X-block is in the center bottom position.
At first glance, this exercise looks impossible.

How to write a program that solves this puzzle?

The Brute Force method

In this approach simply all possible move sequences are tried until the solution is met.
(by accident we may say)
Programming is relatively simple, but for more difficult puzzles the processing time will be very long :
hours or even days.
The process time may be shortened by avoiding superfluous moves.
The brute force approach is a good general starting point to solve puzzles but
ways to speed up the process are puzzle dependent.
In this case of the SHIFT puzzle we expect many moves until the solution is met.
Also we note that the number of possible moves is limited as are the different board states
(the way the blocks occupy the board)
The first measure to limit processing time is establishing a maximal allowed number of moves.
If the last move is tried and there is no solution, this last move is taken back and the next sequential
move is tried.

Because no pieces (blocks) are removed by moves, the danger of repeating board states exists.
This situation is avoided by storing the board states in a buffer.
If a move produces a board state that is already present in the buffer, the move is skipped.
This is the second measure to limit processing time.

The third and last measure is to avoid blocks shifting "back and forth".
The board has 4 * 5 = 20 fields of which 18 are covered by blocks and 2 are not covered.
If a block moves, 1 or 2 covered fields become uncovered.
If a later move wants to move back a block to cover a field it had uncovered before, this move is skipped.
This is called the BAF (back & forth) test. A detailed description is given later in this article.

Coding the board, blocks and moves

Programming amounts to the definition of data structures and the design of procedures that manipulate the data.

Fields

Below is a picture of the board where each field is assigned a number.

The position of a block on the board is the number of the left-top field.
So, in the initial state, block X has position 1 and block I has position 19.

Block types

There are 4 different block types according to their width and height.
Following type definition defines a block type (programming language is Delphi)

type  Tblocktype = record
                    w,h : byte;  //width,height
                    footprint : DWORD;
                    color : DWORD;
                   end;

DWORD is the same as cardinal, a 32 bit unsigned integer.
Footprint is a DWORD where bit i is associated with field i of the board.
The bit is set (1) if covered and clear (0) if uncovered.

Following definition defines a block on the board

type TBlock = record
               bt  : byte;        //block type 1,2,3,4
               pos : byte;        //position 0..19
               text: char;        //character in block, A..I, X
              end;

Now, the board with all blocks is simple described in

type TGame = array[1..10] of TBlock;

Following constants fill in the data

const blocktype : array[1..4] of TBlockType =             //dim h x v
      ((w: 1; h: 1; footprint:  $1; color: $ff6000),      //1 x 1
       (w: 2; h: 1; footprint:  $3; color: $ff6000),      //2 x 1
       (w: 1; h: 2; footprint: $11; color: $ff6000),      //1 x 2
       (w: 2; h: 2; footprint: $33; color: $0000ff));     //2 x 2

      Game1 : TGame =
       ((bt: 3; pos:  0; text:'A'),               //postitions:
        (bt: 4; pos:  1; text:'X'),               //  0  1  2  3
        (bt: 3; pos:  3; text:'B'),               //  4  5  6  7
        (bt: 3; pos:  8; text:'C'),               //  8  9 10 11
        (bt: 2; pos:  9; text:'D'),               // 12 13 14 15
        (bt: 3; pos: 11; text:'E'),               // 16 17 18 19
        (bt: 1; pos: 13; text:'F'),
        (bt: 1; pos: 14; text:'G'),
        (bt: 1; pos: 16; text:'H'),
        (bt: 1; pos: 19; text:'I'));

Note, that the footprint is initially set with the block in the left-top position.

Moves

type Tmove = record           //for move list
              mblk : byte;    //number of block that moves
              mdir : byte;    //move direction 
              alldirs : byte; //all possible directions for block
             end;

The move directions are coded as below

1: right
2: up
4: left
8: down

"Alldirs" is the "or" of all move directions.
If a move has taken place, the bit that corresponds to the direction is cleared.

History buffers

These are the Backward- and the Forward buffer.
They hold previous board states and the purpose is to avoid repeating board states,
or, so to say, prevent moving in circles.
The backward buffer holds board states from previous lower moves.
After move n, the backward buffer holds the boardstates 1,2,.....,n.
So, the length of the backward buffer is always equal to the number of moves.

When we take back a move during the search process, the last entry in the backward buffer is lost.
However, we do not want this state to reoccur in future moves.
To remember this board state, it is entered in the Forward buffer, together with the move (sequence) number.
This requires some explanation.
Say, we allow the computer to find a solution in maximal 150 moves.
Somewhere in the search process after move 140 however no move is possible so this move is taken back
and the board state is copied to the forward buffer together with the move number 140.
If we encounter this board state later after move 142, we qualify this move as illegal.
However, if we had encounterd this board state in the forward buffer at move 130, it is very well possible
that a solution would be found in move 148, or so.
The entry only means, that from this board state no solution exists within 10 moves (150 - 140).

Only board states reoccurring at or after the recorded move number are illegal.

Coding the board state

There are 4 type of blocks.

An entry in the backward buffer has 4 DWORDS.
A DWORD holds the "or" of the footprints of a block type.
So, backward buffer[1,n] has a bit set if the corresponding field is occupied by a type 1 block after move n.

const absmaxmoveNr = 200;          //top entry in move list
...
type TBoardCode = array[1..4] of DWORD; //1: footprints of type 1 blocks..etc.
                                        //for history
...
var BWhistory : array[1..4,0..absmaxmoveNr] of DWORD;
    boardcode : TBoardCode;

"absmaxmoveNr" is the highest move possible.
"boardcode" holds the encoded board state:

The boardcode variable is set by procedure makeboardcode.

The forward buffer may grow very large, because it holds all the boardstates at which a move was taken back.
To compare a new trial move against such a big buffer is time consuming.
Therefore, the buffer is split in 4 groups.

const endFWHistory = 7500;        //top entry in history table per buffer 0..3  {maximal 30000 entries}
...
type TFWhistory = array[0..4,1..endFWhistory] of DWORD;
     PFWhistory = ^TFWhistory;
...
var FW0,FW1,FW2,FW3 : TFWhistory;
    FWtop : array[0..3] of WORD;  //holds pointer to FW0..FW3
...
const FWbuffer : array[0..3] of PFWhistory = (@FW0,@FW1,@FW2,@FW3);

Which forward buffer to use at a given board state?

function getFWbuffer : byte;    //return FWhistory index 0..3
var i,d : byte;
begin
 d := 0;
 for i := 7 to 10 do d := d xor blocks[i].pos;
 result := d and $3;
end;

The positions of blocks 7 .. 10 (the 1*1 blocks) are xored and the modulo 4 is taken.
This value [0..3] selects the forward buffer.

Note: the move number for entry n in forward buffer i is stored in FWi[0,n]

The BAF test

BAF stands for "Back And Forth".
See picture below, showing superfluous moves 1 and 3, undetected by the backward buffer check:

For each field (0..19) a stack of 50 bytes is created.
When a block moves, 1 or 2 fields become uncovered and in de stack of these fields we enter the block number (1..10).
If a block moves to a field it had previously uncoverd (the block number is the top of this stack) then the move is skipped as superfluous.

var BAF   : array[0..19,0..50] of byte; //back & forth check 20 stacks
    BAFh  : array[0..19] of byte;       //height per stack

There is a little 4th trick: the X block is not allowed to move upward.

the search process

A solution simply is a sequence of moves.
A move is defined by the block that is moving and the direction taken.
So, the block number and the direction together form a counter.
If we write (for the sake of this explanation) a move of block bnr in direction dir as [bnr,dir],
and counting sequentially :

[1,1], [1,2], [1,4], [1,8], [2,1], [2,2], [2,4], [2,8], [3,1],........,[10,8] note: remember that the directions are 1,2,4,8 for right, top, left, down.

xmove is the trial move. See flowchart below.
Yellow ellipses are labels.
Goto statements are necessary because of crossing loops in the search procedure.

This concludes the description of the SHIFT puzzle search.

For the details, please refer to the source code.

Press [here] to load the complete Delphi-7 project.

Press [here] to go to the SHIFT puzzle page.