ptoulis,
Odd. The Wikipedia entry mentions that Warnsdorff's algorithm is a heuristic solution, but doesn't mention under what circumstances it fails. The MathWorld entry for KnightsTour indicates it can fail on boards 76x76. There is a proven linear solution that is far more complicated. It would be nice to implement that solution in perl and then find a case where the Python solution fails - just cause.