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

Article on Chessbase

[GeckoFood]

There is an interesting [related] article on chessbase here about knight's tours. On the main chessbase page, they reference the main article involving magic tours.

Re:Another interesting math problem

[Another Nils]

If it turns out 1/3 to 1/3 no matter if you switch, then your program sometimes opens the door with the big prize in it, I guess.

It really works like this:
Assuming you picked door A, then there are three possible situations:
-The prize is behind door A
-The prize is behind door B
-The prize is behind door C

So if you stick to the door you just picked, then you have a 1/3 chance of winning.
Now obviously there's a 2/3 chance that the prize is behind one of the two other doors. And the host is basically giving you the information
"IF the prize is behind one of the two remaining doors, then it is behind THIS one" by opening an empty door.
So switch, it will give you a 2/3 chance of winning.

And yes, I had to write a program, too, before I actually believed it.

Re:That's nice, but not impressive

[iapetus]

A proof would have told us how many routes there are for an arbitrary sized chessboard as well.

Not necessarily. As the article points out, there is a proof for certain sizes of chessboard, but it doesn't extend down to 8x8. Not all mathematical proofs are quite as neat as we might like them to be in terms of how they apply to other variants on the same problem.

Re:Another interesting math problem

[Anonymous Coward]

Imagine that you always stick with your first choice. Therefore, you've got to select the right door in the first place to win, hence your chance of winning by always sticking is 1 in 3.

Now imagine that you always switch. If you picked the right door to start with, you're screwed as you will always lose by switching. However, if you pick one of the two wrong doors then the host must to open the other wrong door, leaving just the right door remaining. So if you picked a wrong door in the first place, you are guaranteed to win by switching. Your chance of selecting a wrong door initially is 2 in 3 and therefore your chance of winning by always switching is 2 in 3.

1/3 + 2/3 = 1, hence all possibilites are accounted for and it is proved that by switching you twice as much chance of winning than by sticking.

Re:Another interesting math problem

[utahjazz]

...Assuming the 'host' always opens one of the remaining doors and the remaining door never has a prize behind it...

A note to all the people writing code to solve this, the key to this problem is that Monty intentionally chooses a door that has no prize behind it. No doubt, some of you are interpreting this problem as, "Monty chooses another door at random, and we're only examining the cases where he chooses the door with no prize". If that is your interpretation, then switching doesn't matter, but the traditional Monty Hall Problem assumes Monty knows what's behind the doors and chooses accordingly.

For those of you who can't be arsed with the links

[jonathan_ingram]

A knights tour involves moving the knight onto every square of the chessboard without repeating a square (being a knight, it is of course allowed to jump over squares it has previously landed on).

A magic square is a square grid, with each grid position numbered, such that the horizontals, verticals, and diagonals all add to the same number (you can also ask for all the broken diagonals to add to this number, but this doesn't have to hold in a basic magic square).

If we number the knight's initial position 1, and increment with every jump, then a knights tour gives us a numbered n by n square (8 by 8 in the case of a normal chessboard).

The question: are there any knights tours which give us a magic square after we perform this numbering operation?

The answer: no, although there are many tours which give us a 'semi-magic' square (where the horizonals and verticals, but not the diagonals, give us the same sum).

The point: although magic squares have a variety of surprising uses, there seems to be no 'point' to the magic knights tour question other than another line in the book of 'solved minor problems' -- but if it's enough to write a paper on, then you can bet you'll be able to find a graduate student to do it :).