11 replies to this topic

[vaneger]

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

[Álvaro]

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

[vaneger]

Once more, and in English perhaps ?

[Álvaro]

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

[IADaveMark]

Agreed... if you can't parse the answer above, perhaps you need to do some more studying before even asking the question.

[schadlerm]

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

[Álvaro]

That's what I said!

[Walrus VN]

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.

[SiCrane]

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.

[Walrus VN]

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.

[SiCrane]

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.

[Walrus VN]

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.