竞赛课第四周（八数码问题+八皇后问题）

本文主要是介绍竞赛课第四周（八数码问题+八皇后问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目的：

1. 掌握递归和排序

2. 掌握BFS与队列

3. 掌握DFS和递归

4. 熟悉并理解回溯问题

实验内容：

1.八数码问题：

在一个3×3的棋盘上，放置编号为1~8的8个方块，每个占一格，另外还有一个空格。与空格相邻的数字方块可以移动到空格里。

任务1：指定初始棋局和目标棋局，计算出最少的移动步数；

任务2：输出数码的移动序列。

#include <bits/stdc++.h>
using namespace std;string Start, End;  // 定义起始状态和目标状态字符串
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };  // 定义四个方向的偏移量
int stepCount = 0;  // 记录步数int bfs()
{queue<string> q;  // 使用队列进行广度优先搜索map<string, int> mp;  // 使用哈希表记录每个状态的步数mp[Start] = 0;q.push(Start);while (!q.empty()){Start = q.front();cout << Start << endl;  // 输出当前状态q.pop();stepCount = mp[Start];int FormerX, FormerY, FormerLocation;FormerLocation = Start.find('.');  // 找到空格的位置FormerX = FormerLocation / 3;  // 计算空格所在的行FormerY = FormerLocation % 3;  // 计算空格所在的列for (int i = 0; i < 4; i++){int nowX = FormerX + dx[i];int nowY = FormerY + dy[i];if (nowX > 2 || nowX < 0 || nowY > 2 || nowY < 0) // 判断是否越界continue;int NewLocation = nowX * 3 + nowY;swap(Start[NewLocation], Start[FormerLocation]);  // 交换空格和相邻位置的数字if (!mp.count(Start)){mp[Start] = stepCount + 1;if (Start == End)  // 判断是否达到目标状态return mp[Start];q.push(Start);  // 将当前状态加入队列}swap(Start[NewLocation], Start[FormerLocation]);  // 恢复原始状态}}return -1;  // 如果无法到达目标状态，返回-1
}int main()
{// 请在此输入您的代码cin >> Start >> End;  // 输入起始状态和目标状态cout << "Moving sequence: " << endl;cout << bfs() << endl;  // 调用bfs函数并输出结果return 0;
}
/*
test：
12345678.
123.46758
*/

【运行结果】

2.八皇后问题：

在棋盘上放置8个皇后，使它们不同行、不同列、不同对角线。问有多少种合法的情况。

#include <bits/stdc++.h>
using namespace std;int mapcolumn[9] = {0};
int situation = 0;bool check(int row, int column)
{for(int i=0; i<row; i++){if(mapcolumn[i] == column || abs(i-row) == abs(mapcolumn[i]-column))return false;}return true;
}void dfs(int row)
{if(row == 8){situation++;return;}	for(int column=0; column<8; column++){if(check(row, column)){mapcolumn[row] = column;dfs(row+1);}}	
}int main()
{dfs(0);cout << situation << endl;
}