From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: rec.games.chess,rec.puzzles,comp.unix.shell
Subject: A puzzle for Christmas
Date: 18 Dec 92 20:04:00 GMT
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.

While at a conference recently, I picked up a neat little sliding-block
puzzle with a chess theme.  It's called CHECKMATE, by W. G. H. Strijbos,
and made by PUSSYCAT, Bad Salzuflen, Germany.  [OK, I've explained two of
the newsgroups this is cross-posted to;  for the shell stuff, see later.]

	Basically, it's a 4x4 set of tiles, looking like a quarter of a
chessboard, with a white rook on a1, white king on a2 and black king on
a4, plus an empty square at "a0".  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.  OK, that's easy enough, and the tiles
are well made, 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;  you can
very easily bottle things up!  Details left as an exercise.

	You don't need to pay #4 [over $6, around 10DM], as I did;  it's
easy to simulate the puzzle using a chess board.  Just use the bottom LH
corner, put kings on a2 and a4, some heavy immobile black piece on c3,
two different pieces, say bishops, on c2 and d2 [to remind you to move
them together], and pawns of the correct colours on the remaining squares
except a1.  Now slide the pieces around in the obvious way.  On the other
hand, I expect W. G. H. Strijbos would like you to buy the real thing, and
it *is* quite neat.

	The real thing is so easy to mess up that I got rather frustrated
with it, and eventually wrote a program to solve it [more precisely, so
that I could unscramble any given position without having to think about
it].  Actually, I wrote a shell script to solve it;  you may or may not
find that amusing/instructive.  The remainder of this article comprises
(a) one of the solutions;  (b) some brief notes on what I found with the
aid of the program;  (c) a shell archive of the scripts used.

	Enjoy!  [As they say.]  Merry Christmas to all our readers!

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk

It 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 Kd3 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 Ra1
where the king and rook moves are given explicitly, and D [L, U, R] means
slide an ordinary tile down [left, up, right] into the empty space.

Somewhat to my surprise, the mate position is actually one of the easier
to reach -- about two thirds of all attainable positions take more moves.
The most remote position from the start is WWWW:KBBW:WBBB:RBkB, where W =
white square, B = black square, K = white king, k = black king, R = white
rook.  [If you run the scripts below yourself, this position is found in
file l115, and its solution is found by "route WWWW:KBFW:DDBB:EBkB", which
uses the internal notation of F for the fixed square, DD for the double
tile, and E for the empty square.]

	There are 256 legal configurations of the kings and the double
tile, and thus 256x11!/5!5! = 709632 legal configurations of the tiles,
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 [eg, you can't reach WKd1, BKd3 with the double tile
on c2d2];  of the 256x11 = 2816 legal configurations of the kings, double
and empty, only 2595 can be reached [eg, with WKa4, BKc4, double a2b2, the
empty cannot be on a3, b3 or b4], so the final database contains "only"
2595x10!/5!5! = 653940 positions.

	If you want to construct this database yourself, "unshar" the files
below into some unused directory, and type "run".  You need a Unix system
of reasonable speed and with ample disc.  There will be created a whole
lot of files called "lNN" where NN is an integer, the generation number,
most of which will be compressed.  These will total around 6 megabytes.
While "run" is running, there is also a large database, which grows to
around 19 meg;  this has to be sorted, so another 19 meg is needed, total
44+ meg.  On many systems, 19 meg can't be sorted "by default", and you
may need to add a parameter such as "-T somedirectory" to the two "sort -m"
commands below, where "somedirectory" has the needed 19 meg free.  The
database could be compressed, which would save space but waste time.

	Once the run is complete, the "route" command will look for any
given position, and will print out how to get to it from "start".  It
could very easily be modded to print instead the route *back* to "start".

	On a Silicon Graphics workstation, the "run" script takes around
1h45m to complete;  it will take a *lot* longer on your average PC or Sun
[around a day on a Sparc 1+, for example].  Re-code it in C if you feel
the need!  Everything given works unchanged on all the systems available
to me here;  your mileage may vary.

	Improvements welcomed.  The same ideas will adopt to *many*
sliding-block puzzles;  I'd be happy to try any interesting ones, but
note that lots of them have prohibitively many attainable positions [eg,
around 10^13 for the classical 14-15 puzzle].  I'd also welcome any
pointers to published algorithms or code for such puzzles.

	The code given works roughly as follows:  (a) Given a file
containing lots of positions, a "sed" script operates on each position,
and generates its followers [eg, "EK" -> "KE" corresponds to moving the
white king left into the empty square].  (b) A second script filters out
the illegalities and generally tidies up.  (c) The result is then sorted
and merged with the existing database.  Finally, (d) a pass is made over
the merged database to strip out positions already known about, and to
combine positions reached in several ways.  Most of the complications
in the "sed" script for (d) are caused by the necessity of adding the
numbers of ways;  but the "sed" script is *much* faster [factor 16, in
my tests] than an "awk" or "shell + expr" script to do the same thing.
Of course, a purpose-built C program would be much faster still.

	ANW

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  generate route run
# Wrapped by anw@piaggio on Fri Dec 18 19:47:13 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f generate -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"generate\"
else
echo shar: Extracting \"generate\" \(2249 characters\)
sed "s/^X//" >generate <<'END_OF_generate'
X#! /bin/sh
X
X# This file is Copyright 1992 A. N. Walker, anw@maths.nott.ac.uk
X#	Permission is hereby granted to use it freely for academic or
X# private purposes, provided that this notice is retained and any changes
X# noted in versions made available to other people.
X
X# From positions given in $1, generate all moves into $3.
X# Resulting positions will be sorted, and those that are already in $2
X# (the "database") will have been stripped out.
X
X# Format of a position:
X#	pppp:pppp:pppp:pppp NNN [UDLR]NNN ...
X# where p = {BWDFEKk} [black, white, double, fixed, empty, WK, BK]
X#	NNN = # ways of getting to this position in minimal moves
X#	UDLR = up, down, left, right
X#	NNN = corresponding line number in $1, for benefit of analysis
X
XC='\([BWKk]\)' S='\([BWDE]\)' D='\([LRUD]\)' N='\([0-9][0-9]*\)'
X
Xsed -n < $1 "
X	s/ $D$N//g; t cancelt
X  : cancelt
X	h; s/E$C/\1E/; t Lsucc
X	s/EDD/DDE/; t Lsucc
X  : Lfail
X	s/${C}E/E\1/; t Rsucc
X	s/DDE/EDD/; t Rsucc
X  : Rfail
X	s/$C\(....\)E/E\2\1/; t Dsucc
X  : Dfail
X	s/E\(....\)$C/\2\1E/; t Usucc
X	b
X  : Lsucc
X	s/$/ L/p; =; g; t Lfail
X  : Rsucc
X	s/$/ R/p; =; g; t Rfail
X  : Dsucc
X	s/$/ D/p; =; g; t Dfail
X  : Usucc
X	s/$/ U/p; =
X" |
X{	sed "
X		N; s/\n//
X	  : adjK:
X		/kK/d; /Kk/d; /K...k/d; /k...K/d
X		/K....k/d; /k....K/d; /K.....k/d; /k.....K/d
X	  : Rcheck:
X		/^k....$S....$S....$S/d
X		/^.....k....$S....$S/d
X		/^..........k....$S/d
X		/^...............k/d
X		s/ / @ /"
X	echo ~~~	# marker!  Ugh!
X} |
Xsort |
Xsort -m - $2 |
X# format of *old* line: posn nnn dirs ...
X# format of *new* line: posn @ nnn dir
X# so new lines all sort after corres old lines
Xsed -n "
X   : start
X	N
X	/@/!D
X	/^\([^ ]* \).*\n\1/b same
X	/^[^ ]* @/ { s/ @//; P; }
X	D
X   : same
X	/@.*@/b add
X	s/\n.*//; b start
X   : add
X	s/@ \([0-9]*\)\(.*\)\n.* @ \([0-9]*\)/@ +\3%=\1#\2/
X    : cont
X	s/=#/=0#/
X	s/\(.\)%/%\1/g
X	s/\(.\)#/#\1/
X	s/%0/%/g
X	s/%2/%11/g
X	s/%3/%111/g
X	s/%4/%1111/g
X	s/%5/%11111/g
X	s/%6/%111111/g
X	s/%7/%1111111/g
X	s/%8/%11111111/g
X	s/%9/%111111111/g
X   : carry
X	s/%1\(.*\)#0/%\1#1/
X	s/%1\(.*\)#1/%\1#2/
X	s/%1\(.*\)#2/%\1#3/
X	s/%1\(.*\)#3/%\1#4/
X	s/%1\(.*\)#4/%\1#5/
X	s/%1\(.*\)#5/%\1#6/
X	s/%1\(.*\)#6/%\1#7/
X	s/%1\(.*\)#7/%\1#8/
X	s/%1\(.*\)#8/%\1#9/
X	s/%1\(.*\)#9/%+1%\1#0/
X	/%1/t carry
X	s/+%//g
X	/@ +/b cont
X	s/=\(.*\)#/\1/
X	b start
X" >$3
END_OF_generate
if test 2249 -ne `wc -c <generate`; then
    echo shar: \"generate\" unpacked with wrong size!
fi
chmod +x generate
# end of overwriting check
fi
if test -f route -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"route\"
else
echo shar: Extracting \"route\" \(1901 characters\)
sed "s/^X//" >route <<'END_OF_route'
X#! /bin/sh
X
X# This file is Copyright 1992 A. N. Walker, anw@maths.nott.ac.uk
X#	Permission is hereby granted to use it freely for academic or
X# private purposes, provided that this notice is retained and any changes
X# noted in versions made available to other people.
X
X# look for $1 in the generated files, and trace back its antecedents to start
X
Xerror () { echo "find:  $@" 1>&2; exit 1; }
X
Xdocat () { zcat $1.Z 2>/dev/null || cat $1 2>/dev/null; }
X
Xrandom () {
X	[ $# = 1 ] || (:) & shift `expr $! % $#`
X	echo "$1"
X}
X
Xverbose=off
X[ -v = "$1" ] && { verbose=on shift; }
X
Xcase $# in
X	1) pos="$1" ;;
X	*) error "usage:  there must be exactly one parameter"
Xesac
X
X# find last generation.  Actually, we now know there are exactly 115 ....
Xnn=1
Xwhile [ -f l$nn -o -f l$nn.Z ]
Xdo	nn=`expr $nn + 1`
Xdone
X
X# find *relevant* generation
Xwhile
X	nn=`expr $nn - 1`
X	case $nn in
X		-1)	 error "Can't find $pos -- sorry!"
X	esac
X	line=`docat l$nn | grep $pos`
X	[ -z "$line" ]
Xdo
X	[ $verbose = on ] && echo Searching generation $nn
Xdone
X
Xcase `echo "$line" | sed -n "$="` in
X	1) ;;
X	*) error "$pos was found at generation $nn, but is ambiguous:
X$line
XChoose one!"
Xesac
X
Xset $line
Xecho $pos found at generation $nn
Xcase $2 in
X	1)	echo It can be reached in just one way: ;;
X	*)	echo It can be reached in $2 ways, of which one is:
Xesac
X
Xcase $nn in
X	0)	echo D -- You gave the start position!
X		exit 1
Xesac
X
Xroute=
X
Xwhile
X	shift 2
X	dir=`random $*`
X	[ $verbose = on ] && echo looking at $line
X	[ $verbose = on ] && echo backtracking $dir
X	case $dir in
X		D*)	route=" D$route";;
X		L*)	route=" L$route";;
X		U*)	route=" U$route";;
X		R*)	route=" R$route"
X	esac
X	number=`echo $dir | sed s/.//`
X	[ $number != 0 ]
Xdo
X	nn=`expr $nn - 1`
X	line=`docat l$nn | sed -n "$number {p; q;}"`
X	set $line
Xdone
X
X[ $verbose = on ] && echo "[initial D means Ra1-a0]:"
Xecho $route |
X	sed 's/................................................../&\
X/g'
END_OF_route
if test 1901 -ne `wc -c <route`; then
    echo shar: \"route\" unpacked with wrong size!
fi
chmod +x route
# end of overwriting check
fi
if test -f run -a "${1}" != "-c" ; then 
  echo shar: Will not over-write existing file \"run\"
else
echo shar: Extracting \"run\" \(528 characters\)
sed "s/^X//" >run <<'END_OF_run'
X#! /bin/sh
X
X# This file is Copyright 1992 A. N. Walker, anw@maths.nott.ac.uk
X#	Permission is hereby granted to use it freely for academic or
X# private purposes, provided that this notice is retained and any changes
X# noted in versions made available to other people.
X
Xcase $1 in
X    [0-9]*) nn=$1 ;;
X     *) echo kBWB:BWFW:KBDD:EWBW 1 D0 > l0
X	cp l0 database
X	nn=0
Xesac
X
Xwhile [ -s l$nn ]
Xdo
X	nplus=`expr $nn + 1`
X	generate l$nn database l$nplus
X	sort -m -o database database l$nplus
X	compress l$nn
X	nn=$nplus
Xdone
X
Xrm database
END_OF_run
if test 528 -ne `wc -c <run`; then
    echo shar: \"run\" unpacked with wrong size!
fi
chmod +x run
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0
Newsgroups: rec.games.chess