The
Red King

Knight Move

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.

Problem Statement

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

   1  2  3  4  5  6  7  8
1
2
3  1
4
5
6
7
8

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

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

Down

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

Solutions

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.

Correct Solution

Select+Drag to reveal

   1  2  3  4  5  6  7  8
1 55 48 33 26 53 46 31 24
2 34 51 54 47 32 25 28 45
3  1 56 49 52 27 30 23 14
4 50 35  2 57 22 13 44 29
5 37 64 21 12  3 58 15 42
6 20 11 36 39  8 43  4 59
7 63 38  9 18 61  6 41 16
8 10 19 62  7 40 17 60  5