logo标签列表

6*6 拼图算法

algorithmpuzzle
7
我有一个6*6的拼图，上面有35个数字（1~35）以随机顺序排列。使用空白格作为“寄存器”，逐个移动数字，使它们按顺序排列。我可以处理3*3的拼图，但如何处理6*6的呢？你能给我一些提示吗？ enter image description here
2
你如何处理3x3的情况？ - Niklas B.
2
任何随机序列？甚至是无法解决的序列？ - harold
2
@TylerCrompton：2x2的简单例子：[[2,1],[3, ]]。所有可能的拼图中有一半是无解的。 - Kendall Frey
4
3x3算法应该能够完美地扩展到6x6版本。 - Kendall Frey
你需要找到最短的移动序列还是任何可行的序列都可以？ - harold
显示剩余11条评论
5个回答
7
这个想法很简单，将问题表示为一个状态图形，并运行最短路径算法。
如果算法的效率很重要，您可能需要一个知情的算法，例如A *算法，它预计会相当快（相对于其他选择），具有良好的可接受启发式函数。较慢但更简单的解决方案可以是运行一个BFS。
这两种算法（A *，BFS）都是完整的（始终找到解决方案，如果存在）和最优的（找到最短路径）。
还要注意，您可以使用宏来学习“好”的移动系列，以使算法更快。在实现工作（尽管较慢）的解决方案之前，请忽略此改进。
编辑：编码指南：
将问题视为图形：图形将为G =（V，E），其中V = {所有可能的状态} 和E = {（u，v）|可以在单个步骤内从状态u移动到状态v} 现在，有了这个图形-您有一个起始位置（源，作为输入给出）和一个目标（排序后的拼图）。开始BFS或A *（请查看这些附加维基百科链接中的伪代码），以找到从源到目标的路径。您应该从BFS开始-它更简单。
最短路径算法返回的路径与您必须执行的移动系列相同，以便从起始板到达目标。
注意：您不需要创建实际的图形！您只需要保留起始节点（源）-并创建其顶点，并具有一个successors:V->2^V函数，该函数为每个顶点提供后继项（正式：successors(v) = {（v，u）|（v，u）在E中} ）。通过这种方式，您可以即时构建图形的相关部分。
1
在这么小的矩阵中，效率可能不是问题，特别是如果它是一个作业或学习问题。 - Robert Harvey
说实话，我不知道如何解决这个问题，而且这个答案也没有帮助。非常高层次的伪代码是展示如何解决问题的好方法。 - Tyler Crompton
3
由于存在36!/2种可能状态且解决方案可能需要数百步，我怀疑Dijkstra或BFS速度不够快。 - interjay
@TylerCrompton：我尝试添加有关此方法的编码准则的解释-您觉得这更有帮助吗？ - amit
@amit 我用这种方法解决了一个15x15的方块。尝试过A和BFS，BFS非常慢，并且无法完成。另一方面，如果所需步骤的数量不太大，使用A算法可以完成，但是当初始状态与目标状态相差很远时会失败（堆栈溢出）。 - user844541
显示剩余4条评论
1

我在大学时研究过这个问题/难题，它涉及到人工智能、启发式技术和图论，非常有趣。正如阿米特所说，强烈建议您检查A*、BFS和启发式算法。

以下是我的贡献：在尝试解决这个问题时，您可以尝试一种“分而治之”的策略。您可以认为这个6x6的网格只是四个3x3的网格紧密耦合在一起，并尝试按给定顺序将每个网格作为单独的情况来解决。

例如，您可以尝试以下算法：

  1. 将拼图块排列成左上角网格包含除一个以外的所有拼图块（该拼图块将用作工作空间）；
  2. 解决左上角网格；
  3. 将右上角网格排列成包含除右下角一个以外的所有拼图块（该拼图块将用作工作空间）；
  4. 解决右上角网格；
  5. ...以此类推，无论网格数量如何！
最后要说的是，你必须注意选择哪个角落作为工作空间，因为你不能让右上角的缺口成为你的工作空间“遗漏的拼图块”，因为未来将无法在那里放置拼图块；
Ps1：工作空间是你暂时放置缺失拼图块的位置，以便有一个自由的空间来操纵拼图块；
Ps2：在这个背景下，网格是NxN拼图块的组合，它们都有正确的拼图块，但不一定按顺序排列。
希望我能以某种方式帮到你。 :-)
0
我使用插入排序算法解决了上述难题。我花了将近两天时间来解决这个难题。如果您有任何问题，请运行下面的.Net代码并给我留言。我没有使用任何C#内置类来解决上述问题，这是一个纯C逻辑代码解决方案。
 private static void MazePuzzle()
        {
            /****
         * A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days.
         * Problem is about Sorting a 2D Matrix with any number of row and column
         * This problem is also known as Rat Maze puzzle
         * It is also be a typical Backtracking Problem
         * ***/
            const int _row = 6;
            const int _coloumn = 6;
            //int _column1 = _coloumn;

            int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } };
            int [] _StoringArray1D=new int[_row*_coloumn];
            int i = 0;
            int j = 0;
            int _comparingArrayElement = 0;
            int _swipeTemp = 0;


            for (; i < _row; i++)
            {
                int _trackrow = 0;
                for (;j <_coloumn; j++)
                {
                    _trackrow = 0;
                    if(i==0 && j==0)
                    {
                          _comparingArrayElement= _doubleArray[i, j + 1];
                        if(_comparingArrayElement<_doubleArray[i,j])
                        {
                             _swipeTemp = _doubleArray[i,j+1];
                             _doubleArray[i, j + 1] = _doubleArray[i, j];
                             _doubleArray[i, j] = _swipeTemp;

                        }//innerMost if
                    }//For First time
                        else
                        {
                            int k = 0;
                            do
                            {
                                if (_trackrow == i || _trackrow < i)
                                {
                                    for (; k < _coloumn; k++)
                                    {
                                        if(k==j && i==_trackrow)
                                        {
                                            break;
                                        }
                                        else
                                        {
                                        if(_doubleArray[_trackrow,k]>_doubleArray[i,j])
                                        {
                                            int _swipetempPrevious=_doubleArray[_trackrow,k];
                                            _doubleArray[_trackrow,k]=_doubleArray[i,j];
                                            _doubleArray[i, j] = _swipetempPrevious;
                                        }
                                        else
                                        {
                                            //do nothing just traverse
                                        }//swipe else
                                        }//k==j else
                                    }//inner for do while
                                    _trackrow++;
                                    k = 0;
                                }//trackrow if
                                else
                                {
                                    break;
                                }//trackrow else
                            } while (true);
                        }//else
                }//innner for
                j = 0;
            }//outer for
            Console.WriteLine("End of Program");
        }//Maze Puzzle Method
0

我认为如果我们一次遍历整个6*6矩阵，我们只能找到一个小数并将其移动到下一个矩阵，这不是一个相关的解决方案。更好的解决方法是在给定的矩阵上使用二分查找。如果我们应用二分查找，则时间复杂度会很高。那么解决这个问题的更好方法是什么？

请大家查看以下代码。以下代码是上述问题的解决方案。我使用插入排序解决了上述问题，无需使用BFS或任何其他东西。 - Prince Sanghi
0
这个游戏的简单策略是将正确的数字放在顶行（应该很容易，因为您不需要考虑其他数字，最后两个数字有点难以放置在正确的位置，因为您必须在同一次移动中放置它们），然后冻结顶行并继续进行左列、顶行和左列...
这不是最优策略，但它是一个可行且编码简单的策略。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接