我有一个 6*6 的拼图，随机排列有 35 个数字（1~35）。将空白的数字用作“寄存器”并将数字一一移动以使它们按顺序排列。我可以处理一个 3*3 的拼图，但是如何处理一个 6*6 的拼图呢？你能给我一些提示吗？
问问题
2222 次
5 回答
7
如果算法的效率很重要，您可能需要一个明智的算法 - 例如 A* 算法，预计它会非常快（相对于替代方案）并具有良好的可接受启发式函数。
一个更慢但更简单的解决方案可以运行BFS。
两种算法（A*、BFS）都是完整的（如果存在，总是找到解决方案）和最优的（找到最短路径）。
另请注意，您可以使用宏来学习“好的”系列动作，以更快地获得算法。在您实施有效（虽然缓慢）的解决方案之前，请忽略此改进。
编辑：编码指南：
将问题视为图表：图表将在G=(V,E)哪里V = { all possible states}和E = { (u,v) | can move from state u to state v within a single step }
现在，有了这个图 - 你有一个起始位置（源，作为输入给出）和一个目标（一个排序的谜题）。启动 BFS 或 A*（在附加的 wikipedia 链接中查看这些伪代码），以找到从源到目的地的路径。你应该从 BFS 开始——它更简单。
最短路径算法返回的路径与从起始板到目标必须执行的一系列移动相同。
注意：您不需要创建实际的图表！你只需要 a 来保存起始节点（源） - 并创建它的顶点，并拥有一个successors:V->2^V函数，它为你提供每个顶点的后继节点（正式地：）successors(v) = { (v,u) | (v,u) is in E }。这样，您可以即时构建图表的相关部分。
于 2012-06-20T15:34:03.953 回答
1
我在大学时研究过同样的问题/谜题，这是一个非常有趣的问题，涉及人工智能、启发式技术和图论。如amit所述，强烈建议您检查 A*、BFS 和启发式。
这是我的贡献：当试图解决这个问题时，你可以尝试分而治之的策略。你可以认为这个 6x6 网格只是四个相互靠近的 3x3 网格，并尝试按照给定的顺序将每个网格作为单独的案例来解决。
例如，您可以尝试以下算法：
- 以左上网格包含所有作品的方式排列你的作品，除了一个（将用作工作空间）；
- 求解左上网格；
- 以包含所有部分的方式排列右上网格，除了右下角的网格（将用作工作空间）；
- 求解右上网格；
- ...等等，与网格数量无关！
最后要说的是，你必须注意你要留下哪个角落作为工作空间，因为你不能让右上角网格的右上角成为你的工作空间“缺失的部分”，因为它不会将来有可能放一块；
Ps1：工作空间是您暂时让棋子错过的位置，以便能够有自由空间来操纵棋子；
Ps2：在这种情况下，网格是 NxN 块的组合，它包含所有正确的块，不一定按顺序排列。
希望我在某种程度上有所帮助。:-)
于 2012-06-20T16:06:06.323 回答
0
这个游戏的一个简单策略是将正确的数字放在第一行（这应该很容易，因为你不关心其他数字，最后两个数字更难放在正确的位置，因为你必须放置他们都在同一个动作），然后你冻结顶行并继续左列，然后是顶行，然后是左列……</p>
这不是最佳策略，但它是一种有效且易于编码的策略。
于 2012-06-20T15:54:43.750 回答
0
我已经通过使用插入排序算法解决了上述难题。我花了将近 2 天的时间来解决上述难题。如果您需要询问任何内容，只需在 .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
于 2015-04-03T07:03:52.300 回答
0
我认为如果我们一次遍历整个 6*6 矩阵，我们将只能找到一个小数字并将其移动到下一个矩阵，这不是一个相关的解决方案。解决这个问题的更好方法是在给定矩阵上使用二进制搜索。如果我们将应用二进制搜索，那么时间复杂度会很高。那么解决这个问题的更好方法是什么
于 2015-04-01T09:13:10.497 回答