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.

Comments

For our next experiment...

[Black Parrot]

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

[Kombat]

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

[Progman3K]

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...

Clip clop

[Channard]

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

Nope, but they got through about six coconuts.

Re:Another interesting math problem

[Dashing Leech]

Actually, not quite right, it's never 1/2. You have a 1/3 chance of picking the right door if you stay with your first choice, and a 2/3 chance if you switch. No need for simulation, just look at the possibility matrix:

\ 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:1GHz WHAT?

[edwinolson]

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.

Brute force--Bring it on!

[Unknown Kadath]

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