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.
But are there any practical applications, or is this a climb the "nerd mountain" type of thing?
Accentuate the positive, don't waste your mod points on the negative.
A project like this just cries out for distributed computing - if it can be done for Seti and cracking the X-Box key (or rather trying to), surely a distributed client running on many PCs would be a godsend for solving major maths problems.
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
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.
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.
I would think that anyone who didn't want to restart an entire project like this would save state. You can never tell when there are going to be power problems, virus/worm problems, or even a stupid user that decided they needed that machine and crashed it.
Checkpointing is your friend.
Jeremy Baumgartner
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."
Since it ALWAYS happens, the host-picked door (which is always empty) actually doesn't have any bearing on the problem. You can safely eliminate it from consideration.
WRONG. Your choice had a 1/3 chance of being right because there were 3 doors to begin with, among which you chose randomly. Therefore all 3 of those doors are important to the problem, because they specify the conditions in which your first choice is made. Just because the host removes doors doesn't suddenly change the probability of your *initial* choice.
To make it more clear: say there are 1,000,000 doors. Choose one randomly. Not a very good chance of being correct, right? (1/1,000,000). Now the host opens all the doors but yours and one other, showing that they are empty. Would you now go and say that your initial choice has a 50% chance of being right?
If you would, then you're a fool. Because the other door has a 99.9999% chance of being the correct one. Think about it -- your original choice is still your original choice, made out of a million doors. The *other* door is basically the host saying "well, if you chose the wrong door, then *this* is definitely the correct one." Since the chance of you having chosen the wrong door at first is 999,999/1,000,000, then that means the chance that the other door is correct is 999,999/1,000,000 as well.
This logic works for 3 doors, as well, but for some reason doesn't seem as intuitive.
The following sentence is true. The preceding sentence was false.