// --------------------------------------------------------------
// In chess a knight moves in an 'L' pattern, for example:
//
// [ ][ ][ ][ ][ ][ ][ ][ ]
// [ ][ ][x][ ][x][ ][ ][ ]
// [ ][x][ ][ ][ ][x][ ][ ]
// [ ][ ][ ][K][ ][ ][ ][ ]
// [ ][x][ ][ ][ ][x][ ][ ]
// [ ][ ][x][ ][x][ ][ ][ ]
// [ ][ ][ ][ ][ ][ ][ ][ ]
// [ ][ ][ ][ ][ ][ ][ ][ ]
//
// Given a board with dimensions (n, m) and a
// starting position (row, column) find a path whereby
// the knight can traverse every square on the board
// without landing on any square more than once.
//
// We start by setting up a table of all available legal moves
// starting from each of the n * m squares.
//
// We then begin from our starting square and try each
// legal move recursively continuing this process until
// we either run out of possibilities or succeed
// in finding a solution.
//
// Here is an example path found by this program
// using an 8 x 8 chess board:
//
// 64 49 22 37 24 35 60 31
// 51 38 63 34 61 32 25 8
// 48 21 50 23 36 9 30 59
// 39 52 1 62 33 58 7 26
// 20 47 18 43 16 27 10 29
// 53 40 55 2 57 4 13 6
// 46 19 42 17 44 15 28 11
// 41 54 45 56 3 12 5 14
//
// Note that all numbers from 1 -> 64 are present
// and for each number 'n' the square containing the
// next number 'n + 1' is always reachable via the
// 'L' pattern discussed above.
//
// To compile this code:
// unix : g++ -W -Wall knight.cpp
// win32: cl -W3 -GX knight.cpp
// --------------------------------------------------------------
 Source Code
Return to Main |
