Talk:Knight's tour: Difference between revisions
Content added Content deleted
(→The 7x7 problem: A solution on 7x7 should be impossible) |
(→The 7x7 problem: Extra-extra.) |
||
| Line 66: | Line 66: | ||
::::: 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) |
::::: 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) |
||
:::::: The way I read the reference documentation, the tour just had to cover every square. Ending on a square that was a nights-move away from the start point was an (interesting), extra requirement. --[[User:Paddy3118|Paddy3118]] 15:27, 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. |
:: 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. |
||