欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蛇形魔方的计算机求解(DFS)

程序员文章站 2024-03-12 15:54:50
...

蛇形魔方:

蛇形魔方的计算机求解(DFS)

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

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

相关标签: new