我有一个6*6的拼图,上面有35个数字(1~35)以随机顺序排列。使用空白格作为“寄存器”,逐个移动数字,使它们按顺序排列。我可以处理3*3的拼图,但如何处理6*6的呢?你能给我一些提示吗?
![enter image description here](https://istack.dev59.com/oRS8q.webp)
G =(V,E)
,其中V = {所有可能的状态}
和E = {(u,v)|可以在单个步骤内从状态u移动到状态v}
现在,有了这个图形-您有一个起始位置(源,作为输入给出)和一个目标(排序后的拼图)。开始BFS或A *(请查看这些附加维基百科链接中的伪代码),以找到从源到目标的路径。您应该从BFS开始-它更简单。
successors:V->2^V
函数,该函数为每个顶点提供后继项(正式:successors(v) = {(v,u)|(v,u)在E中}
)。通过这种方式,您可以即时构建图形的相关部分。我在大学时研究过这个问题/难题,它涉及到人工智能、启发式技术和图论,非常有趣。正如阿米特所说,强烈建议您检查A*、BFS和启发式算法。
以下是我的贡献:在尝试解决这个问题时,您可以尝试一种“分而治之”的策略。您可以认为这个6x6的网格只是四个3x3的网格紧密耦合在一起,并尝试按给定顺序将每个网格作为单独的情况来解决。
例如,您可以尝试以下算法:
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
我认为如果我们一次遍历整个6*6矩阵,我们只能找到一个小数并将其移动到下一个矩阵,这不是一个相关的解决方案。更好的解决方法是在给定的矩阵上使用二分查找。如果我们应用二分查找,则时间复杂度会很高。那么解决这个问题的更好方法是什么?
[[2,1],[3, ]]
。所有可能的拼图中有一半是无解的。 - Kendall Frey