Figure 1: Standard Checkmate problem.
While at a conference, I picked up a neat sliding-block puzzle with a chess theme. It's called Checkmate, © W. G. H. Strijbos, made by PUSSYCAT, Bad Salzuflen, Germany, and looks like a simple 4×4 chess position with an extra (empty) square. See Figure 1 (left).
Figure 1: Standard Checkmate problem.
The puzzle is to mate the black king, while playing only legal chess `slides'. Thus, the kings must never be adjacent, and the BK mustn't be on the same file as the WR unless it is shielded by the WK. You must finish with the squares properly black or white as appropriate.
It's easy to see that you must start with Ra0, and finish with Ra1, meanwhile solving an ordinary 14-15-type puzzle; so the final position must be WRa1, WKd3, BKd1, as in Figure 1 (right). That's straightforward, and the tiles are well made and slide smoothly, so let's ... oops ..., not so well made, the tile on c3 is a bit stiff, in fact I can't move it, and the tiles on c2 and d2 seem to be a bit tight as well. Aha! That's the point -- the black tile on c3 isn't meant to move, it's stuck down; and the tiles initially on c2 and d2 are stuck together, so can only move left or right (and as a pair). These restrictions make the solution quite tricky.
With the double tile on c2d2, both d3 and d1 are the ends of blind alleys, so no manoeuvring either into or out of them is possible. While it is on b2c2, there is a long necklace round from b4 to c4, then down the d-file, along the 1-rank and up to a2 and a3; it is possible to circulate tiles around this necklace, but the kings cannot legally turn the corners unless they are at least three tiles apart. Finally, while it is on a2b2, the board is effectively cut into two pieces joined by the necklace through the d4 corner, so that tiles are trapped in their part of the board. With the help of these observations, a solution can be found; but if you make a false move, it is quite tedious and frustrating either to get back on track or to unscramble back to the start position.
What I should have done was to write a proper C program (perhaps including a graphical interface for demonstration purposes) to solve or to unscramble any position. What I actually did was to write a suite of shell scripts. This is a form of masochism which will appeal to only a minority of readers; so the scripts and their rationale are relegated to an Appendix. However, there are some points of more general interest.
Every sliding-block puzzle corresponds to an undirected graph, in which the vertices represent configurations and the edges represent legal (single) slides between configurations. Usually, there is a distinguished Start configuration, and a set of Finish configurations; the task is to find a route, and if possible the shortest route, between Start and Finish. Often, there is only one Finish configuration, but puzzles are also common in which the task is more general (for example, to manoeuvre a specified tile to a specified place without regard for where the other tiles are).
This graph may be quite large (the 14-15 puzzle has 16! = 20922789888000 configurations, and would require 2436 gigabytes of uncompressed storage to maintain just one bit of information per node) but usually need not all be retained in memory. The shortest route from Start to Finish may be found by a breadth-first search, in which the nodes are partitioned into generations such that Generationn contains exactly those nodes that are distance n from Start. Thus Generation0 contains only Start, while Generationn+1 can be constructed by listing all nodes reachable in one move from those in Generationn and striking out those contained in earlier generations; the search can be stopped as soon as a generation contains one of the Finish nodes. It might be thought that the striking-out process would require consideration of all previous generations; but because the graph is undirected, any position that can be reached in one move from a node in Generationn must be at least n - 1 moves from Start, so the striking-out can only involve nodes found in Generationn and Generationn-1 and only these sets need be retained while Generationn+1 is under construction. In the solution described in the Appendix, the striking-out is effected by maintaining the generations in sorted order, after which a merging process can be used to determine which nodes are uniquely in the latest generation; alternatives are discussed later.
There is another simplification possible in this case. For Checkmate, the associated graph is bipartite; every move slides either the empty square by one or the double piece by one (and the empty square by two), so the positions of the double piece and the empty square suffice to determine whether an odd or an even number of moves has been made from Start. Thus, the graph has no odd cycles, and a node arising in Generationn+1 need not be compared with those in Generationn; it suffices to strike out those in Generationn-1. The 14-15 puzzle also has this `parity' property; the position of the empty square determines whether an odd or an even number of moves has been made. This is quite distinct from the well-known `reachability' property of the 14-15 puzzle; in that puzzle, only positions which differ from Start by an even permutation are reachable at all, whereas in Checkmate even and odd permutations are indistinguishable (essentially because two black or two white squares may be interchanged `invisibly'). There is much more about parity properties and the groups associated with sliding-block puzzles in Wilson (1974).
Of the 3×13×12 = 468 configurations of the kings and the double square, only 256 are legal (kings separated, and BK not exposed on the a-file). So the associated graph has 256×11!/5!5! = 709632 nodes, allowing for the empty space, the five ordinary white tiles and the five ordinary black tiles. Of the 256 legal king/double configurations, only 242 can be reached from the standard Start position; for example, you can't reach WKd1, BKd3 with the double tile on c2d2. Similarly, of the 256×11 = 2816 legal configurations of the kings, double and empty, only 2595 can be reached; for example, with WKa4, BKc4, and double a2b2, the empty cannot be on a3, b3 or b4. However, for each of these surviving configurations, any arrangement of the ordinary squares can be reached, so the part of the graph connected to Start contains 2595×10!/5!5! = 653940 nodes. The remaining 55692 nodes comprise a large number (several thousand) of disconnected components; counting exactly how many would be a singularly pointless exercise.
Solving the problem of Figure 1 takes 68 moves; there are five distinct minimal solutions, of which one is:
Ra0 Ka1 D L D Kb4 U U L U Kb1 D L D R U L L U R Kc1 R D L L U Kd1 D R D L Kb3 L L U U Kd2 R R R D D D L L L U Kd3 R Kb2 R U U L Kb1 L U R Kc1 R D L L U Kd1 R R Ra1where the king and rook moves are given explicitly, and D [L, U, R] means to slide an ordinary or double tile down [left, up, right] into the empty space.
Possibly surprisingly, this is one of the easier positions to reach; the largest generation, which contains 18729 nodes, is 74 moves from Start, and about two-thirds of all reachable positions are more remote then Finish. However, part of the reason for this ease is the fact that the board is properly chequered at both ends so that relatively little re-organisation of the ordinary tiles is necessary. The remotest positions, at up to 117 moves from Start, have the tiles arranged largely in colour blocks (compare Figure 2). Only a handful of properly-chequered positions (such as WKa4, BKc4) are further from Finish than is Start, and then by no more than four moves. Even 117 moves is by no means the maximum separation of positions in Checkmate; it takes 145 moves to solve the problem of Figure 2, where the empty square is marked by an open box, the fixed square by a filled box, and the double square by a dash. (This is probably, based on extensive computer searches from remote positions, the unique hardest problem in Checkmate; but it is just possible that a more distant pair have escaped detection.)
Figure 2: Hardest known problem in Checkmate.
Constructing the complete set of generations from any given Start position takes about 11 minutes on an SGI Indy workstation, using the scripts given in the Appendix. Most of this time is spent sorting, and most of the rest is spent in file-handling. A custom-written C program which used bit-vector techniques to maintain generations within memory would be an order of magnitude faster.
A similar approach is possible for many other sliding-block puzzle. Two of these in particular have been investigated, and are described below. The `bible' of such puzzles is Hordern (1986); of Hordern's 272 puzzles, over 150 should be solvable in practice using minor variations of the scripts given here, to judge from the table of results obtained by de Bakker and quoted in Singmaster (1995). Problems with more than a few million reachable nodes are too large to solve by this method using currently-available file storage; bit-maps could be used up to around 108 nodes (reachable or not); de Bakker reports failure on a 64M-byte workstation when the size of a generation reaches about 700000. Another reason for failure would be complexity of the edit scripts; problems with several empty spaces or with several non-convex pieces are very hard to describe using these techniques.
This is one of a number of puzzles played on a 5×4 arena using a 2×2 square, several 2×1 and 1×2 rectangles, and a number of 1×1 squares. It gets its name from a red donkey which is traditionally drawn on the 2×2 square, though my own copy has a sweet container which can only be opened by solving the puzzle [or by brute force!]. The usual puzzle is to manoeuvre the donkey from its starting position in the middle of the top row to the middle of the bottom row, but Hordern lists 35 minor variations (puzzles C15 to C45 in Hordern's classification).
The edit scripts for these puzzles are more complicated than for Checkmate, primarily because there are two empty squares, either or both of which can be used in a particular move. There is also an ambiguity in counting moves; if a 1×1 tile slides across both empty squares (either in a continuing direction or orthogonally), is that one move or two? But this ambiguity does not affect either the number of configurations or their reachability. However, only one of Hordern's variations (C22, which has distinctive tiles to be arranged in a specific pattern) has more than 175580 reachable configurations, and this smaller number of nodes and an accompanying greater length of solution (some over 300 moves) result in much smaller generations than for Checkmate, and faster computer solutions. A typical computer search takes under a minute on an SGI Indy using the techniques of the Appendix.
This puzzle is discussed extensively in Berlekamp (1982), pp. 769-777, where a complete graphical solution to the primary problem (Hordern's C27d) is presented.
This is a 3×4 puzzle. The rightmost column of three consists of a blank, a tile representing a goat, and another blank. The remaining 3×3 tiles comprise an empty square surrounded by an octangular `fence'. The puzzle is to swap the goat and the empty, to `capture' the goat. As commonly sold, this puzzle has therefore apparently 12! = 479001600 configurations, half (including the Finish configuration!) unreachable by the even/odd permutation rule. But the fence is symmetric, and opposite corners are identical; so the goat and the empty may be swapped by also swapping two opposite corners. This reduces the node count to 119750400, all connected; this is still too many for sensible solution, especially as the largest generations have several million nodes.
However, in the original problem, the top right fence corner and the adjacent blank are joined into a 1×2 rectangle, which therefore cannot be swapped to the bottom left corner. In this version, the top left and bottom right fence corners must be swapped, and there are 3×10!/2 = 5443200 nodes, all reachable, in the associated graph.
A breadth-first search of this graph turns out to be feasible. On an SGI Indy, the full search takes about two-and-a-half hours using scripts similar to those below. The minimal solution takes 28 moves (confirming a conjecture by Hordern); the remotest positions are 51 moves away from Start. The present author's search, originally made in 1992, and reported in Singmaster (1993), appears to have been the first successful attempt on this problem.
De Bakker (Singmaster, 1995) has systematically worked through Hordern's catalogue of sliding-block puzzles, solving those which have standard pieces and conditions and which have few enough configurations (and small enough generations) for computer solution. The remaining standard problems, including the 14-15 puzzle itself, seem to have far too many reachable configurations for solution in the immediate future. However, there are several other related genres for which a computer search, possibly using the techniques described here, would be interesting. These include parking puzzles and Sokoban puzzles.
In parking puzzles (Hordern's categories E15 to E18), the tiles are mostly 1×2 and 2×1 rectangles representing cars in a (large) garage, though larger tiles (lorries) are also usually present. The puzzle is to manoeuvre a specified car out of the garage. The tiles may only be moved `lengthways', not moved sideways and not rotated. These restriction actually make the edit scripts easier; unfortunately, the large number (at least six in Hordern's examples) of empty squares makes them impossible, and a purpose-built program will be essential. The number of reachable configurations is very hard to estimate without computer exploration, so whether these problems are typically solvable is unknown a priori.
Sokoban (`warehouseman') puzzles are a recent Japanese genre. The arena is usually a complex of small `rooms' and connecting passages; the tiles (`crates') scattered around have no independent powers of movement; instead, they must be `pushed' by a distinguished tile, the `warehouseman', into the Finish configuration. Thus a crate which is pushed into a corner can never be moved again, and one which is pushed against a wall can be pushed off only if it be pushed to a `door' which the warehouseman can later reach the other side of. The interlocking access requirements make these challenging logical puzzles. There are far too many configurations for computer solution to be feasible by brute force. However, many of these configurations will contain dead ends, where crates have been pushed out of play, and many other configurations will be equivalent (for example, if a large room contains no more than three crates, it matters little where they are as long as none is against a wall, but four crates must not be pushed into a 2×2 block). An intelligent search which could prune the dead ends and recognise the equivalences should be able to solve at least Horden's examples (H1 to H10).
The solution to Checkmate is driven by three Unix shell scripts: (a) a run script that initialises the zeroth generation file, and repeatedly calls generate to construct the next generation, until some generation turns out to be empty; (b) a generate script that takes current and previous generation files as parameters, and creates from them the next generation; and (c) a find script capable of searching through the generations to find a given configuration, and when found to locate a predecessor configuration in the previous generation, and so on until the whole solution can be constructed. The run script is entirely routine, and is not discussed further. The find script is little harder; it uses the Unix grep command to find the configuration; once found. the appropriate generation file contains information about where the predecessor is to be found, so a simple edit extracts this information and iterates back to generation zero. The generate script is more interesting.
Each generation file contains one line per configuration. Each line typically looks like
The first part is the configuration in a simple notation -- read along the rows of a configuration, using B for black square, W for white square, kK for black and white kings, DD for the double piece, F for the fixed square, E for the empty and colon as a separator. Then there is a count, here 3, of the number of ways in which this configuration can be reached by a shortest route. Finally there is a list of how this configuration can be reached; in this case, it can be reached by moving Left from the configuration in line 16115 of the previous file, or by moving Right from that in line 16152.kWEB:BWFB:DDWB:KWWB 3 L16115 R16152
Each line is processed by a sed (the Unix `stream editor') script, which can, for example, suggest the replacement of TWKE by TWEK to swap WK and empty square. Other possible moves are generated in a similar way. No edits involve the colons, so `horizontal' moves are confined to a single row. For vertical moves, the swap is between the empty square and a movable tile five characters away. No moves involve the fixed square, and only horizontal moves (e.g. TWEDD to TWDDE) the double square.
The suggested moves are passed to a second sed script, which deletes `illegal' moves, by looking for kings separated by three, four, five or no characters and for an exposed BK on the a-file. The result is sorted, and then is merge-sorted with the previous generation.
Finally, the merged list is passed to yet another sed script. This firstly deletes any configuration which is from the older generation (which sorts before any copies) or is a copy thereof. Any remaining identical configurations are merged. The great complication here is the need to add the counts; it would take too much time to invoke a separate process, so this is done somewhat awkwardly by the edit script. This is undeniably slow, but it takes only a tiny fraction of the total time, which is dominated by the first sort. If the counts and moves were absent from the generation files, generate would be very much simpler (but only a little faster), at the expense of complications in find, which would have to construct predecessor configurations to search for in earlier generations.
Modern computers can easily handle arrays with a million or so elements, and a more efficient way of solving the whole problem would certainly have been to maintain an array with bits set aside for each configuration. There could be bits to describe presence, absence and legality of each configuration in each generation, and further bits to contain counts, line numbers, and so on. Sorting would then be unnecessary, and all processing could be done by simple scans up the array, setting, testing and clearing bits. However, the relationship between configuration and array index would be less transparent, especially in problems such as L'Ane Rouge, where a naive translation would use a great deal of unnecessary space. The programs required would be many more lines than the following scripts!
(a) run:
#! /bin/sh
nn=0 nminus=-1 start=${1:-kBWB:BWFW:KBDD:EWBW}
echo $start 1 D0 > l$nn 2> l$nminus
while [ -s l$nn ]
do nplus=`expr $nn + 1`
generate l$nn l$nminus l$nplus
nminus=$nn; nn=$nplus
done
#! /bin/sh
C='\([BWKk]\)' S='\([BWDE]\)' D='\([LRUD]\)' N='\([0-9][0-9]*\)'
sed -n < $1 "
s/ $D$N//g; t cancelt
: cancelt
h; s/E$C/\1E/; t Lsucc
s/EDD/DDE/; t Lsucc
: Lfail
s/${C}E/E\1/; t Rsucc
s/DDE/EDD/; t Rsucc
: Rfail
s/$C\(....\)E/E\2\1/; t Dsucc
: Dfail
s/E\(....\)$C/\2\1E/; t Usucc
b
: Lsucc
s/$/ L/p; =; g; t Lfail
: Rsucc
s/$/ R/p; =; g; t Rfail
: Dsucc
s/$/ D/p; =; g; t Dfail
: Usucc
s/$/ U/p; = " |
{ sed " N; s/\n//
/kK/d; /Kk/d; /K...k/d; /k...K/d
/K....k/d; /k....K/d; /K.....k/d; /k.....K/d
/^k....$S....$S....$S/d; /^.....k....$S....$S/d
/^..........k....$S/d; /^...............k/d; s/ / @ /"
echo ~~~; } | # marker -- ugh!
sort | sort -m - $2 |
# format of *old* line: posn nnn dirs ...
# format of *new* line: posn @ nnn dir
# so new lines all sort after corresponding old lines
sed -n "
: start
N; /@/!D; /^\([^ ]* \).*\n\1/b same
/^[^ ]* @/ { s/ @//; P; }; D
: same
/@.*@/b add
s/\n.*//; b start
: add
s/@ \([0-9]*\)\(.*\)\n.* @ \([0-9]*\)/@ +\3%=\1#\2/
: cont
s/=#/=0#/; s/\(.\)%/%\1/g; s/\(.\)#/#\1/
s/%9/%51111/g; s/%8/%5111/g; s/%7/%1111111/g; s/%6/%111111/g
s/%5/%11111/g; s/%4/%1111/g; s/%3/%111/g; s/%2/%11/g; s/%0/%/g
: carry
s/%1\(.*\)#0/%\1#1/; s/%1\(.*\)#1/%\1#2/; s/%1\(.*\)#2/%\1#3/
s/%1\(.*\)#3/%\1#4/; s/%1\(.*\)#4/%\1#5/; s/%1\(.*\)#5/%\1#6/
s/%1\(.*\)#6/%\1#7/; s/%1\(.*\)#7/%\1#8/; s/%1\(.*\)#8/%\1#9/
s/%1\(.*\)#9/%+1%\1#0/; /%1/t carry
s/+%//g; /@ +/b cont
s/=\(.*\)#/\1/; b start" >$3
#! /bin/sh
error () { echo "find: $@" 1>&2; exit 1; }
random () { [ $# = 1 ] || (:) & shift `expr $! % $#`; echo "$1"'; }
nn=0 pos="$1" route=
while [ -f l$nn ] || error "can't find $pos -- sorry!"
line=`cat l$nn | grep $pos`; [ -z "$line" ]
do nn=`expr $nn + 1`
done
echo $pos found at generation $nn.
[ $nn = 0 ] && error "you gave the start position!"
[ `echo "$line" | sed -n "$="` = 1 ] ||
error "$pos is ambiguous (choose one):
$line"
set $line
case $2 in
1) echo It can be reached in a unique way by: ;;
*) echo It can be reached in $2 ways, of which one is:
esac
while shift 2; dir=`random $*`
case $dir in
D*) route=" D$route";;
L*) route=" L$route";;
U*) route=" U$route";;
R*) route=" R$route"
esac
number=`echo $dir | sed s/.//`; [ $number != 0 ]
do nn=`expr $nn - 1`; set `sed -n "$number {p; q;}" l$nn`
done
echo $route |
sed 's/................................................../&\
/g'