My Java solution can solve the 100x100 board in 5.5ms (on my 2.5GHz Intel Core 2 Duo laptop). (Actually, it can solve the the 100x100 board 10,000 times in 55 seconds.) I actually provide two solutions: a very small heuristic-less solution, and a longer one based on Warnsdorff's heuristic.
/**
* Knight.java
* author: Kevin Greer
* date: Dec 1, 2008
Gives the following output for SIZE = 8
1 50 15 32 61 28 13 30
16 33 64 55 14 31 60 27
51 2 49 44 57 62 29 12
34 17 56 63 54 47 26 59
3 52 45 48 43 58 11 40
18 35 20 53 46 41 8 25
21 4 37 42 23 6 39 10
36 19 22 5 38 9 24 7
**/
public class Knight {
static final int SIZE = 100;
static final int[][] b = new int[SIZE][SIZE];
static final int[][] M = { {1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1} };
static void displayBoard() {
for ( int c = 0 ; c < SIZE ; c++ ) {
for ( int r = 0 ; r < SIZE ; r++ ) System.out.print(String.format(" %4d", b[r][c]));
System.out.println("\n");
}
}
// Simple Heuristic-less solution
static boolean s(int x,int y, int i) {
if ( x < 0 || y < 0 || x >= SIZE || y >= SIZE || b[x][y] != 0 ) return false;
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
return s(x+2,y+1,i) || s(x+2,y-1,i) || s(x-2,y+1,i) || s(x-2,y-1,i) || s(x+1,y+2,i) || s(x+1,y-2,i) || s(x-1,y+2,i) || s(x-1,y-2,i) || ( b[x][y] = 0 ) == 1;
}
// Solution using Warnsdorff's Heuristic
static boolean isGood(int x, int y) { return x >= 0 && y >= 0 && x < SIZE && y < SIZE && b[x][y] == 0; }
static boolean solve(int x, int y, int i) {
if ( ! isGood(x, y) ) return false;
try {
if ( ( b[x][y] = i++ ) == SIZE * SIZE ) { displayBoard(); return true; }
int[] friends = new int[M.length];
for ( int m = 0 ; m < M.length ; m++ ) if ( isGood(x+M[m][0], y+M[m][1]) ) for ( int m2 = 0 ; m2 < M.length ; m2++ ) if ( isGood(x+M[m][0]+M[m2][0], y+M[m][1]+M[m2][1]) ) friends[m]++;
for ( int n = 0 ; n < M.length ; n++ ) for ( int m = 0 ; m < M.length ; m++ ) if ( friends[m] == n && solve(x+M[m][0], y+M[m][1], i) ) return true;
return false;
} finally { b[x][y] = 0; }
}
public static void main(String[] argv) {
// Perform more iterators for more accurate benchmarks
for ( int i = 0 ; i < 1 ; i++ ) {
solve(0,0,1);
}
}
}
