8 puzzle: Solvability and shortest solution

Question

I have built a 8 puzzle solver using Breadth First Search. I would now want to modify the code to use heuristics. I would be grateful if someone could answer the following two questions:

Solvability

How do we decide whether an 8 puzzle is solvable ? (given a starting state and a goal state ) This is what Wikipedia says:

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner.

Unfortunately, I couldn't understand what that meant. It was a bit complicated to understand. Can someone explain it in a simpler language?

Shortest Solution

Given a heuristic, is it guaranteed to give the shortest solution using the A* algorithm? To be more specific, will the first node in the open list always have a depth ( or the number of movements made so fat ) which is the minimum of the depths of all the nodes present in the open list?

Should the heuristic satisfy some condition for the above statement to be true?

Edit : How is it that an admissible heuristic will always provide the optimal solution? And how do we test whether a heuristic is admissible?

I would be using the heuristics listed here

Manhattan Distance 
Linear Conflict 
Pattern Database 
Misplaced Tiles
Nilsson's Sequence Score 
N-MaxSwap X-Y 
Tiles out of row and column

---

For clarification from Eyal Schneider :

---

Lysol

ad #2: yes, the A* algorithm guarantees to find an optimal solution if you use an admissive heuristic (never overestimate) – Contributor

Is there any way by which we can check if a heuristic is admissible? I want to use the various heuristics stated on this page: heuristicswiki.wikispaces.com/N+-+Puzzle – Lysol

I wish that someone would be able to explain how to test for the admissibility of a heuristic. – Lysol

Answer 1

I'll refer only to the solvability issue. Some background in permutations is needed.

A permutation is a reordering of an ordered set. For example, 2134 is a reordering of the list 1234, where 1 and 2 swap places. A permutation has a parity property; it refers to the parity of the number of inversions. For example, in the following permutation you can see that exactly 3 inversions exist (23,24,34):

1234
1432

That means that the permutation has an odd parity. The following permutation has an even parity (12, 34):

1234
2143

Naturally, the identity permutation (which keeps the items order) has an even parity.

Any state in the 15 puzzle (or 8 puzzle) can be regarded as a permutation of the final state, if we look at it as a concatenation of the rows, starting from the first row. Note that every legal move changes the parity of the permutation (because we swap two elements, and the number of inversions involving items in between them must be even). Therefore, if you know that the empty square has to travel an even number of steps to reach its final state, then the permutation must also be even. Otherwise, you'll end with an odd permutation of the final state, which is necessarily different from it. Same with odd number of steps for the empty square.

According to the Wikipedia link you provided, the criteria above is sufficient and necessary for a given puzzle to be solvable.

Petaliferous

I understood what parity means. Now, coming to the sentence: "parity of the permutation of all 9 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner" So, we will be getting the parity of a state as an integer by considering it to be a permutation of the goal state which should be added to some other number. ( parity of the taxicab distance ) Now, isn't taxicab distance itself a number? What does its parity mean? – Lysol

@Ranjith: It means the simple parity of the number. You can treat it as 0 and 1, so adding parities is simply checking the parity of the sum. – Petaliferous

@Ranjith: Now, the solvability criteria is simple: a puzzle is solvable if and only if the following two are equal : 1) the parity of the number of steps the empty square has to do (simply calculate the parity of the manhattan distance between the start and end position). 2) The parity of the permutation represented by the initial state, compared to the goal state. – Petaliferous

I have edited the question and added three images: the first image showing one state and two goal states. The second and third images showing whether the two goal states can be reached or not. Can you please look at them and tell whether I have done it right or not. I want to be sure that I have understood things correctly. – Lysol

@Ranjith-SR2GF: Yes, it seems to be fine, except for the typo in case B, where the number 3 is presented as an even number... – Petaliferous

Any idea about some concrete method for checking the admissibility of a heuristic function, other than trial and error... – Lysol

@Ranjith-SR2GF: You should prove that your heuristic function is admissible. – Petaliferous

Answer 2

The A* algorithm is guaranteed to find the (one if there are more than one equal short ones) shortest solution, if your heuristic always underestimates the real costs (In your case the real number of needed moves to the solution).

But on the fly I cannot come up with a good heuristic for your problem. That needs some thinking to find such a heuristic.

The real art using A* is to find a heuristic that always underestimates the real costs but as little as possible to speed up the search.

---

First ideas for such a heuristic:

1. A quite pad but valid heuristic that popped up in my mind is the manhatten distance of the empty filed to its final destination.
2. The sum of the manhatten distance of each field to its final destination divided by the maximal number of fields that can change position within one move. (I think this is quite a good heuristic)

Steinway

Any idea about the solvability part? – Lysol

@Lysol - SR2GF: I have not yet an idea about the solvability part. Naive way is: try to find a solution, if there is none, you will not find one ;-) – Steinway

But that would take a lot of time! – Lysol

@Lysol - SR2GF: About the solvability: 1. In general these puzzles are solvable. 2. An not solvable puzzle can be made solvable, if you swap two neighbor fields at the beginning. So one possibility is to try to solve the puzzle and in parallel try to solve the puzzle with one neighbor pair fields swapped. If a solution on the modified version is found, the original puzzle was not solvable. – Steinway

That is a good idea - solving the original puzzle and the swapped puzzle in parallel. It would be better if I can directly check for solvability. – Lysol

Thanks for answering the second part of the question. – Lysol

Answer 3

For anyone coming along, I will attempt to explain how the OP got the value pairs as well as how he determines the highlighted ones i.e. inversions as it took me several hours to figure it out. First the pairs. First take the goal state and imagine it as a 1D array(A for example) [1,2,3,8,0,4,7,5]. Each value in that array has it's own column in the table(going all the way down, which is the first value of the pair.) Then move over 1 value to the right in the array(i + 1) and go all the way down again, second pair value. for example(State A): the first column, second value will start [2,3,8,0,4,7,5] going down. the second column, will start [3,8,0,4,7,5] etc..

okay now for the inversions. for each of the 2 pair values, find their INDEX location in the start state. if the left INDEX > right INDEX then it's an inversion(highlighted). first four pairs of state A are: (1,2),(1,3),(1,8),(1,0)
1 is at Index 3
2 is at Index 0
3 > 0 so inversion.

1 is 3
3 is 2
3 > 2 so inversion

1 is 3
8 is 1
3 > 2 so inversion

1 is 3
0 is 7
3 < 7 so No inversion

Do this for each pairs and tally up the total inversions. If both even or both odd (Manhattan distance of blank spot And total inversions) then it's solvable. Hope this helps!

Halibut