蛇形魔方的计算机求解（DFS）

蛇形魔方：

这个玩具是要拼成正方形：

蛇形魔方很简单，不费吹灰之力即可找到解法，也很容易想明白是唯一解。

这里我用深度优先搜索算法求解。

思路和代码都很简单，就是个简单的深度优先搜索，直接上代码：

      #include<iostream>
      #include<string>
      using namespace std;
      const int MaxDeep = 17;
      const int len[MaxDeep] = { 3, 2, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3 };
      #define N 3 //3*3*3
      #define M N+2 
      int board[M][M][M];//坐标分量的取值范围是1-N，0和N+1作为无效边界
      const int dx[6] = { 0, 0, 0, 0, 1, -1 };//(dx[i],dy[i],dz[i])是第i个方向的方向向量
      const int dy[6] = { 0, 0, 1, -1, 0, 0 };//6个方向分别是上下后前右左
      const int dz[6] = { 1, -1, 0, 0, 0, 0 };
      const string s[6] = { "上", "下", "后", "前", "右", "左" };
      int ans[MaxDeep];
      void init()
      {
     	for (int i = 0; i < M; i++)for (int j = 0; j < M; j++)for (int k = 0; k < M; k++)board[i][j][k] = 1;
     	for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++)for (int k = 1; k <= N; k++)board[i][j][k] = 0;
      }
      bool visit(int sx, int sy, int sz, int direc, int deep)
      {
     	if (deep == MaxDeep)return true;
     	int x = sx + dx[direc], y = sy + dy[direc], z = sz + dz[direc], le = len[deep]-1;
     	while (!board[x][y][z] && le)
      	{
      		le--, board[x][y][z] = 1, x += dx[direc], y += dy[direc], z += dz[direc];
      	}
      	x -= dx[direc], y -= dy[direc], z -= dz[direc];
     	bool flag = false;
     	if (le == 0)for (int dir = 0; dir < 6; dir++)
      	{
     		if (visit(x, y, z, dir, deep + 1))flag = true, ans[deep] = direc;
      	}
     	while (le < len[deep] - 1)
      	{
      		le++, board[x][y][z] = 0, x -= dx[direc], y -= dy[direc], z -= dz[direc];
      	}
     	return flag;
      }
      int main()
      {
     	init();
     	for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++)for (int k = 1; k <= N; k++)
      	{
      		board[i][j][k] = 1;
     		if (visit(i, j, k, 0, 0))
      		{
     			for (int i = 0; i < MaxDeep; i++)cout << s[ans[i]];
      			cout << endl << i << ' ' << j << ' ' << k << endl;
      		}
      		board[i][j][k] = 0;
      	}
     	return 0;
      }
  
 

其中，dx,dy,dz用来描述方向向量，在我的很多棋类代码中都有讲到这个flat技术。

由于6个方向的对称性，可以不妨设第一步是往上。

输出结果：

上后下右后左上右前下后左后右前上后
1 1 1
上前下右前左上右后下前左前右后上前
1 3 1
上后下左后右上左前下后右后左前上后
3 1 1
上前下左前右上左后下前右前左后上前
3 3 1

不难发现，虽然输出了4个解法，但是因为旋转对称性，实际上就是唯一解。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/104602506