Anonymous user
Talk:Knight's tour: Difference between revisions
m
no edit summary
mNo edit summary |
|||
| (8 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 83 ⟶ 86:
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)
Line 104 ⟶ 120:
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 121 ⟶ 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)
| |||