Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Science Hardware

No Magic In A Knight's Tour 278

Posted by Hemos from the brute-force-it-baby dept.
morgothan writes "As reported in an article on Math World the solution, or rather lack of solution has been found to the over one hundred fifty year old math problem of how many numbers of magic tours a knight can make on a standard 8x8 chessboard. It turn out that there exist one hundred forty distinct semimagic tours, but no magic tour. The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz, the project was completed on August 5, 2003 in which every possible enumeration was tried out. The author of the software that finally solved the problem has also put up a webpage in which he further explains the problem and his method of solving it." Thanks to Mig for pointing out a great background page on Chessbase.com.
This discussion has been archived. No new comments can be posted.

No Magic In A Knight's Tour More

No Magic In A Knight's Tour

Comments Filter:

  • Google Cache of the Web Page (Score:3, Informative)

    by Suhas ( 232056 ) on Monday August 18, 2003 @08:34AM (#6721610)
    is right here [216.239.57.104]

  • Magic Tours... (Score:3, Funny)

    by LordYUK ( 552359 ) <jeffwright821@noSPAm.gmail.com> on Monday August 18, 2003 @08:37AM (#6721623)
    Maybe if the Knight REALLY wanted to take a Magic Tour he'd consult a Wizard instead of a Computer...

    No wonder he didnt only got a Semimagic tour, damn you Travelocity! Damn you to hell!

  • Tired out (Score:3, Funny)

    by Gherald ( 682277 ) on Monday August 18, 2003 @08:37AM (#6721624) Journal
    The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz

    I bet the horse was tired after hopping around so much.

  • For our next experiment... (Score:5, Funny)

    by Black Parrot ( 19622 ) on Monday August 18, 2003 @08:38AM (#6721632)


    Now we're going to examine how many routes there are through all the bars in Amsterdam, and see if there are any "magic" routes that will let us complete the circuit without falling drunk in a bed of tulips.

  • That's nice, but not impressive (Score:5, Interesting)

    by Kombat ( 93720 ) <kevin@swanweddingphotography.com> on Monday August 18, 2003 @08:41AM (#6721650)

    Whatever happened to the classic style of problem-solving, whereby an actual proof was deduced, rather than simply employing brute-force to "count them all?" I mean, don't get me wrong, I'm glad that we finally have an answer to this pressing question (which I'm sure 95% of us had never heard of prior to reading this article), but does anyone else feel that these "brute-force" solutions are kind of cheating?

    • Re:That's nice, but not impressive (Score:5, Insightful)

      by forsetti ( 158019 ) on Monday August 18, 2003 @08:44AM (#6721665)
      Normally I agree with you -- however, if I have to chose between 150 years looking for a proof, or <150 days of brute force, I would have to admit that the brute force approach was better.....

    • Re:That's nice, but not impressive (Score:4, Insightful)

      by Jooly Rodney ( 100912 ) on Monday August 18, 2003 @08:45AM (#6721670)
      I haven't studied this particular problem much, but some theorems aren't susceptible to an elegant hand-proof -- one famous proof of graph 3- or 4-colorability (can't remember which) required the use of a computer to address thousands of cases and subcases.

    • Re:That's nice, but not impressive (Score:2, Funny)

      by Anonymous Coward
      Proof:

      Given: an 8x8 chess board, a black knight piece, a Cray supercomputer

      1. Execute brutechess.exe
      2. Therefore, there are no magic knight's tours.

    • Of course its cheating, but it does get the job done.

      And you are correct about there being more pressing questions, such as prime numbers! [mersenne.org] :-)

    • Re:That's nice, but not impressive (Score:4, Insightful)

      by 91degrees ( 207121 ) on Monday August 18, 2003 @08:47AM (#6721682) Journal
      I agree. They're highly unsatisfying. A proof would have told us how many routes there are for an arbitrary sized chessboard as well.

      • 8x8 a special case. (Score:4, Informative)

        by Goonie ( 8651 ) <robert.merkel@b[ ... g ['ena' in gap]> on Monday August 18, 2003 @09:03AM (#6721766) Homepage
        According to the article on Mathworld there is a general proof for boards bigger than 8x8, but 8x8 turned out to be a special case.

        Brute forcing to get a proof is better than no proof at all, but brute forcing a special case is even more acceptable.

      • Re:That's nice, but not impressive (Score:5, Informative)

        by iapetus ( 24050 ) on Monday August 18, 2003 @09:03AM (#6721768) Homepage
        A proof would have told us how many routes there are for an arbitrary sized chessboard as well.

        Not necessarily. As the article points out, there is a proof for certain sizes of chessboard, but it doesn't extend down to 8x8. Not all mathematical proofs are quite as neat as we might like them to be in terms of how they apply to other variants on the same problem.

        • Actually, as the article points out, there is a proof for ALL boards where boardsize > 2, EXCEPT for 8.

          It also points out that everybody who actually cared one bit about the problem had fairly well already decided that there was no solve for boardsize == 8. So, effectively, someone blew 50+ days of CPU time proving something that nobody really cared about, and determined an answer that everybody already knew.

          It's kind of like Microsoft Windows: The answer to a problem that no one really had.

    • Re:That's nice, but not impressive (Score:5, Insightful)

      by Progman3K ( 515744 ) on Monday August 18, 2003 @08:47AM (#6721686)
      Sure, but isn't a brute-force proof along with a mathematical proof even better?

      I mean this way we have one of the two, all that remains now is to turn the algorithm used into a formula for mathematical verification and there you have it.

      In a way, the algorithm used is ALREADY a mathematical proof, inasfar as an algorithm can be proven correct using math...
      • A pen-and-paper proof typically yields insights about the nature of a problem, whereas a brute-force solution often tells you nothing beyond the answer. Mathematicians usually want to know why something is true or false, and not just if.
        • OK, I'm with you there, but here's what I'm wondering:

          In Computer Science courses (university level, maybe before), you learn to take (some) algorithms and express them as mathematical formulas.

          Sums using sigma notation and whatnot, if you are familiar.

          So doesn't that mean that if you have the algorithm to solve the problem, you have the PROOF?

          Admittedly, it might be very difficult to translate the algorithm into a standard mathematical formula, but it should be possible, right?

          I am arguing that an alg

    • Re:That's nice, but not impressive (Score:4, Interesting)

      by zubernerd ( 518077 ) on Monday August 18, 2003 @08:49AM (#6721701)
      This is not the only problem to not have a "done by hand" proof, the four color map theorem proof (one version of it) was in part by done with a computer.
      http://www.math.gatech.edu/~thomas/FC/fourcolor.ht ml [gatech.edu]
      By the way, I couldn't help but to notice the quote at the bottom of the page (generated by slashdot)
      "Don't think; let the machine do it for you!" -- E. C. Berkeley

    • Re:That's nice, but not impressive (Score:5, Interesting)

      by JanneM ( 7445 ) on Monday August 18, 2003 @08:51AM (#6721710) Homepage
      Nah. A result is a result no matter what methods were used to produce it. No cheating.

      That said, there are arguments in favour of a classical proof as well. First, of course, is the matter of elegance; an elegant symbolic proof is a lot more pleasing than a brute-force approach (though an inelegant symbolic proof is as bad - or worse - than a method like this).

      Second, a theoretical proof is sometimes more interesting for the secondary results it produces and the new avenues of progress in other areas, rather than in the proof itself. This is generally lacking for brute-force methods.

      But in reality, these methods complement each other quite nicely. Knowing what the result should be, making an elegant classical proof of it becomes so much easier than before. And of course, you tend to need to know quite a lot about a problem (culled from classical methods) before you can formulate a prq'acticable brute-force approach.

    • Well, it's not a proof but it still gives us some insight: Now we can be fairly sure that there is no magic tour, so we can stop trying to prove the existence of one. This can be quite helpful. After all, there are people who spent years trying to fond (non-existent) counter-examples to the 4-colour theorem.

    • There are Godel/Turing-type results which imply that most mathematical truths are 'random' -- ie they don't have short/elegant/informative proofs.

      Build a combinatorial structure and ask some random question about it, and the odds are pretty decent you'll need to resort to brute force.
    • What exactly is the difference between proof aided by computer and a proof by just a human? Does he get to use a calculator, or does he have to do everything long hand?
    • I would say both would be nice. I believe a proof on paper still needs to be proved in practice.
    • One criterion for a good solution to a problem is that the proof allow you to establish the result more quickly than you could establish the result without the proof; it is easier to verify the proof that it is to generate it.

      This work merely demonstrates the result; it does not do so in a way that's faster to verify than it was to generate. In general, the proofs of open questions tend to involve work which extends related theories; proving Fermat's Last Theorem, for example, involved developing and relat
    • I like a nice elegant proof as much as the next geek, but brute-force answers are pretty much unarguable, where proofs require reasoning which may be flawed. Many "proofs" have stood for quite some time before someone else found an error in reasoning or logic.

      That said, any problem involving an infinite series of numbers pretty much require a logical proof, but a problem constrained to a chessboard is more analagous to "prove the quadratic theory is correct when a, b, and c are integers from 1 to 10."

  • Source Code snippets (Score:2, Interesting)

    by JamesP ( 688957 )
    Check this out...

    #define true 7361
    #define false 28456

  • Article on Chessbase (Score:5, Informative)

    by GeckoFood ( 585211 ) <geckofood@nosPAM.gmail.com> on Monday August 18, 2003 @08:44AM (#6721667) Journal
    There is an interesting [related] article on chessbase here [chessbase.com] about knight's tours. On the main chessbase page, they reference the main article involving magic tours.
  • I thought this was something about Cheesebase when I first saw it.

  • on FARK.com this would have the following header (Score:4, Insightful)

    by Ubergrendle ( 531719 ) on Monday August 18, 2003 @09:10AM (#6721808) Journal
    "Still no cure for cancer."

    Without trying to be too much of a Troll, can someone explain to me as a mathematical lay man as to why this problem has any significance? Given that a chess board is an arbitrary 8x8 set of constraints, is there anything that can be learned and applied to the real world (or even theoretical mathematics?) through solving this problem?

    Also, I was under the impression that the objective of mathematical puzzles like this would be to find a simple, elegant proof. Does a brute-force calculation approach carry as much weight?

    • Re:on FARK.com this would have the following heade (Score:5, Insightful)

      by Skater ( 41976 ) on Monday August 18, 2003 @09:22AM (#6721884) Homepage Journal
      You're right, the evidence has no mathematical beauty. Still, it's good to know what you're trying to do when you start writing a proof.

      Here's what I have to say about mathematicians (since I have a bachelors in mathematics): Most people would invent paint to cover a wall they have that's bare. Mathematicians would invent paint with no intended purpose, then later discover it could be used on a wall.

      Mathematicians frequently create for the sake of creation, rather than for any specific purpose.

      --RJ

    • I am trying not to be too negative here, but why should everything have to have a significance to the real world? The world doesn't benefit from me solving a crossword puzzle. It's just me, wanting to know the solution to the puzzle.

      In the same way, people have been puzzled by the magical knight's tour problem for 150 years. And someone finally has solved the problem. It might not provide a cure for cancer, but at least it entertained a few people for some time.

      Maybe something as insignificant as that s

    • Re:on FARK.com this would have the following heade (Score:5, Insightful)

      by reverseengineer ( 580922 ) on Monday August 18, 2003 @12:00PM (#6723000)
      Well, this initially doesn't sound like a very serious problem- I mean, so, you're taking the fairly simple and well-worn problem of finding a knight's tour on a standard chessboard, and throwing in the rather odd constraint that the path has to create an 8x8 magic square. An oddity produced by the rules of chess (trying to fit L-shaped moves on a square board makes finding a knight's tour obviously more challenging than finding a queen's tour) meets an ancient mathematical curiosity. Viewed that way, this problem seems entirely pointless.

      However, try and think about what this problem really is mathematically, rather than in terms of chess or magic squares. A knight's tour requires the knight to visit every square on the board exactly once. Replace "squares" with "nodes," and "board" with "graph," and what we have here is the problem of finding a Hamiltonian path with some interesting constraints.

      And that's where this problem gets interesting- finding a Hamiltonian path on a graph is known to be NP-complete, a designation which carries with it all sorts of baggage, including some of the million-dollar sort. [claymath.org] The fact that the question of whether magic knight's tours exist on an standard 8x8 board required 60+ CPU-days to answer speaks volumes about the complexity of the problem, and demands answers as to how this complexity comes about, and why there is no solution with the given constraints. Far from being just a silly mathematical curiosity, this is a problem that presents a lot of potential applications with regards to algorithms, complexity, and computability. Also, if you can find an algorithm that finds Hamiltonian paths in polynomial time, you get the aforementioned free money. [claymath.org]

      So yes, the problem of finding a magic tour seems worthless if you only consider the problem literally in terms of a chessboard and magic squares, instead of as a model for other complex problems in mathematics, science, and engineering. But by the same token, how interesting and useful would the Traveling Salesman Problem [wolfram.com] be if it were only applied to traveling salesmen?

  • A pedantic geek says . . . (Score:5, Funny)

    by droleary ( 47999 ) on Monday August 18, 2003 @09:12AM (#6721822) Homepage

    The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz

    Yeah, and I came to work in 12.34 horsepower-hours, corresponding to 666.13 hours of driving at 5K RPM. I mean, damn, I understand when my mom utters movie-level technobabble, but this?

  • 1GHz WHAT? (Score:4, Insightful)

    by JessLeah ( 625838 ) on Monday August 18, 2003 @09:18AM (#6721859)
    The story uses CPU-hours "at 1GHz" as a unit of measurement.

    Guys, please, this is SlashDot. A 1GHz G5 is not the same as a 1GHz Duron is not the same as a 1GHz P3. What sort of 1GHz chip is being referred to here?

    • Re:1GHz WHAT? (Score:5, Funny)

      by edwinolson ( 116413 ) on Monday August 18, 2003 @09:42AM (#6721969) Homepage
      Oh please. Next you'll want to know the exact DRAM configuration. Was it DDR? How big was the L2? Was the data set swapped out to a 7200rpm hard disk or a 10k rpm disk?

      Good grief. It's just an estimate. It's not the exact compute time that's interesting. It still tells me the interesting bits-- that it was a complexity that an ordinary PC could do in a reasonable time frame, not the sort of thing a gigantic cluster chewed on for 100 years.
    • The ones they use at the Library of Congress of course!
    • 61.40 CPU-days = 138.25 1GHz CPU-days, hence they must have been using 2.2 GHz CPUs.

      OR

      1 billion cycles per second for 138.25 days = 86,400,000,000,000 cycles (8.64 x 10^11 cycles, right?)

      Which on my computer would take, hmm... 3 1/2 years if I turn kpp off.

  • on the value of horse problems (Score:3, Insightful)

    by falsemover ( 190073 ) on Monday August 18, 2003 @09:27AM (#6721901)
    a wise man once said :- "behind a lot of great solved problems is a totally useless result; the value therein lies not in its outcome but in the solution methodology and how it applies to the attainment of other results, some of which will be a trifle more interesting"

    who also said

    "never buy of the horse that is overridden as it will fetch less at the clackers"

  • Is math dying? (Score:4, Interesting)

    by 3Suns ( 250606 ) on Monday August 18, 2003 @09:30AM (#6721919) Homepage
    It seems to me that more and more math problems are being approached in a brute-force, computerized way. While this is certainly a legitimate way of finding answers to a problem, aren't we missing the point of these problems by using it? It's not like anyone was really waiting on the answer to that problem. It's such a lazy disappointing answer to an exciting mathematical question: "Are there any magic knight tours on an 8x8 chessboard?" "Nah, I tried 'em all out, see." Are we seeing the death of "clever" mathematics where a simple elegant solution is found, correlating known theorems in novel ways that enhance our collective understanding of the way math works?

    Now before you object, I am aware of really nifty, clever mathematical breakthroughs in recent memory. The recent polynomial-time primity test comes to mind. But what is the point of "research" and "inquiry" if we only care about the answers to the problem, and not the reason why? What is the point of finding the next Optimal Golomb Ruler" [distributed.net] if we can't find a pattern relating one to the next? What would we really do with a magic knight's tour anyway, besides reading a clever and insightful proof of it's (non)existance?

    Even a computerized proof would be interesting, if a method for proof-solving on computers were possible. And yes, it is possible to write proof-solving software that is at least as good as a human mathematician without upsetting Mr. Godel. But this brute-force type proofing is just plain dull!

    • Re:Is math dying? (Score:3, Insightful)

      by Fungii ( 153063 )
      To be honest, I'm pretty surprised to see all the "Is Math dying?" or "This isn't real maths" type comments here on slahdot.

      I would have thought that the slashdot crowd would be the first group to realise that computers are an excellent aid to mathematics. Not every maths problem can be solved by hand, and there is often quite a bit of inginuity involved in these computer soloutions.

      I see comments like this as people being afraid of technology - The computer can potentiall be one of the mathematicican'

      • Re:Is math dying? (Score:3, Interesting)

        by 3Suns ( 250606 )
        Did you even read what I wrote? Let me reiterate:

        Even a computerized proof would be interesting, if a method for proof-solving on computers were possible. And yes, it is possible to write proof-solving software that is at least as good as a human mathematician without upsetting Mr. Godel. But this brute-force type proofing is just plain dull!

        My problem is certainly not with computers, which I agree are a huge aid to mathematics. Suites like Mathematica etc. are tremendous tools, visualization method

        • The brute-force proofs, whether you do them by hand or computer, are like saying you know how to drive because you can call a taxi.

          I'd say it's more like driving to the airport and taking a private jet. Sure, it doesn't involve much of driving skill, but you can get to places that are impractical or impossible to drive to. And even if you don't know how to drive, you (hopefully) know how to fly.

    • Re:Is math dying? (Score:2, Interesting)

      by entartete ( 659190 )
      it does provide data for people to look at and possibly derive some insight out of, probably not about anything relating to knight's tours or whatever. just like how many insights into the way things work come from observing nature i think that it's possible to find a few nuggets of gold hidden in amongst all the reams of data. wolfram's early cellular automata work was based pretty much off of brute forcing simple systems and then taking things from there. but in general i agree with you, the solution of
    • Fear not. Many if not most interesting mathematical problems are of the form "Is there an x in an (infinite) set S having a property P?".

      Of course if such an x doesn't exist, you cannot solve this by applying brute force directly. You have to put some minimum of creative thinking into transforming such a problem into a finite case (as it was done in case of the 4-coloring problem).

    • And, what's the point of finding -any- Golomb Ruler? All the explanation I've seen basically says "this is for fun, there's no real use" .. well, my CPU time is better used HLTing rather than playing with distributed.net on that problem...

  • Cheers (Score:2, Funny)

    by Anonymous Coward
    Put my mind at rest.. I've been worrying about this for years.

  • Ahh the memories... (Score:2, Interesting)

    by heneon ( 570292 )
    I remember when in school and army I used to kill time doing this. I had a notebook with pages upon pages filled with 6x6, 8x8 and 10x10 matrices and numbers all over them. The smaller ones were easier because you could calculate more moves in advance. I have never realised that this could be an "official sport" with a chessboard.

    Many years ago I saw some guy doing a kinght's tour blindfolded on tv. I thought that was amazing, he must have calculated every move after he was given the starting square. But

  • For those of you who can't be arsed with the links (Score:5, Informative)

    by jonathan_ingram ( 30440 ) on Monday August 18, 2003 @10:03AM (#6722079) Homepage
    A knights tour involves moving the knight onto every square of the chessboard without repeating a square (being a knight, it is of course allowed to jump over squares it has previously landed on).

    A magic square is a square grid, with each grid position numbered, such that the horizontals, verticals, and diagonals all add to the same number (you can also ask for all the broken diagonals to add to this number, but this doesn't have to hold in a basic magic square).

    If we number the knight's initial position 1, and increment with every jump, then a knights tour gives us a numbered n by n square (8 by 8 in the case of a normal chessboard).

    The question: are there any knights tours which give us a magic square after we perform this numbering operation?

    The answer: no, although there are many tours which give us a 'semi-magic' square (where the horizonals and verticals, but not the diagonals, give us the same sum).

    The point: although magic squares have a variety of surprising uses, there seems to be no 'point' to the magic knights tour question other than another line in the book of 'solved minor problems' -- but if it's enough to write a paper on, then you can bet you'll be able to find a graduate student to do it :).

  • A chess article without Go mentioned? (Score:3, Funny)

    by Thinkit3 ( 671998 ) * on Monday August 18, 2003 @10:12AM (#6722147)
    Is this a /. first? Well I won't let it happen. Hey, screw the magical knight tour, how about solving 9x9 Go?

  • Sure he can... (Score:5, Funny)

    by cactopus ( 166601 ) on Monday August 18, 2003 @10:15AM (#6722186)
    Sir Paul McCartney did make a Magical Mystery Tour

  • Brute force--Bring it on! (Score:5, Interesting)

    by Unknown Kadath ( 685094 ) on Monday August 18, 2003 @11:18AM (#6722664)
    I've been seeing a lot of comments disappointed with brute-force problem-solving--but I am all for it. Here's why:

    In my job, I do fine structural analysis and computational fluid dynamics for aerospace design. Aerospace engineering is rapidly reaching the point where simplified, elegant models are inadequate to the real-world structures they are meant to mimic. For instance, the Navier-Stokes equations, a set of second-order partial differential equations which describe fluid flow, are not susceptible to analytical solution in any but the most simplified cases, and as things like airfoils, turbine blades, and computers grow more refined, their properties require much hairier math to describe. Turbulent flow around a wing or turbine blade has no elegant solution, but a brute-force computational model can yield a solution that allows us to design a lighter wing, and thus a more fuel-efficient plane, or a stronger turbine fan, and a more efficient generator. Or, to cite an example near and dear to many slashdotter hearts, as we can better model the heat transfer inside a microprocessor, we can better devise ways to cool it, and thus build a faster, more stable computer. (And then, we can solve more iterations on it, and build an even faster computer...and then we can solve more iterations... ^_~)

    There is an intense intellectual satisfaction to a 20 or 100 line proof (I still remember the triumph of my high school proof that a triangle's interior angles sum to 180), but for a lot of things, there simply exist no such proofs. As we tackle more and more mathematical problems, those with relatively simple proofs will quickly be solved and set aside, and we will move on to messier things. For instance, the proof of Fermat's Theorem runs to several hundred pages of dense elliptic curve math. It was an aesthetic disappointment for those hoping for a simpler solution, but it was a triumph for the field of mathematics as a whole.

    There is a whole 'nother world of proofs involved in brute-force solutions. Estimated time to solution, order of error--elegant mathematical tools are still necessary, but they are increasingly used to delineate regions of uncertainty as the complete picture becomes messier. The closer mathematical models get to the real world, the more complex and beautiful, but the less elegant, they become. I do not think that the field of mathematics will stop producing elegant proofs, but I do think they will have less and less to do with the world we live in and more and more to do with hypothetical mathematical constructs, whose usefulness will then filter down in the form of special cases to more prosaic disciplines, like science and engineering. This diminishes neither science nor engineering, and adds to the knowledge available in all fields.

    -Carolyn

  • Topical Fiction (Score:3, Informative)

    by ThinkingHurts ( 699218 ) on Monday August 18, 2003 @11:59AM (#6722994)
    Anyone interested in a great read involving chess, magic squares, knight's tours, acoustics, fibonnaci numbers, the French revolution and the 1970's programming scene, check out The Eight [amazon.com] by Katherine Neville. Just finished it for the third time, and discovered the the last two years of my daily /. education helped me to appreciate and enjoy it even more. I apologize in advance for the amazon link; it was the only site that gave a decent balance of reviews.

Slashdot Top Deals

THEGODDESSOFTHENETHASTWISTINGFINGERSANDHERVOICEISLIKEAJAVELININTHENIGHTDUDE

Close