# number grid puzzles

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

## 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 on other sites
It is correct that not all permutations have a solution. The board
1 2 34 5 68 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 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 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 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 on other sites
Quote:
 Original post by calvinchi... 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.

• 17
• 10
• 21
• 16
• 9