🚀 go-pugleaf

Hi,

I have written a small program for a school project that solves the Knight
tour puzzle. Gauss solved this problem when he 4 years old (Wow, he was
really bright!!!). The problem consist to find a way to visit all the
Chessboard's cases without visiting the same case more than once.

I have used 2 methods to solve this problem. The first one is to stupidly
try all the possibles combinations. The other one is similar except that
when it is the time to select the next case to visit, it prefers the cases
which are harder to access (e.g. the corners).

With the second method, the program find a solution after few seconds.
However, I tried the first one and the program have been running for more
than 24 hours and it's still searching. There has been more than 2 billions
backtracks. ( The program prints a dot at each 1 000 000 backtracks and the
screen is full of '.'). A backtrack, it is the action to go one step back
when the algorithm is at a dead-end.

My problem is the following: I'm not sure if it is because there is a bug
or if it is because the problem is really very complex to solve that my
program did not find yet an answer and I'm incapable to calculate the
number of necessary backtracks in the worst case to find a solution. I
guess the answer is near 63! (63! is the result of a permutation P(63,63)
but the true answer is surely below that because of the game's imposed
restrictions)

Could you help me to find the number of neccesary backtracks ?
Will I need a Deep Blue to solve my problem in a reasonnable time ?

TIA

P.S.: If you want to answer me please do it by e-mail because I don't
always check the newsgroup.

-- 
Olivier Langlois - olanglois@sympatico.ca
Electrical Engineering Student
�cole de Technologie Sup�rieure - http://www.etsmtl.ca
Montreal, Canada