John F. Dumas Vulcan Ware
_blank_

Knight Traversal


// --------------------------------------------------------------
// 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
// --------------------------------------------------------------

Return to Main