No Magic In A Knight's Tour 278
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.
Interesting problem... (Score:0, Insightful)
Re:A note to the anti-MS zealots (Score:1, Insightful)
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.
Re:That's nice, but not impressive (Score:5, Insightful)
Re:That's nice, but not impressive (Score:4, Insightful)
Re:That's nice, but not impressive (Score:4, Insightful)
Re:That's nice, but not impressive (Score:5, Insightful)
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...
Re:Another interesting math problem (Score:4, Insightful)
on FARK.com this would have the following header (Score:4, Insightful)
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?
1GHz WHAT? (Score:4, Insightful)
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:Another interesting math problem (Score:5, Insightful)
\ 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.
Re:on FARK.com this would have the following heade (Score:5, Insightful)
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
on the value of horse problems (Score:3, Insightful)
who also said
"never buy of the horse that is overridden as it will fetch less at the clackers"
Re:That's nice, but not impressive (Score:2, Insightful)
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.
Re:Is math dying? (Score:3, Insightful)
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.
Re:Interesting problem... (Score:2, Insightful)
As discussed in Simon Singh's excellend Fermat's Enigma [amazon.com], the research done by many other people may be built upon the assumption that a particular mathematical statement is either true or false. Until a proof is presented -- either by brute force or more elegant means -- it us unknown whether the "ediface" built on the assumption will stand or fall.
Since pure mathematics underlies a great deal of applied research, having mathematical statements proven true or false can tell us whether or not it's worth our time and resources to follow a particular line of reasoning.
As for the importance of pure research, I think you'll find that a huge number of people in this world are counting on some pretty miraculous discoveries being just around the corner, because based on what we know and know how to do today, we've got some serious problems on the way. Only pure research might enable us to luckily stumble across the right leads. After all, if we knew where to look, we'd already have arrived at the answers.
Re:A note to the anti-MS zealots (Score:2, Insightful)
Checkpointing is your friend.
Re:on FARK.com this would have the following heade (Score:5, Insightful)
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?
Re:Another interesting math problem (Score:3, Insightful)
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.