This is an interesting article, despite a typo in figure 4. ![[bigsmile]](/data/assets/smilies/bigsmile.gif "[bigsmile] [bigsmile]")
Solving Sliding Tiles with Artificial Intelligence (and Some C#)
Solving Sliding Tiles with Artificial Intelligence (and Some C#)
Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations Chriss Miller on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Solving Sliding Tiles with Artificial Intelligence (and Some C#)
- Thread starter SamBones
- Start date
It looks to me as if there are several mistakes in this article. Even though Sam Loyd is commonly credited with inventing the puzzle, it appears that he was actually trying to enhance his own reputation by claiming credit for a puzzle invented by someone else. Also, when I was in college, I looked at the proof of why only half of the starting configurations are solvable, and the explanation in the article looks to be so badly garbled as to be simply wrong.
Here is a reference that denies Sam Loyd's claim to be the puzzle's inventor. I also thought the description of the "arcane language" used in the December, 1879, issue of the American Journal of Mathematics to be quite apt. I looked up this article in my school's math library and could make absolutely no sense out of it, even though the proof that only half of the starting configurations are solvable is actually quite easy.
Here is a reference that denies Sam Loyd's claim to be the puzzle's inventor. I also thought the description of the "arcane language" used in the December, 1879, issue of the American Journal of Mathematics to be quite apt. I looked up this article in my school's math library and could make absolutely no sense out of it, even though the proof that only half of the starting configurations are solvable is actually quite easy.
Olaf Doschke
Programmer
There is a simple obvious solution to not create unsolvable starting situations of this puzzle: Start from the solution and manipulate it randomly via allowed modifications to get a solvable start situation.
Bye, Olaf.
Bye, Olaf.
The "simple obvious solution" of scrambling the puzzle to create a solvable configuration is ok for some purposes, but is worse than a mathematical proof of impossibility for others.
Here is my understanding of what determines whether a configuration is solvable or not:
1. "Solve" the proposed configuration by transposing two tiles at at time, or a tile and the blank space, until you arrive at the solution. It's irrelevant for this purpose whether the transpositions are legal moves in the 15 puzzle. All you are interested in is getting from the starting position to the solution by a series of binary transpositions.
2. Note whether the number of transpositions in step 1 is an even or odd number.
3. Mentally color the puzzle grid in a white and black checkerboard pattern. Note whether the blank space has changed colors from the starting position to the solution.
4. Based on the previous steps, the following two situations are solvable:
A. The blank space has switched colors and the number of transpositions is odd.
B. The blank space remains on the same color and the number of transpositions is even.
As a simple example, consider figure 4 in the article cited by SamBones. You get from the starting position to the solution by swapping tiles 14 and 15 and the blank space remains in the same location (i.e. has not changed color) You have an odd number of transpositions and no change in color - that's not a solvable configuration.
Here is my understanding of what determines whether a configuration is solvable or not:
1. "Solve" the proposed configuration by transposing two tiles at at time, or a tile and the blank space, until you arrive at the solution. It's irrelevant for this purpose whether the transpositions are legal moves in the 15 puzzle. All you are interested in is getting from the starting position to the solution by a series of binary transpositions.
2. Note whether the number of transpositions in step 1 is an even or odd number.
3. Mentally color the puzzle grid in a white and black checkerboard pattern. Note whether the blank space has changed colors from the starting position to the solution.
4. Based on the previous steps, the following two situations are solvable:
A. The blank space has switched colors and the number of transpositions is odd.
B. The blank space remains on the same color and the number of transpositions is even.
As a simple example, consider figure 4 in the article cited by SamBones. You get from the starting position to the solution by swapping tiles 14 and 15 and the blank space remains in the same location (i.e. has not changed color) You have an odd number of transpositions and no change in color - that's not a solvable configuration.
No discussion of this puzzle would be complete without pointing out that the brilliant but troubled chess champion, Bobby Fischer, also claimed to be the world's fastest solver of the 15 puzzle.
Olaf Doschke
Programmer
The "15 puzzle" is an easter egg of a programming language and there is a hotkey for putting the puzzle in the solved state. If you move tiles fast and then after a while use the hotkey you can at least seem to be faster than Bobby Fischer.
Anyway, I agree a mathematical proof always is more valuable. I doubt it's as easy as here to determine if a certain chess position is possble at all or not, if there is no obvious error like a pawn in row 1 or 8.
Bye, Olaf.
Anyway, I agree a mathematical proof always is more valuable. I doubt it's as easy as here to determine if a certain chess position is possble at all or not, if there is no obvious error like a pawn in row 1 or 8.
Bye, Olaf.
- Status
Similar threads
- Locked
- Question
- Locked
- Question