Anonymous user
Talk:Knight's tour: Difference between revisions
→Incomplete Tours and Warnsdorff: 7x7 heading and more information
(→References: more refs-) |
(→Incomplete Tours and Warnsdorff: 7x7 heading and more information) |
||
Line 53:
:The Perl solution is deterministic, and produces complete tours for all 64 start squares. So it must be something in the ordering of the move list. --[[User:Markjreed|Markjreed]] 01:54, 31 May 2011 (UTC)
=== The 7x7 problem ==
:Try a 7x7 board. --[[User:Paddy3118|Paddy3118]] 03:24, 31 May 2011 (UTC)
:: I will. At this point there is something wrong with this solution. I will have to come back to it later (possibly this weekend). This was implemented from the WP description which talks about sets. I think the heart of the problem lies in the used of unordered sets everywhere and I will have to walk through some comparative examples side by side. This wouldn't be the first time I've been burned by a vague WP algorithm description. I'll have to borrow one of the other solutions and add code to show me the order squares get presented. --[[User:Dgamey|Dgamey]] 09:48, 31 May 2011 (UTC)
Line 61 ⟶ 63:
:::: 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)
:::: 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.
::::Looking at two cases where the start was a1 and a3, the a1 failed and a3 start did not. Both case went through a1 but the one starting in a3 went through a1 on move 37. Looking at the ties, there was no obvious choice that would have produced a tour. The start in a1 would have had to violate the accessibility filter to succeed. That is a1, b3, c1, a2, b4, ... fails vs. a1, b3, c1, a2, c3, ... succeeds. In the later case c3 was chosen not from the ties but from the group with the highest accessibility. I'll have to dig into this a bit more later. What I did add was a log like this showing the move, minimal accessibility, and moves in that group:
<pre>Debug log : move#, move : (accessibility) choices
1. a1 : (5) b3 c2
2. b3 : (3) c1 a5
3. c1 : (2) a2
4. a2 : (5) b4
5. b4 : (2) a6
6. a6 : (3) c7
7. c7 : (5) b5 e6</pre>
I'd be interested in seeing how others fare with a 7x7 starting in a1. --[[User:Dgamey|Dgamey]] 10:28, 2 June 2011 (UTC)
== C++ formatting ==
| |||