Slashdot Mirror
No Magic In A Knight's Tour
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.
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.....
10b||~10b -- aah, what a question!
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.
I agree. They're highly unsatisfying. A proof would have told us how many routes there are for an arbitrary sized chessboard as well.
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...
I don't know the meaning of the word 'don't' - J
You're wrong...but don't feel bad. Lots of people make this mistake. Assuming the 'host' always opens one of the remaining doors and the remaining door never has a prize behind it, you should always switch. Why? On your first pick you have a 1 in 3 chance of getting the prize. If you always switch, your chance of getting the prize becomes 2 in 3. Prize -> Goat Goat1 -> Prize Goat2 -> Prize Thus, you win. or, to put it another way... Imagine there are 1000 doors and after picking a single door (1/1000 chance of getting the prize) the host opens all but 1 door. Would you switch? Of course! At that point there's a 9999/1000 chance you will win!
"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?
John Maynard Keynes: "When the facts change, I change my mind. What do you do?"
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?
Honey, I shrunk the Cygwin
\ 1 2 3
A y n n
B n y n
C n n y
The top row is the door number, the letters are the three cases, y means 'yes' (location of prize), n means 'no'. Suppose you chose door #1. In case A he'll show you door 2 or 3, in case B he'll show you #3, in case C he'll show #2. Only in Case A will you win by sticking with it. Case B and C you'll win by switching. That's 2/3 chance of winning by switching. Same thing regardless of what choice of door you made first.
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
who also said
"never buy of the horse that is overridden as it will fetch less at the clackers"
consider coffee a lubricant that helps one penetrate the coding zone
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's most useful tools in the future, if they let it. The thing to bear in mind is that it is just that a tool.
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. 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.
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 be if it were only applied to traveling salesmen?
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."