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

Re:That's nice, but not impressive

[forsetti]

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

Re:That's nice, but not impressive

[Jooly Rodney]

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.

Re:That's nice, but not impressive

[91degrees]

I agree. They're highly unsatisfying. A proof would have told us how many routes there are for an arbitrary sized chessboard as well.

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

Re:Another interesting math problem

[Deathlok's Bear]

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!

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:on FARK.com this would have the following heade

[Skater]

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

Re:on FARK.com this would have the following heade

[reverseengineer]

Well, this initially doesn't sound like a very serious problem- I mean, so, you're taking the fairly simple and well-worn problem of finding a knight's tour on a standard chessboard, and throwing in the rather odd constraint that the path has to create an 8x8 magic square. An oddity produced by the rules of chess (trying to fit L-shaped moves on a square board makes finding a knight's tour obviously more challenging than finding a queen's tour) meets an ancient mathematical curiosity. Viewed that way, this problem seems entirely pointless.

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?