8 puzzle: solvability and the shortest solution

Question

I built 8 puzzles using Breadth First Search. Now I want to change the code to use heuristics. I would be grateful if someone answers the following two questions:

solvability

How do we decide if 8 puzzles are allowed? (given the initial state and state of the goal) Here's what Wikipedia says:

An invariant is the parity of the permutation of all 16 squares plus the ratio of the distance between the taxi (the number of rows and the number of columns) of the empty square from the lower right corner.

Unfortunately, I could not understand what this means. It was a little hard to understand. Can someone explain this in a simpler language?

Shortest solution

Given the 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 thick), which is the minimum depth of all nodes present in the open list?

If the heuristic satisfies a certain condition so that the above statement is true?

Edit: how is a valid heuristic that will always provide an optimal solution? And how do we check if heuristics are acceptable?

I would use the given heuristics here

Manhattan Distance Linear Conflict Pattern Database Misplaced Tiles Nilsson Sequence Score N-MaxSwap XY Tiles out of row and column 

---

For clarification from Eyal Schneider:

---

Answer 1

I will only refer to the solvability problem. Some background in permutations is needed.

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

 1234 1432 

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

 1234 2143 

Naturally, the permutation of identity (which preserves the order of elements) has even parity.

Any state in 15 puzzles (or 8 puzzles) can be considered as a permutation of the final state if we consider it as a concatenation of lines starting from the first line. Please note that each legitimate step changes the parity of the permutation (because we are changing two elements, and the number of inversions related to each other must be even). Therefore, if you know that an empty square must go through an even number of steps to achieve its final state, then the permutation must also be even. Otherwise, you will end up with an odd permutation of the final state, which will necessarily be different from it. Same thing with an odd number of steps for an empty square.

According to the Wikipedia link you provided, the above criteria are sufficient and necessary for the solvability of a given puzzle.

Answer 2

The A * algorithm is guaranteed to find (one, if there are several identical short ones) the shortest solution, if your heuristic always underestimates the real costs (in your case, the actual number of necessary steps to solve).

But on the fly I can’t come up with a good heuristic for your problem. For this, a certain thought is needed to find such a heuristic.

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

---

First ideas for such a heuristic:

• Enough sheets, but the actual heuristic that arose in my head is the distance manhatten from the empty filed at the final destination.
• The sum of the manhatten distance of each field to the final destination divided by the maximum number of fields that can change position in one turn. (I think this is a pretty good heuristic).

Answer 3

I will try to answer the question related to the "shortest solution" part. The A * tree search algorithm is guaranteed to be optimal (i.e., find the shortest path, if one exists) if the heuristic is valid (i.e., it never overestimates the cost of the path to the nearest target). Formally, the heuristic h is admissible if for each node n, 0 <= h (n) <= h * (n), where h * (n) is the exact cost of achieving the nearest goal from n.

However, searching for the A * tree can lead to exponentially more repetitive work. We need a way to close the extended nodes so that they are not expanded again, which leads to a graph search algorithm. A * graphical search is optimal only if the heuristic is used in a consistent manner, i.e. Estimates the cost of the path gradually, so the heuristic value along the path never decreases. Formally, the heuristic h is consistent if, for each node n and for each successor s of n, h (n) <= h (p) + cost (n, p).

The Manhattan distance is a consistent heuristic for a problem with 8 puzzles, and the A * graph search, equipped with a Manhattan distance as heuristic, will indeed find the shortest solution if it exists.

I wrote a detailed explanation of A * search and provided python an implementation of the N-puzzle problem using A * here: A * search search and N- python puzzle

Answer 4

For everyone who comes, I will try to explain how the OP received pairs of values, as well as how it determines the selected ones, i.e. inversions, since it took me several hours to figure this out. First couples. First, take the state of the target and imagine that it is like a 1D array (for example, A) [1,2,3,8,0,4,7,5]. Each value in this array has its own column in the table (all the way down, which is the first value of the pair). Then move 1 value to the right in the array (i + 1) and go down again, the second value of the pair. for example, (state A): first column, second value will start [2,3,8,0,4,7,5]. second column, start [3,8,0,4,7,5], etc.

Now suitable for inversions. for each of the two values ​​of the pair, find their location INDEX in the initial state. if left INDEX > right INDEX , then this is the inverse (highlighted). the first four pairs of state A: (1,2), (1,3), (1,8), (1,0)
1 is at index 3
2 is at index 0
3> 0, so the inversion.

1 is 3 3 - 2
3> 2, so the inversion

1 is 3 8 - 1 3> 2, so the inverse

1 is 3 0 - 7 3 <7, so there is no inversion

Do this for each pair and summarize the total inversions. If both are even or both are odd (Manhattan empty space and total inversions) then it is decidable. Hope this helps!