Puzzles for FDR

The author has solved many puzzles on FDR over the year: examples are peg solitaire from Chapter 15 of TPC and Sudoku from Chapter 4 of UCS, in addition to the topics of several of the exercises in UCS and the practicals on the teaching material page.  Here are some more:

Knights exchange: this is based on a 5x5 grid containing 12 each black and white chess knights, arranged as follows with the central slot empty.

B B B B B
W B B B B
W W   B B
W W W W B
W W W W W

The objective is to exchange the blacks and whites in as few knights' moves as possible.

Cube Roll: You are given 8 unit cubes arranged within a 3x3 square:

X X X
X   X
X X X

Each of these cubes has three of its six faces visible and three concealed.  (There are two patterns of cube: the ones on the corners have the three faces round a corner visible.  The other three have the top face and ones on opposite sides of it.) The visible faces are all white, and the concealed ones are all black.

A move is to roll one of the cubes into the single empty slot in the 3x3 grid.  Thus initially any one of the four centre edges can roll into the centre, and then one of the adjacent corners rolls into the vacated slot.

The objective is to make all visible faces black, and all concealed ones white.

Monkey Puzzle: This consists of a number of different-sized rectangles
arranged in a 4 by 5 board (light pink is 2x2, magenta 1x2, green 2x1 and yellow 1x1; the two white squares are empty):



The objective is, by sliding the pieces around the board, to place the monkey (the 2x2 piece) in the bottom centre -- on top of its tail.

You can clearly change the initial configuration, or make it bigger, as
with many of these puzzles.


Instant Insanity: this is based on four coloured cubes, which can be unfolded to the
following nets:



The objective is to arrange them into a stack so that each of the four colours is visible on each of the four sides.

Exercise 8.2 generalised.  The puzzle shown in Figure 8.2 of UCS can be described as two one-dimensional cubes (i.e. lines) which intersect at a point, as in the following two two-dimensional cubes (squares) intersect at an empty slot .

    B B B
    B B B
W W . B B
W W W
W W W

White pegs move forward up or right (increasing one coordinate) either one step into the empty slot or hopping a black, and the blacks decrease a coordinate similarly.  Swap the blacks and whites.

This can be generalised to any size of cube in any number of dimensions.  (Or even a generalised rectangle such as 3x2x2.)  Not all instances are soluble.

Towers of Hanoi: this is a very standard combinatorial puzzle in which there are three pegs A,B,C and N differently sized discs.  Initially they are arranged on peg A, in increasing size from top to bottom of the pile.  You move one disc at a time from one peg to another, but you may never place any disc on top of a smaller one. 

The objective is to move all the discs to one of the other pegs (B, say).

Other Sudoku-like puzzles: for example "killer" sudoku (where the 9x9 grid is partitioned into regions, each of which does not allow repetition within it) and kakuro. Newpapers are full of these. (The author developed a CSP script to solve killer sudoku puzzles, which proved a much more challenging exercise than the normal sort.)

Such puzzles can provide interesting exercises in coding, and in the discipline of creating models that have no more than one state for each natural state of the puzzle.  They can be good benchmarks for searching and alternative model checking techniques, and nice examples to illustrate how FDR can solve problems that humans find very difficult - even though by sheer brute force.

It is sometimes, for example in knights exchange and cube roll, possible to put a measure on an arbitrary position to judge how far it is from the target state, and use a parallel process to measure this distance.  If used skillfully these can cut down the number of states required to find an optimal soluition considerably. Using measures discovered by the author, knights exchange reduces from 68M to 1M states, and cube roll can be cut from approaching 900M to about 50M.  In many cases the puzzles can be clarified by some mathematics (e.g. solitaire and instant insanity) or a nice program (e.g. Hanoi).








  

This site is presently under construction