### Archive

Posts Tagged ‘draught’

## Draught board puzzle / checkerboard puzzle solver in Python

The checkerboard puzzle or draught board puzzle (also called Krazee Checkerboard Puzzle, Banzee Island checkerboard puzzle, Zebas puzzle, etc.) is a mutilated chessboard problem, which further is a tiling puzzle/dissection puzzle. Hence, the core problem is similar to the one of solving the well known Tangram, which some of you might be familiar with. The checkerboard puzzle we are looking at in this post is a 8×8 chess board imitation with black and white fields. It is split into 12 stones (left figure). The puzzle goal is to obtain at least one valid solution (right figure) – which is done by our solver. Although we are discussion this specific 8×8 board, the solver is designed to work with any board size (even with unequal width and height).

## Checkerboard puzzle representation

The stones the board consists of are stated in a text file, which the solver loads at the start. In the text file, stones are represented as an 2D array:

• B represents a black field
• W represents a white field
• _ represents an “empty” field (the stone does not cover that field)
• === represents separator between stones
```B,_,_
W,B,W
_,_,B
============
W,B,W,B
_,W,_,_
============
_,W,B,_
W,B,W,B
_,W,B,_
============
B,W,_,_
_,B,W,B
============
B,W,B,W
W,_,_,_
============
W,B,W,B
B,_,_,_
============
B,W
_,B
_,W
============
W,B,W
B,W,_
W,_,_
============
B,W,B,W
_,B,_,_
============
W,B,_,_
_,W,B,W
============
B,W,B,W
_,B,W,_
============
B,_,_
W,B,W
_,_,B
============
```

Within the solver, stones are represented as an 2D array as well:

• -1 represents a black field
• 1 represent a white field
• 0 represents an empty (not covered) field

As each stone can be rotated and flipped (“mirrored”), that stone can be put to the board in one of at maximum 8 versions (which we call “rotations” from now on). When loading stones, the solver generates and stores all different rotations for each stone for speedup.

The gameboard is represented as an 2D array as well:

• -1 is a black field, hence to fill with the black part of a stone
• 1 is a white white, hence needs a white part of a stone

This representation gives us the advantage of putting stones to the board fast (and checking, if that is possible in the first place). To check if a stone can be put to a specific xy-position on the board, we use a pointwise array sum. Putting a black part of a stone to a black field on the board results in a sum of -2, putting a white one to a white field results in 2. Instead, putting a black one to a white field or a white one to a black field results in a sum of 0. If a stone does not cover a certain field, the sum will be -1 or 1 (depending on if the field on the board is black or white). Hence, when checking if a stone can be placed on the board, -2 and 2 as well as -1 and 1 are valid sums, while 0 is an invalid sum.

We also have to account for other stones already placed on the board. When we put a stone to the board we change newly covered black fields to -10 and newly covered white fields to 10. This way we ensure that putting a stone ontop another one results in different sums. We consequently have to extend valid sums to also include -10 and 10, and invalid sums -11, 11, -9, 9 (would be the result of trying to put a stone ontop another).

## Solving the checkerboard puzzle

As we want to obtain all possible solutions our solver is designed as depth first search with branch cutting and limited successor generation. If a solution is found it gets appended to a solution file – and the search goes on. The search terminates if we have checked all possible states. We further do some inter-state caching of data for speedup.

### Successor generation

We do not generate all possible successors, but only those of placing a single stones to the field, in all rotations and to all possible positions. This avoids arriving at same successor states by putting stone A and B in different order, hence reduces branching. Consequently, we have to decide on the one stone to put to the board. Imagine that for one stone there is only one placement possibility left on the board. A human player would always put that stone to the board immediately – which is a good idea, as it further reduces branching. Our search does the same by always putting the stone to the board with least placement possibilities left.

### Branch cutting

We do branch cutting using a validity check. A failed validity check indicates that a board cannot yield a valid solution any more, hence it gets excluded from further search (which means none of it successors get generated or looked at, which cuts the complete branch). This check is the main cause for decreasing the branching factor – hence it’s OK if a noteworthy part of computations is done for it (anyway the implementation is done in a way that the validity check itself is quick). The validity check ensures:

• Each not yet placed stone must have at least one position on the board left where it could be placed
• Each field must have at least one stone that could still cover that field (based on stone placements still possible with the board)

### Caching for speedup

Naturally, each board contains information about:

• Which stones have been placed where so far (as array for faster access to the board, as well as list of placed stones, their rotation and position)
• Which stones are left to be placed

• For all stones left to be placed on the board: where they could possibly be placed
• For all yet empty fields on the board: all stones left to be placed that could possibly fill this field

For the latter two, all posibilities are generated at the game start. Afterwards, it is only necessary to update them, depending on which stones are put where to the board.

## Implementation

The implementation source code is available in this repository: https://github.com/pirius/draught-board-puzzle-aka-checkerboard-puzzle-solver

When called on our sample board, the solver finds multiple solutions for our 8×8 board, e.g. the following one:

```===================================
|  7B 11W 11B 11W  2B  3W  3B  5W |
|  7W 11B  2W  2B  2W  3B  5W  5B |
|  7B  7W  2B 10W  3B  3W  5B  5W |
|  4W  7B  6W 10B  1W  1B  1W  5B |
|  4B  6W  6B 10W 10B  1W  1B  8W |
|  4W  4B  6W 10B  0W  0B  1W  8B |
|  9B  4W  6B  0W  0B  0W  0B  8W |
|  9W  9B  9W  9B  0W  0B  8W  8B |
===================================
```

### Findings

It’s not easy to estimate the branching factor for this checkerboard puzzle. Depending on which stone is chosen to be the one to place on the board, the initial branching can range up to above 300 possibilities (8×8 field and 2×3 stone). Which each successive stone, the branching factor gets smaller, as less possibilities to place stones remain. For an 8×8 board, without immediately excluding successors eliminated by the branch cutting validity check, the measured average approximation of the branching factor is in the range of 6.5. This includes all stones placed to the board within search as well as invalid successor states, which would be removed by validity checks immediately. If excluding successors failing validity checks, the measured average approximation of the branching factor is reduced to about 1.2 – which is a huge gain (hence, the validity check is really worth its time).