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?

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.

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

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.

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

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.