Sign in to follow this  
capn_midnight

number grid puzzles

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
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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this