**1**

# Solving N-Puzzles

###
#5
Moderators - Reputation: **2532**

Posted 10 February 2011 - 09:14 AM

**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!"*

###
#6
Members - Reputation: **100**

Posted 13 February 2011 - 04:50 PM

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

###
#8
Members - Reputation: **100**

Posted 14 February 2011 - 09:33 AM

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

###
#10
Members - Reputation: **100**

Posted 14 February 2011 - 10:24 AM

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

###
#11
Moderators - Reputation: **9670**

Posted 14 February 2011 - 10:33 AM

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.

###
#12
Members - Reputation: **100**

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.