Talk:Knight's tour

Trivial 1x1 closed tour?

"A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began" But there are a few references to the trivial case of a closed tour on a 1x1 board. I would say that a knight can not attack any square on a board smaller than 2x3, and therefore can not complete a closed tour. — Preceding unsigned comment added by 76.251.81.253 (talk) 19:49, 15 October 2011 (UTC)

I agree. There can't be an open or closed tour on a 1x1 board, so the sloane number must be changed to T=0 for n= 1. The word tour implies that some movement has been established. 99.135.167.202 (talk) 00:06, 23 September 2013 (UTC)

There is no connection between tour and movement. Tour here simply refers to a Hamiltonian path or cycle on the knight's graph, while for the 1x1 board this graph is a singleton graph which is considered Hamiltonian (i.e. having a Hamiltonian cycle) -- see http://mathworld.wolfram.com/SingletonGraph.html Maxal (talk) 02:46, 23 September 2013 (UTC)

Please don't be so quick to judge my observation. When was the last time anyone ever toured without leaving from the place they started. I'm trying to understand the knight's tour from the most basic and objective viewpoint, and I disagree !!tremendously!! with you for having quoted something from mathworld. They don't review new ideas. I've asked them.99.135.166.191 (talk) 23:26, 8 October 2013 (UTC)

Think of "touring without leaving from the place they start" as an empty tour with no movements. This is similar to how sets may have no elements etc. Maxal (talk) 01:16, 9 October 2013 (UTC)

I agree with Maxal. Similarly, what is the sum of zero numbers? 0. What is the product of zero numbers? 1. Bubba73 ^{You talkin' to me?} 02:30, 9 October 2013 (UTC)

Across the Board Citation

Will someone please cite Across the Board properly in the bibliography and point the Schwenk's theorem section to the same reference? I am too inexperienced/lazy-to-find-out-how to do so. Leon math (talk) 22:15, 8 December 2008 (UTC)

OK, I did it, assuming that the theorem is in Watkins. (I don't have the book.) Bubba73 (talk), 23:13, 8 December 2008 (UTC)

Thanks, it is. Leon math (talk) 00:44, 9 December 2008 (UTC)

Define Directed?

I read this page and have no idea what "Directed" and "Undirected" mean. They are used but not defined. Could someone please add a definition? —Preceding unsigned comment added by Spril4 (talk • contribs) 04:18, 14 February 2008 (UTC)

Added links from "directed" and "undirected" to Glossary_of_graph_theory#Direction. Alexdow (talk) 20:11, 24 March 2009 (UTC)

Conrad

For the paragraph regarding Hamiltonian paths, can someone correct the Conrad link? I'm not sure of what it refers to. --Ricky81682 09:04, Nov 27, 2004 (UTC)

Done, we don't have an article about that particular mathematician. Btyner 22:36, 28 May 2006 (UTC)

TODO?

What is the TODO for condition #3? Jumping cheese ^Cont@ct 06:54, 15 November 2006 (UTC)

TODO means that there is still something to do in that section, which is true because we still have more to put for Condition 3. I'm not sure if it's good Wikistyle, but I've seen it on other articles.

oops, forgot to sign, Leon math 21:32, 17 November 2006 (UTC)

Schwenk's Theorem

Edit: I overlooked the word "closed" knight's tour. Tobias Pfanner 13:07, 17 December 2006 (UTC)

I suppose it does need to be made clearer that Schwenk's Theorem only holds for closed knight's tours. Does anyone agree?Leon math 20:56, 18 December 2006 (UTC)

Proof

The article astutely observes, in the last section, that "Simply proving the above three conditions does not prove the theorem, it is still required to prove that all rectangular boards that do not fall in one of the above three categories have knight's tours." But, uh, where's the proof? Solemnavalanche 15:52, 11 January 2007 (UTC)

Not every page with a theorem has the complete proof of it, as this would often make it ridiculously long and rather formidable. Perhaps someone with access to Schwenk's proof can judge whether it is appropriate for Wikipedia. Leon math 22:50, 11 January 2007 (UTC)

giving half the proof leaves the reader (like me) eager to read the other half, so at least give a link (external) with the rest of the proof or a reference where the proof can be found —Preceding unsigned comment added by 62.1.238.203 (talk) 02:05, 27 April 2008 (UTC)

Number of tours

The article states that the number of non-closed tours is "billions" and the number of closed tours is about 122,000,000. It seems to me, from reading Sloane, that the number of closed tours is 13,267,364,410,532, which is considerably more than "billions", let alone 122 million. Where does the figure 122 million come from? I'm going to change it to the Sloane figure, but I'm posting here first because the 122 million figure has been around for a while (June 2003) and I'm hoping Camembert or someone else will respond. Adam1729 21:08, 6 April 2007 (UTC)

I see from the page history that it was I who added the 122,000,000 figure, but I'm afraid to say I don't remember what my source was (very shoddy of me not to include it with the edit, I know). This comment states that the figure appears in the Oxford Companion to Chess, and so I suppose this is where I would have pulled it from; however, when I look at my own copy (2nd edition, 1996), I find it says "There are countless ways of achieving this, and about 8,000,000 ways of performing the more restricted version known as a re-entrant tour in which the knight, on its 64th move, could arrive back at its starting square". Perhaps the 122,000,000 figure appears in the first edition (which I think is the one I would have had at the time of the edit), though in that case the fact that the number went down in between editions makes the enormous difference between it your 13 trillion-and-odd all the more puzzling (I don't believe that there has been a third edition, by the way).

I'm far from an expert on this sort of thing, so if you have confidence in your figure, I'm certainly not going to argue with it. I do think, though, that we should be sure of citing a source for it (or for whatever other number ends up in the article), thus correcting my earlier mistake. Best--Camembert 14:28, 11 April 2007 (UTC)

Just a quick PS: if this is the entry in Sloane that you're referring to, I'm a little confused by it; the comment that "No closed tour exists on an m X m board if m is odd" certainly suggests that the figure refers to closed tours, but the heading just states "Number of knight's tours on a 2n X 2n chessboard" which to me means the total number of all tours, not just closed ones. Are we sure that figure is really referring just to closed tours? --Camembert 14:44, 11 April 2007 (UTC)

Yes, that's the entry, and I agree it's not completely clear. It claims "Loebbing and Wegener give 33,439,123,484,294 for the 8 X 8 board. The value given here is due to B. McKay and agrees with that given by Wegener in his book.". Reading Loebbing and Wegener gives the figure 33,439,123,484,294 (closed, undirected), but it also claims that it's wrong, because 33,439,123,484,294 is not divisible by 4. It seems to me that the Sloane page is saying that 13,267,364,410,532 is the corrected figure for 33,439,123,484,294, and is therefore the correct number of closed, undirected 8x8 knight's tours. Wolfram's Mathworld agrees with the 13,267,364,410,532 figure, and they cite [Wegener, I. Branching Programs and Binary Decision Diagrams. Philadelphia, PA: SIAM, 2000] which is a book [ISBN 0-898-71458-3]. I don't have the book, but at this point I think we've got enough verifiability, so I'm going ahead. Until a wiki-author reads that book, I think we don't know the number of non-closed tours. Mathworld simply quotes the figure from the paper which gives the wrong figure for the number of closed tours, which must be highly suspect. Adam1729 07:23, 12 April 2007 (UTC)

According to British convention, those numbers are in the 'billions'. Leon math (talk) 22:12, 8 December 2008 (UTC)

Merge

All right, no one's said anything, I'm making the merge with Warnsdorff's algorithm now. Leon math (talk) 00:30, 28 January 2009 (UTC)

I would just point out that Warnsdorf spelled his name with one f not two. See the link to his 1823 book. This is a persistent error in the literature. I did change it years ago but it has been reverted to ff. I now hesitate to do so again. GPJ.

Variations section

It looks like the recent editor of this section put in a lot of effort, which I applaud. But... what does it really contribute to the article? I guess it shows that it's possible to have an irregular (non-rectangular) board, but it doesn't give a knight's tour across the given board (which is the subject of our article). Oh, and it's completely unreferenced. If no one objects, I will clean up. Dmitry Brant (talk) 10:57, 20 April 2009 (UTC)

Okay, I have removed the recent edits that have added nearly 25KB of irrelevant source code (and console output!). WP is not a repository of code; one implementation of the knight's tour in C is more than enough. Dmitry Brant (talk) 11:52, 21 April 2009 (UTC)

k...i'll include comments bout the adds to "Variations" w the hope it helps others understand it and prevents any fut unnec editing...

i'm a cryptic here, but pls bear w me...

1. "irrelevant source code (and console output!). WP is not a repository of code" ... um actually, the entire Knight's Tour prob and sol is nec & admittedly algorithmic in nature...the obv tool to bring to bear in sols is the computer...unless u want to support args that we revert to an 18th cent scrivners treatment.

2. all probs and sols up to "Variations" a) involve only C and Java code (not a more modern C# implementation), b) imply no hint of a recursive sol in the det of move seqs, which is often argued as the more elegant and, when properly implemented as here, the most efficient form of sol and c) doesn't deal w the generic prob of a Knight's Tour...specifically doesn't mod or chg the move env or board and doesn't add any specific conditions on the move env or board vis-a-vis standard acceptable Knight Moves

my adds to "Variations" of the Knight's Tour address 1. and 2. and include an added bonus of a hash code treatment in sol which turn out to be much quicker than a "game board" or quasi "mapped" approach of sol...i'v provided the code...u can test for urselves.

all adds to "Variations" r based entirely on my own work and thus properly refed as such...3GHef. —Preceding unsigned comment added by 3ghef (talk • contribs) 23:05, 23 April 2009 (UTC)

Then you should especially read WP:OR and WP:VERIFY. Your own work is not allowed. Also please read Wikipedia policies WP:What Wikipedia is not, WP:NOTE, and Wikipedia:Wikipedia is an encyclopedia. Bubba73 (talk), 01:16, 24 April 2009 (UTC)

Wikipedia is not about showing off "your own work." If your algorithm appeared in a respected publication (and if it were original), that would be a different story. This article, as it is, does a fine job of explaining what a knight's tour is, and how to solve it using two common programming languages. (The source code in the article is based on algorithms that appear in textbooks). This isn't a competition to see who can write the most efficient or "elegant" solution. If you find an algorithm in a textbook or a respected journal that is fundamentally different from our C and Java solutions, then by all means add it to the article. Your C# code, aside from being unpublished, is extremely convoluted and unhelpful in generalizing a hamiltonian path. There's nothing about it that belongs in the article. Dmitry Brant (talk) 10:59, 24 April 2009 (UTC)

Poor code examples

Who wrote the sample code to solve the knight's tour? I don't think Wikipedia is a good place to publish beginner's code, and the sample is pretty bad. 165.189.101.177 (talk) 21:09, 4 June 2009 (UTC)

If it was written by an editor it shouldn't be in the article because of wp:rs. Code should be from a published reliable source and cited. Bubba73 (talk), 21:56, 4 June 2009 (UTC)

May I suggest this online sample? Okkay (talk) 03:25, 16 September 2012 (UTC)

Improved Animated Image

In the course of my personal nonsense regarding this problem, I made a pretty dang sweet animated SVG image of the Turk tour. I am willing to give it a public domain dedication.

http://www.fsdev.net/attachments/10/turk.svg —Preceding unsigned comment added by FSDEVcmiller (talk • contribs) 09:01, 7 November 2009 (UTC)

Unfortunatelly, Wikipedia doesn't support animated SVGs. Could you convert it to Ogg Theora or animated GIF? (If don't know how, I could try to find out how to do that.) After that, you can upload it to Wikimedia Commons. You can choose one of the allowed licences or release it into public domain. Svick (talk) 12:24, 7 November 2009 (UTC)

Unfortunately it looks like the smooth movement of the Knight piece along its path makes it impractical to convert to a GIF. So it looks like we'll just have to shelf the idea until policies change (which should happen when more browsers support SVG - it doesn't use SMIL, only a generic SVG 1.1 animation motion, so it isn't hard to render. Increased browser support should be in the near future.

--FSDEVcmiller (talk) 00:28, 8 November 2009 (UTC)

4x4

It's said here there isn't any tour if shorter side is 4, so what with 4x4 square? —Preceding unsigned comment added by 79.191.120.75 (talk) 15:57, 9 May 2011 (UTC)

" No tour on 4x4. Bubba73 ^{You talkin' to me?} 16:49, 9 May 2011 (UTC)

Schwenk algorithm?

The partial proof of the Schwenk algorithm seems out of place to me - lots of detail in the middle of a survey article. What do others think? — Preceding unsigned comment added by 2.24.222.110 (talk) 19:06, 7 May 2012 (UTC)

Agreed. Removing. 2.29.5.216 (talk) 18:36, 5 August 2012 (UTC)

Turk's tour is closed?

It seems to me that the tour given by "The Turk" is not closed. The square f3 is not reachable from h7 by a knight's move. I am removing the "closed" comment. Kingsindian (talk) 20:49, 9 December 2012 (UTC)

It looks like it starts and ends on d4, which is closed. Bubba73 ^{You talkin' to me?} 21:48, 9 December 2012 (UTC)

Sorry for the delay. It does start and end on d4, but one move is illegal (from f3 to h7) Kingsindian (talk) 16:56, 21 December 2012 (UTC)

I can see somewhat where the confusion has come. The arrows on the knight's tour are wrong. The tour starts at f3 and ends at h7 (or vice versa). It does not start and begin at d4. I propose that the arrows be changed, or the image itself be deleted.Kingsindian (talk) 17:13, 21 December 2012 (UTC)

No, the diagram is OK. It goes from f3 to g5 and then to h7, which is in a straight line, so there is no corner in there. The diagrammed tour can't start on f3 and end on h7, otherwise it would never go to g5. It gets g5 between f3 and h7. Bubba73 ^{You talkin' to me?} 17:34, 21 December 2012 (UTC)

Ah you're correct. Kingsindian (talk) 17:56, 21 December 2012 (UTC)

It would help if the diagram had a dot on g5. Bubba73 ^{You talkin' to me?} 18:02, 21 December 2012 (UTC)

no knight's tour for NxN size boards, N is odd

Is it possible that after N*(N-3) moves that either no ties can be broken, or that an alternate tour cannot be chosen when applying Warnsdorff's rule (succesively) to a board of NxN size where N is odd? 99.135.166.138 (talk) 02:52, 12 October 2013 (UTC)

Sanskrit poem

The poem in the History section is fascinating. What does it translate to in English? --Rosekelleher (talk) 12:40, 22 November 2014 (UTC)

A talk by Knuth goes into a bit more detail of the Sanskrit Poems (called 'Shlokas') - https://www.youtube.com/watch?v=DjZB9HvddQk

I was under the impression that Knuth was the one who discovered these Shlokas for the first time, but the wiki page doesn't mention it. It references some Sanskrit book, but _Who_ found this reference? Was it Knuth?

dufferZafar (talk) 05:32, 14 August 2018 (UTC)

Backtracking

Should backtracking be mentioned? It's not the best solution, but it's not rock bottom, and it comes up in class assignments (or did). "Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated" --Rosekelleher (talk) 13:46, 22 November 2014 (UTC)

Citation needed for allegedly impractical brute force approach

I've asked for a citation for the claim that a brute force approach is impractical except for the smallest boards, as this claim is unsourced, and seems very dubious based on my own experience.

In the late 1980s or early 1990s, just for fun (and/or because I had been told that Erwin Schroedinger had found a solution manually within about an hour during World War II), I tried writing a brute force knight's tour algorithm for a standard 8 x 8 board starting on one of the 4 middle squares and ending on one of the remaining 3 middle squares (I can't remember whether it was one of the 2 neighboring squares or the diagonal one). I was using Nixdorf Business Basic on a Nixdorf mini-computer (probably an 8870, but possibly a Quattro). It was taking ages but from its behavior on screen it was clearly wasting lots of time searching areas of the board from which it had already cut off its only exit. I worked out how to fix this (which took perhaps 15 to 30 minutes - and obviously I can no longer remember the precise details of the fix a quarter of a century later - but it is probably not be too difficult to code 'Is there still an exit from this area of the board?' with at least moderate efficiency). It then started churning out new knight's tours at a rate that I think was slightly faster than one a minute. Unfortunately I then deleted the program as it was proving too much of a distraction from work. (Anybody who wants to try that out for him/herself is welcome to do so).

Clearly none of this can go into the article as that would violate WP:OR. But it does strongly suggest that the current unsourced text is unverified, highly questionable, and seemingly needs a citation from a Reliable Source and/or a modification/rewording. Tlhslobus (talk) 07:59, 11 February 2015 (UTC)

Clarifying Footnote: After giving it a bit more thought, the above still-brute-force-but-less-ignorant technique can be more precisely described as follows:

• -All squares are numbered, 1 to 64 (or 0 to 63) in the case of a standard 8 x 8 board (I use 1 to 8 for the bottom row, left to tight, then 9 to 16 for the next row (also left to right), and so on)
• -Paths are then lists of such numbers such as 28-11-1-18-3-9-19-2-17-27-10-4-14-8-23-6-12-22-5-15-21-31-16-X (X=dead-end)
• -In the above example (the 'lowest' available path if we start at centre square 28), 16 is a dead-end.
• -Using pure brute force and ignorance, the next lowest path would be 28-11-1-18-3-9-19-2-17-27-10-4-14-8-23-6-12-22-5-15-21-31-37, as the options from 31 are 14 (already used), 16 (now rejected as a dead end), 21(already used), 37, 46, and 48. The still-brute-force-but-less-ignorant approach is to deem 31 a failure if any of the available squares (in this case 16, 37, 46, 48) is a dead-end (unless this is the second last move, as the final square will always be a dead-end). Here 16 is a dead-end, so the move to 31 is rejected, and we go on to try the next lowest available path, which is 28-11-1-18-3-9-19-2-17-27-10-4-14-8-23-6-12-22-5-15-21-38...
• -As mentioned earlier, starting at 28 and programmed to end at either 29 or 37(I can't remember which, but it's just a matter of adding a rule banning going to one of them until move 64), back around 1990 this technique churned out new knight's tours at about one a minute on a mini-computer.
• -Note that this is still a brute force technique - it tries every available path until that path is shown to have failed. The only slightly unusual bit is that the test for path failure is slightly intelligent, although still 'obvious once it's pointed out' and requiring no sophisticated maths. In principle it allows you to find all available Knight's tours from any given starting point, sorted into ascending path order, though there is presumably not enough time to find all in practice, though at least with the above-mentioned starting conditions there's plenty of time to find many Knight's Tours. Also, unlike Warnsdorff's rule, the technique doesn't have to worry about what to do in the event of two seemingly equally valid paths (as it just tries the lowest available path until that's found to fail, then tries the next lowest, and so on). So even a complete ignoramus like me can successfully program it.
• -But as already mentioned, all this, being OR, can't go into the article text, and is just here as a clarifying footnote for the benefit of anybody who wants to test for themselves that our current unsourced claim that brute force techniques are impractical really is an implausible claim requiring an RS citation and/or a text amendment. Note: there is a source at the end of the statement, but, besides not being a Reliable Source (though its >10^51 result is similar to my estimated 4x10^54, so I won't quibble with it, though of course almost all of these paths would never be reached, being extensions of shorter paths already deemed failures early on), it merely says there are lots of Knights Tours, it doesn't say that brute force is an impractical way of finding a Knight's Tour (rather than perhaps all Knight's Tours, and I'm not sure that it's even saying that, and I'm also not sure that there are any practical techniques for finding all Knight's Tours).Tlhslobus (talk) 21:19, 11 February 2015 (UTC)

The issue now seems adequately dealt with thanks mainly to David Eppstein's excellent new citation. Thanks, David. Tlhslobus (talk) 20:49, 12 February 2015 (UTC)

Expanding the article

The article is generally pretty vague and incomplete and should be expanded with more information. To the "external pages" section I added a complete (probably the most complete) study on the knight's tour, so it can be taken into consideration to expand the article. Other links and books may be suggested if I'm permitted to do so. Luisa Valencia (talk) 18:56, 8 October 2016 (UTC)

Knight's games

There are some new contributions having to do with games involving knights. These do not seem relevant to the knight's tour problem, so I plan to delete them on my next editing pass. Open to discussion here.

Deleted as irrelevant. — Preceding unsigned comment added by 91.110.143.77 (talk) 19:25, 2 August 2020 (UTC)

Restoring sections for now until we can discuss whether the variations are truly irrelevant; they appear to be based on the Knight's tour and I'm not sure where else these sections could fit on WP. Are they truly irrelevant? Myoglobin (talk) 16:36, 10 August 2020 (UTC)

These sections on games have nothing to do with the knight's tour, which is not a game but a problem or puzzle. They are about games that involve knights and other chess pieces and so belong in Chess variant. Deleting. 95.149.237.145 (talk) 12:43, 1 November 2020 (UTC)

A Commons file used on this page or its Wikidata item has been nominated for deletion

The following Wikimedia Commons file used on this page or its Wikidata item has been nominated for deletion:

• Euler knight tour semimagic square.svg

Participate in the deletion discussion at the nomination page. —Community Tech bot (talk) 20:07, 1 August 2022 (UTC)

Starting position

Is it possible to correctly predict, the end possition or the Knight, when you know the starting position? 148.252.147.133 (talk) 19:46, 28 October 2024 (UTC)