于是，我开始练一些算法和编程大学开始前，我就遇到了这个问题：

So I started practicing some algorithms and programming before university starts and I ran into this problem:

鉴于含从0至8的编号，一个3×3矩阵，求到矩阵以下面的格式进行排序所需的步骤的最低数目：

Given a 3x3 matrix containing the numbers from 0 to 8, find the minimum number of steps required to sort the matrix in the following format:

1 2 3 4 5 6 7 8 0

1 2 3 4 5 6 7 8 0

在一招是只允许选择一个小区，在相邻地包含0的单元和交换这两个单元。

In one move it is only allowed to pick a cell that is adjacent to the cell which contains the 0 and swap those two cells.

现在，我真的坚持这一个，不知道如何开始。任何提示和想法让我开始是AP preciated。

Now, I am really stuck with this one and have no idea how to begin. Any tips and ideas to get me started are appreciated.

这是不做作业，如果有人认为这种方式，我只是想锻炼身体，通过移动到更严厉的问题，我被困。我不是在寻找的人写的code对我来说，我只需要在正确的方向上的点，因为我真的想了解这背后的算法。谢谢你。

This is not homework if anyone thinks that way, I am just trying to exercise and by moving to tougher problems I got stuck. I am not looking for anyone to write the code for me, I just need a point in the right direction because I really want to understand the algorithm behind this. Thank you.

推荐答案

注意：这实际上是一个人工智能的问题，而不是一个简单的数据结构/算法问题。

Note: This is actually an AI problem, and not a trivial data structure/algorithm problem.

这个问题被称为正解谜的问题。你的问题的例子是 8拼图的问题。

This problem is called the n-puzzle problem. The example in your question is the 8-puzzle problem.

要解决这个问题的方法是设法洗牌框的方式，每一步都让你更接近你的最终目标。认为这是一个贪婪的方法（最佳优先搜索）。在这里使用的最佳算法是 A *算法。

The way to solve this problem is by trying to shuffle the boxes in a way that each step gets you closer to your final goal. Think of this as a Greedy approach (Best-first search). The best algorithm to use here is the A* algorithm.

我们定义的游戏状态是板位置，数量   作出到达板位置移动，而previous状态。第一，   插入的初始状态（初始板，0移动，和一个空   previous状态）到优先级队列。然后，从优先删除   排队状态的最低优先级，并插入到   优先级队列中的所有邻国（那些可以在到达   一招）。重复这个过程，直到离队的状态是目标   州。这种方法的成功取决于优先的选择   函数的状态。我们认为两个优先功能：

We define a state of the game to be the board position, the number of moves made to reach the board position, and the previous state. First, insert the initial state (the initial board, 0 moves, and a null previous state) into a priority queue. Then, delete from the priority queue the state with the minimum priority, and insert onto the priority queue all neighboring states (those that can be reached in one move). Repeat this procedure until the state dequeued is the goal state. The success of this approach hinges on the choice of priority function for a state. We consider two priority functions:   

海明优先功能。在错误的位置块的数量，再加上迄今所取得的移动次数来获得的状态。 Intutively，用少量的在错误的位置块的状态接近的目标状态，和我们preFER已使用少量的举动达到的状态。

Hamming priority function. The number of blocks in the wrong position, plus the number of moves made so far to get to the state. Intutively, a state with a small number of blocks in the wrong position is close to the goal state, and we prefer a state that have been reached using a small number of moves.

曼哈顿优先功能。的距离从块到其目标位置，加上迄今所作的移动次数的总和（垂直和水平距离的总和）去的状态。

Manhattan priority function. The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state.

的初始状态。例如，汉明和曼哈顿的优先事项   下面是5和10，分别

For example, the Hamming and Manhattan priorities of the initial state below are 5 and 10, respectively.

 8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
 4     2        4  5  6     ----------------------    ----------------------
 7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3

 initial          goal         Hamming = 5 + 0          Manhattan = 10 + 0

我们做好一键oberservation：从给定的状态，解决了这个难题   在优先级队列中，移动总数我们需要使   （包括那些已经作出）是至少它的优先权，使用任一   海明或曼哈顿优先功能。 （对于海明的优先级，   这是真的，因为每块是不合时宜的，必须移动在   至少一次到达其目标位置。曼哈顿优先，这是   真的，因为每个块必须从它的目标的曼哈顿距离   位置。请注意，我们计算时不计空块   海明或曼哈顿的优先级。）

We make a key oberservation: to solve the puzzle from a given state on the priority queue, the total number of moves we need to make (including those already made) is at least its priority, using either the Hamming or Manhattan priority function. (For Hamming priority, this is true because each block that is out of place must move at least once to reach its goal position. For Manhattan priority, this is true because each block must move its Manhattan distance from its goal position. Note that we do not count the blank tile when computing the Hamming or Manhattan priorities.)

因此​​，只要我们出列一个国家，我们不仅   发现招式的顺序从最初的主板到电路板   与国家相关的，而是一个使最少的   移动。

Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves from the initial board to the board associated with the state, but one that makes the fewest number of moves.

（来源）