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

[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

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