Jump to content
  • Advertisement
Sign in to follow this  
capn_midnight

number grid puzzles

This topic is 5108 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm sure everyone is familiar with the sliding tile puzzle in which you attempt to reorganize the tiles into sequential order. So, given some initial board state:
528
376
14
you can arrive at some goal board state:
123
4 5
678
I have 3 heuristics for solving this problem, but they are based on the assumption that not all random arrangements of number tiles have a solution (that is, if you were to mix the numbers by removing the tiles from the board and relaying them, not by sliding them). But I have no proof, and my AI professor does not agree. Is it true/is there a proof?

Share this post


Link to post
Share on other sites
Advertisement
It is correct that not all permutations have a solution. The board

1 2 3
4 5 6
8 7

does not have a two-dimensional or non-destructive solution. In fact, someone once sold those puzzles promising a ridiculously high reward for a solution. I think there is a proof, but I don't know where to look for it.

Share this post


Link to post
Share on other sites
Nilsson demonstrates that there are two disjoint subsets of configurations of the 8-puzzle. For example, the following cannot be solved.

8 7 6
5 4 3
2 1 -

(transformed into:

1 2 3
4 5 6
7 8 -

)

See Nilsson, N.J. "Problem-solving Methods in Artificial Intelligence", McGraw-Hill, 1971. (page 6).

Share this post


Link to post
Share on other sites
I believe if you slide the tiles into all possible states, there are 9!/2 possible states. You could probably do an inductive proof starting with a 2x2 board.

Share this post


Link to post
Share on other sites
hi... i'm still very new in ai.. currently i'm learning how to implement sliding tile puzzle in java... could anyone please help? i need to get some tutorials and example code or program(if possible).. thanks in advance...

calvinc

Share this post


Link to post
Share on other sites
Quote:
Original post by calvinc
hi... i'm still very new in ai.. currently i'm learning how to implement sliding tile puzzle in java... could anyone please help? i need to get some tutorials and example code or program(if possible).. thanks in advance...

calvinc
it's easiest to implement as an NxN array, N being the dimensions of your grid.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!