View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Solving N-Puzzles

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

11 replies to this topic

### #1vaneger  Members

Posted 08 February 2011 - 01:15 PM

What are some methods for solving arbitrary N sized N puzzles ? How can I determine unsolvable configurations?

### #2Álvaro  Members

Posted 08 February 2011 - 03:02 PM

A configuration is unsolvable if it doesn't have the same parity as the target configuration. To solve a solvable configuration, use a pathfinding algorithm, like A*.

### #3vaneger  Members

Posted 09 February 2011 - 08:31 PM

Once more, and in English perhaps ?

### #4Álvaro  Members

Posted 09 February 2011 - 11:10 PM

Try Wikipedia. Ask specific questions if you don't understand.

Posted 10 February 2011 - 09:14 AM

Agreed... if you can't parse the answer above, perhaps you need to do some more studying before even asking the question.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

Posted 13 February 2011 - 04:50 PM

First lets look at determining an unsolvable puzzle. I agree with the above posters, you should understand the parity concept presented earlier if asking the question - however here another perspective to view.

A puzzle is solvable if the number of permutations is even. This can be easily calculated. Assume you have the following puzzle where the open square is represented by a "_", and the solution puzzle has the numbers in sequential order with the open square at the bottom right. I will demonstrate this with an 8 puzzle, however the idea applies to N-puzzles.

3 4 1
7 5 6
8 _ 2

Now to calculate the number of permutations, go through each position in the board. The number where you are currently at will be called N. The number of permutations is the total from all positions of the amount of numbers smaller than N, which appears after N. Thus for this example you have the following:
3 is before 1,2 = 2
4 is before 1,2 = 2
1 is not before any lower number = 0
7 is before 5,6,2 = 3
5 is before 2 = 1
6 is before 2 = 1
8 is before 2 = 1
_ is before 2 = 1

2 + 2 + 0 + 3 + 1 + 1 + 1 + 1 = 11

11 is an odd number, thus the puzzle is not solvable. If the sum is even, the puzzle is solvable.

As for solving the puzzle, look up A*. It's a simple graph search algorithm which is easily applied to the program. As a hint, consider each state of the puzzle a node in the graph, a child node is a state that can be created from one move from the state. However, you must be sure not to create child states that exist previously in the graph.

Hope that helps a bit

### #7Álvaro  Members

Posted 13 February 2011 - 10:29 PM

That's what I said!

### #8Walrus VN  Members

Posted 14 February 2011 - 09:33 AM

If a puzzle is solvable, and you just need to solve it (i.e. you don't need to find the MINIMUM numbers of moves), there's a faster and simpler method than A*:

Just try to move 1, 2, 3, ... in place, in order, while keeping the previous tiles at the correct position.

### #9SiCrane  Moderators

Posted 14 February 2011 - 09:51 AM

Have you ever actually tried to do one of these puzzles? That strategy doesn't work. Ex 15-puzzle:
[ 1] [ 2] [ 3] [15]
[ x] [ x] [  ] [ 4]
[ x] [ x] [ x] [ x]
[ x] [ x] [ x] [ x]

There is no way to move 4 into place without moving 3.

### #10Walrus VN  Members

Posted 14 February 2011 - 10:24 AM

Have you ever actually tried to do one of these puzzles? That strategy doesn't work. Ex 15-puzzle:

[ 1] [ 2] [ 3] [15]
[ x] [ x] [  ] [ 4]
[ x] [ x] [ x] [ x]
[ x] [ x] [ x] [ x]

There is no way to move 4 into place without moving 3.

The algorithm is only worked when the puzzle is solvable, I'm not sure if your example is a solvable one or not... and yes I have actually coded this algorithm few years ago, I don't remember the details but that's the main idea. Perhaps, we can move 3 (or even 1, 2) in some immediate steps, but after the steps are done, we should have 1, 2, 3, 4 in line.

### #11SiCrane  Moderators

Posted 14 February 2011 - 10:33 AM

1) Your post distinctly said "while keeping the previous tiles at the correct position." If you need to move a previous tile in an intermediary step, then that isn't the same algorithm you originally said would work.

2) An N-puzzle is solvable if the parity is even. A puzzle can be change in parity from odd to even or vice versa by swapping the values of two adjacent tiles. Since the value of 8 positions are left unspecified then that puzzle configuration can map to any number of solvable puzzles.

### #12Walrus VN  Members

Posted 14 February 2011 - 10:31 PM

1) Your post distinctly said "while keeping the previous tiles at the correct position." If you need to move a previous tile in an intermediary step, then that isn't the same algorithm you originally said would work.

2) An N-puzzle is solvable if the parity is even. A puzzle can be change in parity from odd to even or vice versa by swapping the values of two adjacent tiles. Since the value of 8 positions are left unspecified then that puzzle configuration can map to any number of solvable puzzles.

Yes, my mistake. Let me change it to "some previous tiles can be moved in intermediary steps". So basically there's a function moveTile(i), i = 1..N*N, with the precondition that 1, 2, i-1 is already in place, and the postcondition should be 1, 2, ..., i in place - any tiles can be moved in an intermediary step, though. I can't remember the details on how to implement this function, perhaps there're few cases, depending on the current position of i and the correct position of i.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.