Anonymous user
Talk:Knight's tour: Difference between revisions
→The 7x7 problem: added summary of results
m (→The 7x7 problem: +sig and purpose, noted fix) |
(→The 7x7 problem: added summary of results) |
||
Line 67:
:: 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.
:: This shows a summary of results for 5 tries at each starting position:
:: 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. This is for the failing a1:▼
<pre>Results of tests for N=7 :
::: Debug log : move#, move : (accessibility) choices▼
Starting Square | a1 a2 a3 a4 b2 b3 b4 c3 c4 d4
::: 1. a1 : (5) b3 c2 ▼
* Total * | 66.67% 0.00% 66.67% 0.00% 53.33% 0.00% 60.00% 73.33% 0.00% 100.00%
::: 2. b3 : (3) c1 a5 ▼
RandomTieBreaker | 80.00% 0.00% 40.00% 0.00% 60.00% 0.00% 40.00% 80.00% 0.00% 100.00%
::: 3. c1 : (2) a2 ▼
FirstTieBreaker | 80.00% 0.00% 80.00% 0.00% 40.00% 0.00% 80.00% 60.00% 0.00% 100.00%
::: 4. a2 : (5) b4 ▼
RothTieBreaker | 40.00% 0.00% 80.00% 0.00% 60.00% 0.00% 60.00% 80.00% 0.00% 100.00%
::: 5. b4 : (2) a6 ▼
* Count * | 15 15 15 15 15 15 15 15 15 15 </pre>
▲:: Looking at two cases where the start was a1 and a3, the a1 failed and a3 start did not (Random Tie Breaker). 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. This is for the failing a1:
:: I'd be interested in seeing how others fare with a 7x7
== C++ formatting ==
| |||