INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

Solving Sliding Tiles with Artificial Intelligence (and Some C#)

RE: Solving Sliding Tiles with Artificial Intelligence (and Some C#)

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.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=...

RE: Solving Sliding Tiles with Artificial Intelligence (and Some C#)

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.

RE: Solving Sliding Tiles with Artificial Intelligence (and Some C#)

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.

RE: Solving Sliding Tiles with Artificial Intelligence (and Some C#)

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.

Quote:

Fischer was never afraid of publicity, so he made arrangements to appear on “The Tonight Show Starring Johnny Carson” in 1972 (at the height of his chess tourney powers) to demonstrate his ability to solve the 15 Puzzle in record time. Thanks to doing that successfully on national TV–his solve rate on the puzzle stands alone.

http://wetpig.com/bobby-fischers-non-chess-talent-...

RE: Solving Sliding Tiles with Artificial Intelligence (and Some C#)

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.

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Resources

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close