蛇形魔方的计算机求解(DFS)
程序员文章站
2024-03-12 15:54:50
...
蛇形魔方:
这个玩具是要拼成正方形:
蛇形魔方很简单,不费吹灰之力即可找到解法,也很容易想明白是唯一解。
这里我用深度优先搜索算法求解。
思路和代码都很简单,就是个简单的深度优先搜索,直接上代码:
#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个解法,但是因为旋转对称性,实际上就是唯一解。
上一篇: 数据结构与算法六:图