java 8 谜题：可解性和最短解

8 puzzle: Solvability and shortest solution

提问by Ranjith

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:

我使用广度优先搜索构建了一个 8 拼图求解器。我现在想修改代码以使用启发式方法。如果有人能回答以下两个问题，我将不胜感激：

Solvability

可解性

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

我们如何确定一个 8 拼图是否可解？（给定一个起始状态和一个目标状态）这就是维基百科所说的：

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.

不变量是所有 16 个方格排列的奇偶性加上空方格从右下角的出租车距离（行数加列数）的奇偶性。

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?

给定一个启发式，是否保证使用 A* 算法给出最短的解决方案？更具体地说，开放列表中的第一个节点是否总是具有一个深度（或如此肥胖的运动次数），即开放列表中存在的所有节点的深度的最小值？

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 :

来自 Eyal Schneider 的澄清：

---

---

回答by Eyal Schneider

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):

排列是对有序集合的重新排序。例如，2134 是列表 1234 的重新排序，其中 1 和 2 交换了位置。排列具有奇偶性；它指的是反转次数的奇偶性。例如，在以下排列中，您可以看到正好存在 3 个反转 (23,24,34)：

1234
1432

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

这意味着置换具有奇偶校验。以下排列具有偶校验 (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.

15 拼图（或 8 拼图）中的任何状态都可以视为最终状态的排列，如果我们将其视为行的串联，从第一行开始。请注意，每个合法的移动都会改变排列的奇偶性（因为我们交换了两个元素，并且它们之间涉及项目的反转次数必须是偶数）。因此，如果您知道空方格必须经过偶数步才能达到其最终状态，那么排列也必须是偶数。否则，您将以最终状态的奇数排列结束，这必然与其不同。与空方块的奇数步数相同。

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

根据您提供的维基百科链接，上述标准对于给定的谜题是可解的来说是充分且必要的。

回答by MrSmith42

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

在A *算法是保证找到的（一个，如果有超过一个等于短的）最短的解决方案，如果你的启发式总是低估真实成本（在你的情况所需要移动到解决方案的实数）。

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.

使用 A* 的真正艺术是找到一种总是低估实际成本但尽可能少地加快搜索速度的启发式方法。

---

---

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)

1. 在我脑海中出现的一个非常简单但有效的启发式方法是空字段到其最终目的地的曼哈顿距离。
2. 每个场到其最终目的地的曼哈顿距离的总和除以一次移动中可以改变位置的最大场数。（我认为这是一个很好的启发式）

回答by David

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

对于任何人，我将尝试解释 OP 如何获得值对以及他如何确定突出显示的值，即反转，因为我花了几个小时才弄明白。首先是对。首先将目标状态想象成一个一维数组（例如A）[1,2,3,8,0,4,7,5]。该数组中的每个值在表中都有它自己的列（一直向下，这是该对的第一个值。）然后在数组中向右移动 1 个值（i + 1）并一直走再次下降，第二对价值。例如（状态 A）：第一列，第二个值将从 [2,3,8,0,4,7,5] 开始向下。第二列，将开始 [3,8,0,4,7,5] 等。

okay now for the inversions. for each of the 2 pair values, find their INDEXlocation in the start state. if the left INDEX> right INDEXthen 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.

现在可以反转了。对于 2 对值中的每一个，在开始状态中找到它们的INDEX位置。如果左边的INDEX> 右边的INDEX那么它是一个倒置（突出显示）。前四对状态 A 是： (1,2),(1,3),(1,8),(1,0)
1 在索引 3
2 在索引 0
3 > 0 所以反转。

1 is 3
3 is 2
3 > 2 so inversion

1 是 3
3 是 2
3 > 2 所以反转

1 is 3
8 is 1
3 > 2 so inversion

1 是 3
8 是 1
3 > 2 所以反转

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

1 是 3
0 是 7
3 < 7 所以没有反转

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!

对每一对执行此操作并计算总倒置。如果两者都是偶数或都是奇数（空白点的曼哈顿距离和总倒数），那么它是可解的。希望这可以帮助！