Talk:Knight's tour: Difference between revisions

Line 64:

:::: The probability of failure depends on the board size and the tiebreak rule (move consideration order, for a first- or last-wins algorithm); for random move selection, it's about 25% on a 7x7 board. The order that I picked happens to work 100% of the time for an 8x8 board, but a general solution requires a more complex algorithm. The Ganzfried paper cited above includes one such, Squirrel's algorithm, which adjusts the ordering of the moves after certain landmarks in the progress of the tour. --[[User:Markjreed|Markjreed]] 02:29, 1 June 2011 (UTC)

::::: It should be 100% rate of failure on a 7x7 board! The issue is that a true tour is one that's a circuit that goes back to the initial position. If there's an odd number of squares, a simple parity argument shows that there cannot be solution (there must be different numbers of white and black squares, so a return to the initial location would require a parity violation when completing the loop). Sorry to be so awkward, but this problem's actually very well defined in this area… –[[User:Dkf|Donal Fellows]] 14:12, 2 June 2011 (UTC)

:: I started to measure success/failure on a 7x7 using different tie breakers. Starting with a triangle of squares that provide a minimum under rotation & reflection it really looks like starting position is the predominant factor. I haven't yet tried all cases just in case rotation/reflection does affect the results.