Knight's Tourlogician series
This is a well-known chessboard puzzle. The knight’s move (plus or minus two squares in one direction and plus or minus one square in the orthogonal direction) can be seen as ordering the squares of the board in a kind of strange way: to the knight, d4 is adjacent to e6, while d5 is three steps away from d4. The knight’s tour problem (stated here for a 6×6 board because it takes too long to solve for 8×8) is fairly tricky to express well in our notation. Don’t worry if your first few correct versions all time out!
Consider a board like a normal chessboard except that it has only 6 ranks and 6 files instead of the normal 8.
There is a knight in square a1 (a corner square). Find a function “next” from square to square (actually it is better to define two, “nextR” and “nextF” from pairs (rank,file) to rank and file respectively) such that next(x) is always a knight’s move away from x and such that the knight on a1 will visit every square on the board exactly once by always jumping from each square to the “next”.
It is easy to prove that there is no knight’s tour on any square board with more than one and less than 5 ranks and files, and obviously any knight’s tour on a board with an odd number of squares must start and finish on the “majority” colour. Otherwise, knight’s tours exist for every (square) board size. A knight’s tour is closed if the knight on its finishing square attacks its starting square. Obviously, closed tours can exist only for boards with an even number of squares. As a point of trivia, there are known to be 19,724 closed tours on the 6×6 board.
In looking at this problem from the standpoint of AI planning (a side interest of mine when I’m not writing logic puzzles) I have found that a decent solution method is forward chaining: the knight repeatedly guesses a good square to jump to and jumps, optimistically, and backtracks when there is a square with no possible exit moves. A good heuristic for this method is always to jump to the square (among those a knight’s move away from the present one) with the smallest number of available (unvisited) exits. Even more efficient solution methods exist, as the problem is actually solvable in linear time. For the solver you are using, which works from a description in first order logic, sophisticated search-guiding heuristics are hard to incorporate. Don’t worry about them for this problem: for the 6×6 board you don’t need them.
For an account of the knight’s tour and some of its ramifications, see here
Solver
Auto Parser Results
No errors found.