Page 12 M500 180
Solution 178.6 – Ten blocks
Ten pieces of various sizes slide round a board in the obvious
manner. Move the large square from the middle-left of the array
to the middle-right.
Dick Boardman
Denote the pieces by letters, as above, and divide
the board into 20 numbered squares, opposite.
Piece A originally covers squares 1, 2, 5, 6 and the
object of the puzzle is to move it to the position
that occupies squares 13, 14, 17, 18.
0 4 8 12 16
1 5 9 13 17
2 6 10 14 18
3 7 11 15 19
Initially, the method used was a breadth-first search in which all the new
positions resulting from a given position were placed on a stack. Positions
which occurred before, positions which are symmetrical to previous positions
and positions in which pieces of similar shape are swapped were rejected.
This method found a solution in 106 moves after processing about 12000
positions.
Later versions of this program use a ‘best-first’ search method in which
the stack is searched for the node with the highest value and the next posi-
tions are generated from that. Positions with the same value are processed
sequentially. This reduces the number of processed positions to about 5000.
The value of a position is taken as the number of the first column containing
piece A.
Comments to this Manuals