The
random walk is not normally valued as a searching method.
(It is no surprise. Only very sparingly will it deal with the problem
optimally, if, indeed, at all.) There is a large number of
chessboard puzzles and the random walk is employed to tackle four of them. The results are surprisingly good.
A bewildering number of variations is available on the standard game of chess: Some people allow the queen and bishops to be optionally
reflected when they reach the edge of the board. The game need not end when the king is captured, but could go on until the entire side is out. There is no shortage of chessboard puzzles, either, and the topic appears to be a goldmine if you are interested in
artificial intelligence programming.
Place 14 knights on a standard chessboard so that all squares are in control, including those on which knights have been placed (that's the
14 knight puzzle). The board is initially filled with knights, and as many of them as possible are removed at random- so long as all squares are still in control (
program).
The program has played the puzzle 1,000 times and here is the bargraph for the number of knights needed every time. My figures are dependent on random numbers, so yours will not be quite the same.
There is also the dual puzzle, which the program found more demanding, but it can be done: Place 25 knights on a standard chessboard, so that none can be removed without losing control of some square(s)- that is, place them as 'inefficiently' as possible. (Placing more may well be possible- I have not looked into this very thoroughly.)
After accounting for symmetries, about 5.7 × 10
16 cases are possible. Of course, a program which deals with this puzzle in a systematic way does not need to examine most of those, if only because there are multiple solutions.
A related puzzle requests placing 5 queens on the standard chessboard, so that all squares are in check, this time
excluding the squares on which queens have been placed (
program). A distribution also involves other numbers of remaining queens, of course, when the problem is tackled by the random walk, and the following table gives the results of playing 1,000 games:
| Number of queens left | Number of games |
|---|
| 5 | 18 |
| 6 | 302 |
| 7 | 513 |
| 8 | 142 |
| 9 | 22 |
| 10 | 3 |
On a modern computer, the
program should provide a 5-queen solution every 150 milliseconds, on average. The dual problem involves 10 queens as far as I can tell, and is, again, tougher:
Present random quote:
For my own code up to this point:
Valid XHTML 1.1