SOLUTION OF THE KNIGHTS HAMILTONIAN PATH PROBLEM ON CHESSBOARDS

Is it possible for a knight to visit all squares of an n x n chessboar d on an admissible path exactly once? The answer is yes ff and only if n greater-than-or-equal-to 5. The kth position in such a path can be computed with a constant number of arithmetic operations. A Hamiltonia n path from a given source s to a given terminal t exists for n greate r-than-or-equal-to 6 if and only if some easily testable color criteri on is fulfilled. Hamiltonian circuits exist if and only if n greater-t han-or-equal-to 6 and n is even.