蛇形魔方的计算机求解（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个解法，但是因为旋转对称性，实际上就是唯一解。