An implementation of knight’s tour algorithm written in javascript & html5

A knight’s tour is a sequence of moves of a knight on a chessboards such that the knight visits every square exactly once. The knight’s tour problem is an instance of the more general Hamiltonian path problem in graph theory. we use the Warnsdorff’s rule “an heuristic algorithm”. We move the knight so that we always proceed to the square from which the knight will have the fewest onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is, of course, possible to have two or more choices for which the number of onward moves is equal. Below we can see the piece of code where the chessboard created using html5 and algorithm’s implementation in javascript. The algorithm chooses the square where the knight has the minimum value of possible moves. This is not the best approach because there are cases that the puzzle doesn’t have a solution as we can see at this paper. In a next post i’ll try to solve the problem. The knight’s tour has been tested in mozzila firefox and google chrome.

(more…)