Red King

A harder problem to solve using random search than Einstein's Problem is laid out below; it concerns finding the set of moves made by a knight on a chess board to fit a set of goals.

The Numbers 1 to 64 have been placed in the grid, with the starting point as shown:

1 2 3 4 5 6 7 8123145678

Each subsequent number is placed in accordance with a knight's move in chess, ending with 64, a knight's move from 1. The following clues include:

*Across*

- Nothing greater than 55
- One square number, nothing below 20, two multiples of 17
- Two cube numbers and two square numbers; three multiples of 7
- Nothing divisible by 8 or 12
- One cube number & one square number; two multiples of 21; nothing divisible by 13
- One cube number & two square numbers. Nothing greater than 60
- Two square numbers; one number is seven times another
- Two multiples of 20 and one multiple of 17

*Down*

- One cube number and one square number; nothing between 20 and 30
- One cube number and one square number; two multiples of 19; nothing below 10
- Three square numbers; two multiples of 18
- Three multiples of 13 and one multiple of 18
- Two cube numbers; nothing between 40 & 50
- One square number; nothing divisible by either 4 or 9
- One square number; four multiples of 4; nothing divisible by 9
- One square number; one number is the reverse of another; Total equals 234

You will all know how much grunt power is required if you intend to just do a complete, random search of the moves on a chessboard. Problems based on the Knight's Tour, where a knight visits every square once and once only, can run into the millions of years of completion time. A common algorithm to overcome this is the Warnsdorff Rule, which states that given a choice of moves, the move that permits the LEAST number of permitted moves at the next square should be tested first. However, this is perhaps not the best course of action here as that rule is used with a view to finding any solution to the problem, not such a specific one such as here.

Instead, I base my search solution on the core elements of the problem. We are told the rows/columns of all the cube & square numbers as well as those for the multiples of 18 & 17 and the rows/columns where multiples of 4 & 9 do not occur. These alone are what was used to control the search space.

All tests were done on an Athlon 2200+, 256Mb RAM and FreeBSD 4.9 generic kernel. The source code was compiled using gcc and the UNIX time command used as stated below:

g++ -O3 -funroll-loops -funroll-all-loops -o knightmove knightmove.c board.c time knightmove

The final program took 402.2secs to complete.

Source Code can be found here.

Select+Drag to reveal

1 2 3 4 5 6 7 8155 48 33 26 53 46 31 24234 51 54 47 32 25 28 4531 56 49 52 27 30 23 14450 35 2 57 22 13 44 29537 64 21 12 3 58 15 42620 11 36 39 8 43 4 59763 38 9 18 61 6 41 16810 19 62 7 40 17 60 5