蛇形魔方的计算机求解（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