number grid puzzles

Artificial Intelligence Programming

Started by capn_midnight September 20, 2004 09:18 AM

4 comments, last by capn_midnight 19 years, 6 months ago

1,708

Author

September 20, 2004 09:18 AM

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?

[Formerly "capn_midnight". See some of my projects. Find me on twitter tumblr G+ Github.]

Shadowdancer

319

September 20, 2004 09:47 AM

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.

fup

463

September 20, 2004 09:47 AM

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

My Website: ai-junkie.com | My Books: 'Programming Game AI by Example' & 'AI Techniques for Game Programming'

Rixter

785

September 21, 2004 12:34 PM

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.

calvinc

122

September 29, 2004 06:25 AM

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

capn_midnight

1,708

Author

September 29, 2004 02:57 PM

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.

[Formerly "capn_midnight". See some of my projects. Find me on twitter tumblr G+ Github.]

number grid puzzles

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

number grid puzzles

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines