1.八数码问题
在一个3×3的棋盘上，放置编号为1~8的8个方块，每个占一格，另外还有一个空格。与空格相邻的数字方块可以移动到空格里。
任务1：指定初始棋局和目标棋局，计算出最少的移动步数；
任务2：输出数码的移动序列。
输入案例二维棋盘压缩成一维，输入的 x 表示空格
第一行输入初始棋盘，第二行输入目标前
23415x768
12345678x
输出案例
空格移动的步骤：上左左下下右上右下左左上右右下左上右下
空格移动的步数为：19
???? BFS
Cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
string li[4] = {"上", "右", "下", "左"};
int bfs(string s,string end)
{
queue <string> q;
unordered_map<string, int> dist;
unordered_map<string, string> list;
dist[s] = 0;
list[s] = "";
q.push(s);
while (q.size())
{
string t = q.front();
q.pop();
int dis = dist[t];
string lis = list[t];
if (t == end)
{
puts(lis.c_str());
return dis;
}
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (0 <= a && a < 3 && 0 <= b && b < 3)
{
swap(t[k], t[a * 3 + b]);
if (!dist.count(t))
{
dist[t] = dis + 1, q.push(t);
list[t] = lis + li[i];
}
swap(t[k], t[a * 3 + b]);
}
}
}
puts("无解！！");
return -1;
}
int main()
{
string start,end;
cin >> start >> end;
// for (int i = 1; i <= 9; i ++ )
// {
// string s;
// cin >> s;
// strat += s;
// }
int steps = bfs(start,end);
if(steps != -1)
cout << "总步数为：" << steps;
return 0;
}
Java
import java.util.*;
public class 八数码
{
// 位移数组
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static String[] move = { "上", "右", "下", "左" };
static String end;// 终点
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String start = sc.next();
end = sc.next();
int steps = bfs(start);
if (steps != -1)
System.out.println("空格移动的步数为：" + steps);
}
private static int bfs(String start)
{
LinkedList<String> q = new LinkedList<>();// BFS当前层的队列
HashMap<String, Integer> dist = new HashMap<>();// 步骤数
HashMap<String, String> list = new HashMap<>();// 存移动的历史记录
dist.put(start, 0);
list.put(start, "");
q.add(start);
while (!q.isEmpty())
{
String t = q.poll();
int steps = dist.get(t);// 当前的步骤数
String path = list.get(t);// 移动的历史记录
if (end.equals(t))// 说明到达终点
{
System.out.println("空格移动的步骤：" + path);
return steps;
}
int k = t.indexOf('x');// 找到当前的空格位置
int x = k / 3;
int y = k % 3;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i];// 要移动到的横坐标
int yy = y + dy[i];// 要移动到的纵坐标
if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
{
String newStr = swap(t, k, xx * 3 + yy);// 移动
if (!dist.containsKey(newStr))// 去重
{
dist.put(newStr, steps + 1);// 步数 + 1
// q.push(newStr); //错误示例：将元素加入队首
q.add(newStr);// 将元素加入队尾
list.put(newStr, path + move[i]);// 记录操作步骤
}
}
}
}
System.out.println("无解！");
return -1;
}
/**
* 交换字符串 s 中 a，b下标的字符，并返回交换后的字符串
*/
private static String swap(String s, int a, int b)
{
char[] ss = s.toCharArray();
char t = ss[a];
ss[a] = ss[b];
ss[b] = t;
return String.valueOf(ss);
}
}
???? 双向BFS
import java.util.*;
public class 八数码plus
{
static class Pair
{
int d;// 当前点到终点估计的距离
String sta;// 存当前的状态
public Pair(int d, String sta)
{
super();
this.d = d;
this.sta = sta;
}
}
static class Pair2
{
String s;
String c;
public Pair2(String s, String c)
{
super();
this.s = s;
this.c = c;
}
}
// 返回 状态m 中 1-8 中每个数 到 终点的 位置 的哈夫曼距离 之和
static int f(String m)
{
int dt = 0;
for (int i = 0; i < 9; i++)// 枚举当前状态的每个坑位对应的数
if (m.charAt(i) != 'x')//
{
int t = m.charAt(i) - '1';// t 当前坑位上的数
// t 的 终点位置 (t/3,t%3), t 的当前位置(i/3,i%3),求哈夫曼距离
dt = dt + Math.abs(i / 3 - t / 3) + Math.abs(i % 3 - t % 3);
}
return dt;
}
// 交换 x 中 a,b两个位置上的字符
static String swap(String s, int a, int b)
{
char[] cc = s.toCharArray();
cc[a] = s.charAt(b);
cc[b] = s.charAt(a);
String res = String.valueOf(cc);
return res;
}
static String bfs(String start, String end)
{
HashMap<String, Integer> d = new HashMap<>();// 存距离<状态,距离>
// 小根堆实现 A星 BFS
PriorityQueue<Pair> heap = new PriorityQueue<>((o1, o2) -> o1.d - o2.d);
// 存路径（当前状态的上一状态 + 操作类型）
HashMap<String, Pair2> pre = new HashMap<>();
// char[] op = { 'u', 'd', 'l', 'r' };// 四种交换操作
String[] op = { "上", "下", "左", "右" };// 四种交换操作
// 四个方向，必须与四种交换操作一一对应
int[] dx = { -1, 1, 0, 0 };
int[] dy = { 0, 0, -1, 1 };
heap.add(new Pair(f(start), start));// 起点进堆
d.put(start, 0);// 距离初始化为 0
while (!heap.isEmpty())
{
// 取出当前距离最近的点,出堆的点距离已经确定为最优解
Pair t = heap.poll();
String sta = t.sta;// 当前状态
if (sta.equals(end))// 终点出队就退出
break;
int x = 0, y = 0;// 记录 x 的坐标
for (int i = 0; i < 9; i++)
if (sta.charAt(i) == 'x')
{
x = i / 3;
y = i % 3;
break;
}
// 宽搜四种交换方案
for (int i = 0; i < 4; i++)
{
// xx,yy求新的 x 的坐标
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx > 2 || yy < 0 || yy > 2)// 非法越界
continue;
String newsta = swap(sta, xx * 3 + yy, x * 3 + y);// 交换后的状态
// 新状态以前没有搜到过 || 之前的距离大于当前状态 sta 交换到 newsta 的距离
if (!d.containsKey(newsta) || d.get(newsta) > d.get(sta) + 1)
{
d.put(newsta, d.get(sta) + 1);// 更新当前距离
// 把 起点到 newsta的距离 + 预测newsta到终点的距离 和当前状态放入堆中
heap.add(new Pair(f(newsta) + d.get(newsta), newsta));
// 记录 newsta 的上一个 转移状态 和 对应的交换操作
pre.put(newsta, new Pair2(sta, op[i]));
}
}
}
String ans = "";
while (end != start)
{
ans += pre.get(end).c;
end = pre.get(end).s;
}
ans = new StringBuffer(ans).reverse().toString();
return ans;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String start = sc.next();
String end = sc.next();
// String end = "12345678x";// 表示终点
String step = bfs(start, end);
System.out.println("需要移动的步数为：" + step.length() + "\n空格移动序列为：" + step);
}
}
2.八皇后问题
在棋盘上放置8个皇后，使它们不同行、不同列、不同对角线。问有多少种合法的情况。
答：92种
???? Java版
public class 八皇后
{
// 版本2(从左上到右下，按格子放皇后)
static int N = 20; // 由于斜线的原因，至少开 2n-1 的空间
static int n; // n皇后问题
static char[][] g = new char[N][N]; // 存储皇后的信息
// 布尔类型默认值为 flase
static boolean[] col = new boolean[N]; // 列
static boolean[] row = new boolean[N]; // 列
// 正对角线 u = -i + b --> b = u + i
static boolean[] dg = new boolean[N];
// 反对角线 u = i + b --> b = u - i 但是 b 不能小于0，所以b = n - (u - i) = n - u + i
static boolean[] udg = new boolean[N];
static int cnt = 0;// 记录方案数
/**
* @param x 行
* @param y 列
* @param s 皇后个数
*/
static void dfs(int x, int y, int s)
{
if (y == n)
{// 列标 溢出
y = 0;
x++;// 转到下一行
}
if (x == n)
{
if (s == n)
{ // 放满8个皇后
print();
}
return;
}
// 不放皇后
dfs(x, y + 1, s);
// 放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}
// 输出当前棋盘
private static void print()
{
System.out.println("方案" + ++cnt);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
System.out.print(g[i][j]);
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args)
{
n = 8;// 八皇后
// 初始化棋盘
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0, 0, 0);
System.out.println("总方案数为：" + cnt);
}
}
???? C语言版
#include <stdio.h> // 包含标准输入输出库的头文件
#define N 20 // 定义一个常量N，代表棋盘大小
int n; // 定义一个全局变量n，表示棋盘的行数和列数
char g[N][N]; // 定义一个二维字符数组g，用于表示棋盘
int col[N], row[N], dg[N], udg[N]; // 定义四个数组，用于标记列、行和两个对角线是否已经放置了皇后
int cnt = 0; // 定义一个全局变量cnt，用于记录方案的数量
// 打印当前棋盘状态的函数
void print() {
printf("方案%d\n", ++cnt); // 打印方案编号
for (int i = 0; i < n; i++) { // 遍历每一行
for (int j = 0; j < n; j++) { // 遍历每一列
printf("%c", g[i][j]); // 打印当前格子的状态
}
printf("\n"); // 每打印完一行后换行
}
printf("\n"); // 每打印完一个方案后换行
}
// 深度优先搜索函数，用于搜索所有可能的皇后放置方案
void dfs(int x, int y, int s) {
if (y == n) { // 如果y坐标达到n，说明一行已经放置完毕
y = 0; // 重置y坐标，开始新的一行
x++; // 移动到下一行
}
if (x == n) { // 如果x坐标达到n，说明已经放置了n个皇后，找到一个方案
if (s == n) { // 检查是否所有皇后都已放置
print(); // 如果是，打印当前方案
}
return; // 结束递归
}
dfs(x, y + 1, s); // 递归调用，尝试在当前行下一个位置放置皇后
// 检查当前位置是否可以放置皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q'; // 放置皇后
row[x] = col[y] = dg[x + y] = udg[x - y + n] = 1; // 标记当前位置已放置皇后
dfs(x, y + 1, s + 1); // 递归调用，尝试放置下一行的皇后
row[x] = col[y] = dg[x + y] = udg[x - y + n] = 0; // 回溯，撤销当前位置的皇后
g[x][y] = '.'; // 恢复棋盘状态
}
}
int main() {
n = 8; // 设置棋盘大小为8
for (int i = 0; i < n; i++) // 初始化棋盘，所有格子状态为'.'
for (int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0, 0, 0); // 从棋盘左上角开始深度优先搜索
printf("总方案数为：%d\n", cnt); // 打印所有可能的皇后放置方案总数
return 0; // 程序结束
}