Slashdot Mirror
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.
is right here
Maybe if the Knight REALLY wanted to take a Magic Tour he'd consult a Wizard instead of a Computer...
No wonder he didnt only got a Semimagic tour, damn you Travelocity! Damn you to hell!
This is my sig. Its pathetic.
The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz
I bet the horse was tired after hopping around so much.
The unofficial
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.
Sheesh, evil *and* a jerk. -- Jade
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?
Like woodworking? Build your own picture frames.
Check this out...
#define true 7361
#define false 28456
how long until
> The webpage mentions that the program is windows based and doesn't save state. That means that all of those CPU hours came in a row (at idle priority even). Bash MS all you want, but Windows isn't as unstable and problematic as all of your anti-MS zealots would like to believe.
61.40 CPU-days spread between 10 people's computers, and you think that indicates enough uptime to brag about? Puh-leeze.
Sheesh, evil *and* a jerk. -- Jade
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.
Be excellent to each other. And... PARTY ON, DUDES!
uptime is nothing to brag about, unless you're talking about your penis.
Probably not, but this problem and the way to achieve the magical tour have been going around for quite a few centuries, with some of the brightest minds trying to work on it. So even if it doesn't have practical applications it's still important.
Don't try to fix me. I'm not broken.
You're mistaken, although you are in good company, no less a mathematician than Paul Erdos made the same error.
Post your code if you still think switching makes no difference.
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!
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.
Brute forcing to get a proof is better than no proof at all, but brute forcing a special case is even more acceptable.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
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.
Nope, but they got through about six coconuts.
"Still no cure for cancer."
Without trying to be too much of a Troll, can someone explain to me as a mathematical lay man as to why this problem has any significance? Given that a chess board is an arbitrary 8x8 set of constraints, is there anything that can be learned and applied to the real world (or even theoretical mathematics?) through solving this problem?
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?
John Maynard Keynes: "When the facts change, I change my mind. What do you do?"
The solution came after 61.40 CPU-days, corresponding to 138.25 days of computation at 1 GHz
Yeah, and I came to work in 12.34 horsepower-hours, corresponding to 666.13 hours of driving at 5K RPM. I mean, damn, I understand when my mom utters movie-level technobabble, but this?
I just wrote a quick demonstration program to find them...
"How to Do Nothing," kids activities, back in print!
The story uses CPU-hours "at 1GHz" as a unit of measurement.
Guys, please, this is SlashDot. A 1GHz G5 is not the same as a 1GHz Duron is not the same as a 1GHz P3. What sort of 1GHz chip is being referred to here?
Honey, I shrunk the Cygwin
\ 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.
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
who also said
"never buy of the horse that is overridden as it will fetch less at the clackers"
consider coffee a lubricant that helps one penetrate the coding zone
Are you sure you read the correct parent post to mine? He is wrong, and you are as well, although your statement disagrees with his.
Suppose there are doors A, B and C. Let's say you pick door A originally, and the host then shows door B to be empty. Given this information, there is a one in three chance that the prize lies behind door A, and a two in three chance the prize lies behind door C.
Google for 'Monty Hall' for proofs of this.
It seems to me that more and more math problems are being approached in a brute-force, computerized way. While this is certainly a legitimate way of finding answers to a problem, aren't we missing the point of these problems by using it? It's not like anyone was really waiting on the answer to that problem. It's such a lazy disappointing answer to an exciting mathematical question: "Are there any magic knight tours on an 8x8 chessboard?" "Nah, I tried 'em all out, see." Are we seeing the death of "clever" mathematics where a simple elegant solution is found, correlating known theorems in novel ways that enhance our collective understanding of the way math works?
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" 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!
-3Suns
~~~~
The Revolution will be Slashdotted
Put my mind at rest.. I've been worrying about this for years.
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 :)
...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.
Thing is though, is this actually an answer with any real point, proving an answer via a simple brute force method is far less interesting(and I would say far less useful) than a mathematical proof.
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.
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.
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
-- Help Digitise the Public Domain at DP.
Is this a /. first? Well I won't let it happen. Hey, screw the magical knight tour, how about solving 9x9 Go?
-Libertarian secular transhumanist
Sir Paul McCartney did make a Magical Mystery Tour
The point is that the host knows where the prize is, and that he is giving away a lot of info by opening one door. It would be useless to switch if he opened the door at random and could possible find the prize himself.
so you should switch. As simple as that
And, your demo prg must be wrong. Remember that the host should use his knowledge and always open and empty door, never the correct one
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
Like Daddy always said: if you can't dazzle 'em with brilliance, baffle 'em with bullshit.
It might not be as interesting, but it can definitely be useful.
As discussed in Simon Singh's excellend Fermat's Enigma, the research done by many other people may be built upon the assumption that a particular mathematical statement is either true or false. Until a proof is presented -- either by brute force or more elegant means -- it us unknown whether the "ediface" built on the assumption will stand or fall.
Since pure mathematics underlies a great deal of applied research, having mathematical statements proven true or false can tell us whether or not it's worth our time and resources to follow a particular line of reasoning.
As for the importance of pure research, I think you'll find that a huge number of people in this world are counting on some pretty miraculous discoveries being just around the corner, because based on what we know and know how to do today, we've got some serious problems on the way. Only pure research might enable us to luckily stumble across the right leads. After all, if we knew where to look, we'd already have arrived at the answers.
I would think that anyone who didn't want to restart an entire project like this would save state. You can never tell when there are going to be power problems, virus/worm problems, or even a stupid user that decided they needed that machine and crashed it.
Checkpointing is your friend.
Jeremy Baumgartner
I for one would find you hitting your hand with a hammer much more interesting then watching you work it out on pen and paper. ;)
I like my women how I like my sugar.. granulated.
Anyone interested in a great read involving chess, magic squares, knight's tours, acoustics, fibonnaci numbers, the French revolution and the 1970's programming scene, check out The Eight by Katherine Neville. Just finished it for the third time, and discovered the the last two years of my daily /. education helped me to appreciate and enjoy it even more. I apologize in advance for the amazon link; it was the only site that gave a decent balance of reviews.
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?
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
Since it ALWAYS happens, the host-picked door (which is always empty) actually doesn't have any bearing on the problem. You can safely eliminate it from consideration.
WRONG. Your choice had a 1/3 chance of being right because there were 3 doors to begin with, among which you chose randomly. Therefore all 3 of those doors are important to the problem, because they specify the conditions in which your first choice is made. Just because the host removes doors doesn't suddenly change the probability of your *initial* choice.
To make it more clear: say there are 1,000,000 doors. Choose one randomly. Not a very good chance of being correct, right? (1/1,000,000). Now the host opens all the doors but yours and one other, showing that they are empty. Would you now go and say that your initial choice has a 50% chance of being right?
If you would, then you're a fool. Because the other door has a 99.9999% chance of being the correct one. Think about it -- your original choice is still your original choice, made out of a million doors. The *other* door is basically the host saying "well, if you chose the wrong door, then *this* is definitely the correct one." Since the chance of you having chosen the wrong door at first is 999,999/1,000,000, then that means the chance that the other door is correct is 999,999/1,000,000 as well.
This logic works for 3 doors, as well, but for some reason doesn't seem as intuitive.
The following sentence is true. The preceding sentence was false.