Talk:Knight's tour

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Discrete mathematics
This article is within the scope of WikiProject Chess, a collaborative effort to improve Wikipedia's coverage of chess. For more information, visit the project page, where you can join the project and/or contribute to the discussion.
Chess Portal
B This article has been rated as B-Class on the quality scale.
High This article has been rated as High-Importance on the importance scale.

Contents

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)