Anonymous user
Talk:Knight's tour: Difference between revisions
m
no edit summary
(→C++ formatting: C++ house style) |
mNo edit summary |
||
| (12 intermediate revisions by 5 users not shown) | |||
Line 1:
== solutions found fast ==
Wow, this was found fast. I was still prepping my first couple implementations.:)
--[[User:Markjreed|Markjreed]] 02:09, 30 May 2011 (UTC)
Line 9 ⟶ 10:
The following had more than I needed to know about the problem [http://www.cs.cmu.edu/~sganzfri/REUPaper.pdf A Simple Algorithm for Knight’s Tours] by Sam Ganzfried. --[[User:Paddy3118|Paddy3118]] 07:22, 29 May 2011 (UTC)
::::::: (above) broken link. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 20:56, 22 July 2019 (UTC)
::::::: (above) referenced document can be found here: [http://math.oregonstate.edu/~math_reu/proceedings/REU_Proceedings/Proceedings2004/2004Ganzfried.pdf A Simple Algorithm for Knight’s Tours by Sam Ganzfried]
Line 68 ⟶ 71:
:::::: 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)
:::::: Donal, there are open and closed tours. You are referring to ''closed'' tours. There are no closed tours on boards of size 2 through 7 inclusive. --[[User:Dgamey|Dgamey]] 02:43, 3 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.
Line 73 ⟶ 78:
:: This shows a summary of results for 5 tries at each starting position:
<pre>Results of tests for N=7 :
Starting Square | a1 a2 a3 a4 b2 b3 b4 c3 c4 d4 *All*
*
RothTieBreaker | 70.00% 0.00% 70.00% 0.00% 90.00% 0.00% 80.00% 90.00% 0.00% 100.00% 50.00%</pre>
:: The notable thing about the pattern of failure in 7x7 is that tours started every other square fail and this shifts by one every rank. The symmetries of the squares above hold for all tie breakers and the overall pattern of failure is a cross-hatching. Like this:
<pre> a b c d e f g
+---------------+
7 | T - T - T - T | 7
6 | - T - T - T - | 6
5 | T - T - T - T | 5
4 | - T - T - T - | 4
3 | T - T - T - T | 3
2 | - T - T - T - | 2
1 | T - T - T - T | 1
+---------------+
a b c d e f g</pre>
::: Where T indicates that Warndsdorf/Roth found a tour and - indicates a failure to find a tour. A quick estimate of the number of paths to be test for an exhaustive search confirmed that would be impossible. I tried a number of searches to find references to unsolvable knights tours on 7x7 boards and found none. I find myself wonder if there are any solutions on any of those failed squares. --[[User:Dgamey|Dgamey]] 10:59, 6 June 2011 (UTC)
::: Running tours for all squares looking at the failed 7x7 start at a2 running 48 moves with a3 empty and all symmetries found no reverse paths either. --[[User:Dgamey|Dgamey]] 10:56, 3 June 2011 (UTC)
:: 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:
Line 89 ⟶ 111:
:: I'd be interested in seeing how others fare with a 7x7. --[[User:Dgamey|Dgamey]] 10:28, 2 June 2011 (UTC)
:::J:<lang j> ktourw 7
0 21 32 41 14 19 16
31 48 23 20 17 40 13
22 1 44 33 42 15 18
45 30 47 24 37 12 39
2 27 36 43 34 9 6
29 46 25 4 7 38 11
26 3 28 35 10 5 8</lang> --[[User:Rdm|Rdm]] 12:54, 3 June 2011 (UTC)
:::: Thanks. How are you breaking ties? Roth? (Also can you find a solution on 7x7 starting on a2? see above. --[[User:Dgamey|Dgamey]] 13:23, 3 June 2011 (UTC)
::::: I did not write this code. It is using the lowest index in the case of a tie. And this version failed when I tried to get it to find a 7x7 solution starting on a2 (index 1). --[[User:Rdm|Rdm]] 13:55, 3 June 2011 (UTC)
== C++ formatting ==
Line 106 ⟶ 140:
:::: I wasn't accusing anyone of anything, just stating why I'd done what I'd done. I don't want to see an edit-war either, so if it happens again, my first suggestion would be a community coding style. I know what my preferences are, but when I teach programming, I stress consistency over any one style, so I have no problem with the idea. (I'm just a TA, so don't take that as me trying to lend weight to my arguments.) If not a style guide, my second suggestion would be to not make purely stylistic changes to existing code. [[User:MagiMaster|MagiMaster]] 03:21, 2 June 2011 (UTC)
::::: Sorry if I sounded a bit short; most of my wiki edits are in a few spare minutes here and there, so after a few rounds of quick edits and rewrites, my prose can ultimately sound worse than it started... I'm familiar with the TA role; [[User:Mwn3d|Mwn3d]] is a former TA from RIT, and has been heavily involved with RC for three or four years, now. I think he suggested elsewhere following the model of [[J/HouseStyle]], as far as developing a community style. I'm beginning to see a need for that, I suppose; better to have the debate and discussion over style in one place, than in dozens of places. I suppose the C++ page would be at [[C++/HouseStyle]] --[[User:Short Circuit|Michael Mol]] 15:30, 2 June 2011 (UTC)
==Tiling smaller tours==
[https://gilith.wordpress.com/2013/02/20/large-knights-tours/ This] blog post by Joe Leslie-Hurd has a novel technique of stitching together smaller tours to make larger ones. Enjoy. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 06:28, 21 July 2015 (UTC)
| |||