八数码问题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

这是最基本的bfs，运用队列来解决这类问题，需要包含头文件,然后分析题目，我们首先构建大致框架改变后期数字移动问题
建立方向函数

int dir[4][2] = {   //控制方向
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};

定义队列类型

queueq;

将八数码里的数排列成九宫格，分别记录各个x和y坐标。从起点开始各个方向移动。把移动后的结果按左右上下的顺序排列记录在队列中，通过不断的出队列和入队列，把结果和最终要求的结果进行对比，得出完成所需步数和有无完成可能。

#include
#include
using namespace std;
const int LEN = 362880;

struct node {
	int state[9];
	int dis;
};
int dir[4][2] = {   //控制方向
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};
int visited[LEN] = { 0 };
int start[9];
int goal[9];
long int factory[] = { 1,1,2,6,24,120,720,5040,40320,362880 };
bool Cantor(int str[], int n) {
	long result = 0;
	for (int i = 0; i < n; i++) {
		int counted = 0;
		for (int j = i + 1; j < n; j++) {
			if (str[i] > str[j])
				++counted;
		}
		result += counted * factory[n - i - 1];
	}
	if (!visited[result]) {					//没有被访问
		visited[result] = 1;
		return 1;
	}
	else
		return 0;
};

int bfs() {
	node head;
	memcpy(head.state, start, sizeof(head.state));
	head.dis = 0;
	queueq;
	Cantor(head.state, 9);
	q.push(head);

	while (!q.empty()) {
		head = q.front();
		if (memcmp(head.state, goal, sizeof(goal)) == 0)
			return head.dis;
		q.pop();
		int z;
		for (z = 0; z < 9; z++)
			if (head.state[z] == 0)
				break;
		int x = z % 3;
		int y = z / 3;
		for (int i = 0; i < 4; i++) {
			int newx = x + dir[i][0];
			int newy = y + dir[i][1];
			int nz = newx + 3 * newy;
			if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
				node newnode;
				memcpy(&newnode, &head, sizeof(struct node));
				swap(newnode.state[z], newnode.state[nz]);
				newnode.dis++;
				if (Cantor(newnode.state, 9))
					q.push(newnode);
			}
		}
	}
	return -1;
}
int main() {
	for (int i = 0; i < 9; i++)
		cin >> start[i];
	for (int i = 0; i < 9; i++)
		cin >> goal[i];
	int num = bfs();
	if (num != -1)
		cout << num << endl;
	else
		cout << "impossible" << endl;
	return 0;

}

钱yj