Back to General discussions forum
I'm trying Warnsdorf heuristic to solve this problem, but this heuristic seems to be wrong.
For example, here is one of the paths built using Warnsdorf's rule:
- - - - 3 6 71 66 73 8 79 64 41 10 31 28
- - - 5 70 - 2 7 62 65 74 9 32 29 42 11
- - 69 - - 4 67 72 75 78 63 40 47 44 27 30
- - - - 68 1 76 - - 61 48 45 - 33 12 43
- - - - - - - - 77 50 53 - 39 46 37 26
- - - - - - - - 60 57 - 49 52 - 34 13
- - - - - - - 58 - - 51 54 - 38 25 36
- - - - - - - - - 59 56 - - 35 14 -
- - - - - - - - - - - - 55 - - 24
- - - - - - - - - - - - - - - 15
- - - - - - - - - - - - - - 23 -
- - - - - - - - - - - - - - 16 -
- - - - - - - - - - - - - - - 22
- - - - - - - - - - - - - - - 17
- - - - - - - - - - - - - - 21 -
- - - - - - - - - - - - - - 18 -
- - - - - - - - - - - - - 20 - -
- - - - - - - - - - - - - - - 19
- - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - -
As you can see, the knight got trapped at move 79 and cannot proceed anymore.
Tried around 1000 times on this board, the best result is 129 jumps, the worst is 54, but never got the full path with 319 jumps.
And I don't even take into account the coordinates of cut cell for now...
Warnsdorf's rule is simply a useful heuristic to speed up your search. You still need to backtrack.
zelevin, thank you much for hint! I will try to combine Warnsdorf's rule with backtracking. Gotta cook an awesome code :).