algorithm - 使用两个 3x3 矩阵解决游戏

Question

我有两个 3x3 矩阵。一个代表实际状态，另一个代表“当前”状态。

Actual state -> 1,2,3
                5,7,6,
                9,8,x

Current state1 -> 3,1,2
                  x,6,7
                  8,9,4

我需要通过仅交换元素 x 及其在水平或垂直方向上的相邻元素来使当前状态矩阵恢复到原始状态。(不允许对角线)。

E.g. Current state 2 can be x,1,2  or 3,1,2 
                            3,6,7     6,x,7  
                            8,9,4     8,9,4 

我可以解决它直到它达到这个状态

current state n -> 1,2,3
                   5,7,6
                   8,9,x

在此之后我不知道如何进入原始状态，即交换两个元素。你能帮我吗？

谢谢

Answer 1

因此，假设您正在谈论这样的拼图(只是更小)

alt text http://www.maukatoyventures.com/images/T/Number%20Puz%20Wall%20Panel.jpg

然后您可以使用大多数图搜索算法(深度优先搜索、广度优先搜索、A*，如果您愿意的话)来解决它。这些有一个很好的概述，因为它们适用于这个特定问题 here .网络上也有大量关于所有这些的信息。