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.
A note to the anti-MS zealots (Score:-1, Interesting)
Bash MS all you want, but Windows isn't as unstable and problematic as all of your anti-MS zealots would like to believe.
That's nice, but not impressive (Score:5, Interesting)
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?
Source Code snippets (Score:2, Interesting)
#define true 7361
#define false 28456
Re:Interesting problem... (Score:3, Interesting)
Re:That's nice, but not impressive (Score:4, Interesting)
http://www.math.gatech.edu/~thomas/FC/fourcolor.h
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)
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.
Re:Interesting problem... (Score:1, Interesting)
There was a very interesting series on BBC radio4 (http://www.bbc.co.uk/radio4/science/) called five number and another five numbers which can be streamed from the above link which talks about this sort of thing.
Re:That's nice, but not impressive (Score:3, Interesting)
Is math dying? (Score:4, Interesting)
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!
Ahh the memories... (Score:2, Interesting)
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 now it seems so simple, you just need to know a magic knight's tour by heart and that's it! (Ok, memorizing that is still pretty amazing by my standards :)
Re:Interesting problem... (Score:2, Interesting)
For me it is sort of like saying if I hurt my hand with a hammer it damn well hurts rather than investing the underlying reason.
Re:on FARK.com this would have the following heade (Score:2, Interesting)
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 should not be published, but on the other hand, I found it interesting to know that that problem got solved, so I don't complain that it has been published.
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?
Perhaps not. But nobody sais that you can't go looking for an elegant proof just because the problem has been solved. There is also some merit in finding he easiest or most elegant solution, not just in finding the first one.
Re:Is math dying? (Score:3, Interesting)
My problem is certainly not with computers, which I agree are a huge aid to mathematics. Suites like Mathematica etc. are tremendous tools, visualization methods, and timesavers. 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.
Re:Is math dying? (Score:2, Interesting)
Brute force--Bring it on! (Score:5, Interesting)
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
Re:That's nice, but not impressive (Score:2, Interesting)
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 algorithm, even a brute-force one IS proof.