文章目录
一、问题描述
国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中，按照“马”走日的规则将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘的64个方格。
给定起始位置，由该点位起点，输出能走遍棋盘的每一步的足迹
二、问题分析
首先要了解马的移动规则，在正常情况下，马是有八个可供选择的移动方向的。
用二维数组来表示棋盘，棋盘的行就是x，列就是y
在这里，马的坐标是（3，3），而马能走的八个坐标如下：
( 3+1 , 3+2 ) , ( 3-1 , 3+2 ) , ( 3+1 , 3-2 ) , ( 3-1 , 3-2 )
( 3+2 , 3+1 ) , ( 3-2 , 3+1 ) , ( 3+2 , 3-1 ) , ( 3-2 , 3-1 )
我们可以得出马移动时的偏移量，记为dir数组
int dir[8][2] = {
{
1,2},{
-1,2},{
1,-2},{
-1,-2},
{
2,1},{
2,-1},{
-2,1},{
-2,-1}
};
这样我们就可以表示出任意一点（x,y）可移动的位置
int x = 3, y = 3;
for (int i = 0; i < 8; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
printf("( %d , %d )\n", tx, ty);
}
但这样给出的坐标还并不一定是对的，可能有些坐标是已经走过的，也可能有些坐标出界了（跑到棋盘外面去了），所以我们需要作出判断
//这里的棋盘是8 * 8 的
//给棋盘开 10 * 10 的空间是为了防止意外溢出
int map[10][10]; //棋盘
int vis[10][10]; //用来表示该点是否访问过，为1表示访问过，0反之
bool in(int x , int y) //判断(x，y)是否在棋盘内
{
return x >= 0 && x < 8 && y >= 0 && y < 8;
}
for(int i = 0 ; i < 8 ; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx,ty) && !vis[tx][ty])
{
//这里表示的是：如果(tx,ty)在棋盘内且没走过，就输出该坐标
printf("( %d , %d )\n", tx, ty);
}
}
之后，我们就可以进行搜索操作了
三、深度优先搜索（Depth First Search）
1.基本原理
我们可以先采取深度优先搜索（dfs），靠穷举法找出答案 深度优先搜索类似于一条路走到黑，走错了再退回来的感觉 比如：
若要从a走到f
就是a先到b，b再到d，因为无路可走了，就回退到b，但d走过了，所以走e，走到e后发现仍是无路可走，又回退到b，此时d和e都走过了，b也没有可以选择的路径了，只能回退，回退到a点后，由于b已经走过，只能走到c，c只能走到f。这样就通过深度优先搜索从a点找到了去f点的路径。
//dfs基本框架
void dfs(/*参数按需求*/)
{
//截止条件，搜索到了就要截止了，退出函数
//标记该点已访问
//遍历候选节点且遍历时进行筛选，符合条件才可遍历
//回溯
//回溯就是让这个已经访问过的点改为没有访问过的状态
}
a走到b，发现b不能走了，回退到a，a走到c，c走到b。
c能走到b的原因就是回溯了，原本第一次走的时候，已经走过了b点，b点已经被标记走过了，但是回溯了，把b点标记成没走过了，所以c才能走到b。
如果直接a到b，不回溯，回退到a点的时候，b点的标记是走过的，则c不能到d；
小结：回溯更类似于悔棋功能，相当于重来了；不回溯则相当于往回走，这个点实际还是走过的；
/** * x,y就是相应的横纵坐标 * step就是表示现在是第几步了 **/
void dfs(int x, int y, int step)
{
map[x][y] = step;//将step的值赋给map中（x,y）坐标里
//截止条件，如果走到了第64步，就说明把棋盘走遍了，结束函数
if (step == 64)
{
//将棋盘打印出来
printMap(); //这是个自定义的函数
printf("\n\n");
return;
}
vis[x][y] = 1; //将此点标记为已经走过
for (int i = 0; i < 8; i++)
{
int tx = dir[i][0] + x;
int ty = dir[i][1] + y;
if (in(tx, ty) && !vis[tx][ty])
{
//如果（tx,ty）在棋盘里面且没走过，则对它进行下一步的判断
//意思就是直接走(tx,ty)这个点，到了这个点之后，再展开一次搜索
dfs(tx, ty, step + 1);
}
}
//回溯
vis[x][y] = 0;
map[x][y] = 0;
}
2.代码预览
#define _CRT_SECURE_NO_WARNINGS //防止scanf_s报错
#include<stdio.h>
int map[10][10]; //棋盘
int dir[8][2] = {
{
1,2} ,{
-1,2},{
1,-2},{
-1,-2},
{
2,1},{
2,-1},{
-2,1},{
-2,-1}
};
int vis[10][10]; //判断该点是否已走
bool f; //判断是否已经找到答案
bool only = false; //如果需要输出多个答案，就把only改成false；反之为true
//打印棋盘
void printMap()
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
printf("%4d", map[i][j]);
}
printf("\n\n");
}
return;
}
bool in(int x, int y) //判断(x，y)是否在棋盘内
{
return x >= 0 && x < 8 && y >= 0 && y < 8;
}
/** * x,y就是相应的横纵坐标 * step就是表示现在是第几步了 **/
void dfs(int x, int y, int step)
{
if (f && only) return;
map[x][y] = step;//将step的值赋给map中（x,y）坐标里
//截止条件，如果走到了第64步，就说明把棋盘走遍了，结束函数
if (step == 64)
{
//将棋盘打印出来
printMap(); //这是个自定义的函数
printf("\n\n");
f = true;
return;
}
vis[x][y] = 1; //将此点标记为已经走过
for (int i = 0; i < 8; i++)
{
int tx = dir[i][0] + x;
int ty = dir[i][1] + y;
if (in(tx, ty) && !vis[tx][ty])
{
//如果（tx,ty）在棋盘里面且没走过，则对它进行下一步的判断
//意思就是直接走(tx,ty)这个点，到了这个点之后，再展开一次搜索
dfs(tx, ty, step + 1);
}
}
//回溯
vis[x][y] = 0;
map[x][y] = 0;
}
void run()
{
int x, y;
printf("请输入起始位置：");
scanf("%d%d", &x, &y);
if (!in(x, y)) //如果(x,y)不在棋盘里，返回真
{
printf("\n\nERROR：起始位置输入有误！！！\n\n");
return;
}
printf("\n\n");
dfs(x, y, 1);
}
int main()
{
run();
return 0;
}
四、dfs+贪心算法
1.贪心策略
正常情况，走下一步是按dir数组顺序，一个一个找可以移动的位置，然后移动，这样移动和随机区别不大。
而本题的贪心策略就是：选择后续节点最少的那一个位置移动，哪一个点的下一步少，就选哪个点
例如：A可以走到B，C，D。B可以移动的位置有5个，C可以移动的位置有2个，D可移动的位置有6个。那A就是选后续节点最少的位置移动，也就是移动到C点。
2.贪心原理
一个点的后续点位越少，就越应该先选。 它的后续点位本来就少，如果不先选了，把后续点位给占了，那么之后该点后续点位被走过了的话，之后你再选该点，就很容易出现无路可走的情况，然后就只能回溯了。但回溯又十分影响效率，所以，为了减少回溯的情况，我们就先把那些之后容易发生回溯的点给先踩过了，这样回溯情况就少了。
举个栗子： A点可以走B，C位置，B有一个后续节点（到B之后能走的就一个方向了）。A走C，它的后续节点很多，但可能包含了B点的后续点位，如果它把B的后续节点给踩了，以后踩到B点了，那B点就无路可走了，就必须要回溯了
3.核心代码
//next数组的初始化值都是0
int next[8] = {
0,0,0,0,0,0,0,0};
void getNext(int x, int y, int* next) //获得后续点位数量的数组
{
for (int i = 0; i < 8; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty)) //这里其实也有 && !vis[tx][ty]的，不过把&& !vis[tx][ty]写到了in数据里面
{
for (int j = 0; j < 8; j++)
{
int ttx = tx + dir[j][0];
int tty = ty + dir[j][1];
if (in(ttx, tty))
{
next[i]++; //统计每个移动方向后续点位个数
}
}
}
}
}
之后我们就要让后续节点更少的先走，所以我们可以进行排序操作
//获得next数组从小到大的，但是值是次序
//比如：next[8] = {3,2,5,1,1,0,1,0};
//那么seq数组就是 {5,7,3,4,6,1,0,2}
//第一个是5，是因为next[5] = 0,第二个是7，是因为next[7] = 0;以此类推
int seq[8] = {
0,1,2,3,4,5,6,7};
void getSeq(int* next, int* seq)
{
int n[8];
for (int i = 0; i < 8; i++)
n[i] = next[i];
//防止原本的next数组被排序，复制个next数组来排序就可
//冒泡排序，不过捆绑了Seq数组，当然，这里也可以用结构体实现
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7 - i; j++)
{
if (n[j] > n[j + 1])
{
int t = n[j];
n[j] = n[j + 1];
n[j + 1] = t;
//n数组交换时，让seq数组进行同样的交换
t = seq[j];
seq[j] = seq[j + 1];
seq[j + 1] = t;
}
}
}
}
4.代码预览
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define ROW 8
#define COL 8
bool only = true; //only为true表示只输出一种结果，反之多种
bool f = false; //判断是否已经找到答案
int map[ROW + 5][COL + 5]; //棋盘
int vis[ROW + 5][COL + 5]; //标记该位置是否已经落子
int dir[8][2] = {
{
-1,2},{
-1,-2}, {
1,-2}, {
1,2}, {
-2,1},{
2,-1}, {
-2,-1}, {
2,1} };
bool in(int x, int y) //在棋盘里，且该位置没棋子
{
return x >= 0 && x < ROW&& y >= 0 && y < COL && !vis[x][y];
}
//需要注意的是，这里的in函数里面整合了 !vis[x][y]
void printMap() //打印棋盘
{
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
printf("%4d", map[i][j]);
}
printf("\n\n");
}
printf("\n\n");
}
void printArray(int* num, int size, const char* str) //打印数组，用于调试
{
printf("%5s:", str);
for (int i = 0; i < size; i++)
{
printf("%4d", num[i]);
}
printf("\n\n");
}
//next数组的初始化值都是0
void getNext(int x, int y, int* next) //获得后续点位数量的数组
{
for (int i = 0; i < 8; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty))
{
for (int j = 0; j < 8; j++)
{
int ttx = tx + dir[j][0];
int tty = ty + dir[j][1];
if (in(ttx, tty))
{
next[i]++; //统计每个移动方向后续点位个数
}
}
}
}
}
//获得next数组从小到大的，但是值是次序
//比如：next[8] = {3,2,5,1,1,0,1,0};
//那么seq数组就是 {5,7,3,4,6,1,0,2}
//第一个是5，是因为next[5] = 0,第二个是7，是因为next[7] = 0;以此类推
void getSeq(int* next, int* seq)
{
int n[8];
for (int i = 0; i < 8; i++)
n[i] = next[i];
//防止原本的next数组被排序，复制个next数组来排序就可
//冒泡排序，不过捆绑了Seq数组，当然，这里也可以用结构体实现
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7 - i; j++)
{
if (n[j] > n[j + 1])
{
int t = n[j];
n[j] = n[j + 1];
n[j + 1] = t;
//n数组交换时，让seq数组进行同样的交换
t = seq[j];
seq[j] = seq[j + 1];
seq[j + 1] = t;
}
}
}
}
void dfs(int x, int y, int step)
{
if (f && only)
{
return;
}
map[x][y] = step;
if (step == 64)
{
//输出
printMap();
f = true;
return;
}
vis[x][y] = 1;//标记
//这里进行深度优先搜索，采取贪心策略进行减枝优化
int next[8] = {
0,0,0,0,0,0,0,0 };
getNext(x, y, next);
int seq[8] = {
0,1,2,3,4,5,6,7 };
getSeq(next, seq);
//原本dfs是随机的找的，现在，通过贪心得到了一个seq数组，就是搜索顺序的数组
//开始搜索
for (int i = 0; i < 8; i++)
{
int tx = x + dir[seq[i]][0];
int ty = y + dir[seq[i]][1];
if (in(tx, ty))
dfs(tx, ty, step + 1);
}
//回溯
vis[x][y] = 0;
map[x][y] = 0;
}
void run()
{
int x, y;
printf("请输入起始坐标：");
scanf("%d%d", &x, &y);
if (!in(x, y))
{
printf("\n\n坐标输入错误！！！！\n\n");
return;
}
printf("\n\n");
dfs(x, y, 1);
}
int main()
{
run();
return 0;
}
五、栈+贪心
1.回溯方法
之前写的代码都是用过递归来进行回溯的，现在将用栈来进行回溯。
2.基本操作
//定义栈的结构体
typedef struct
{
int x;
int y;
int dir; //方向
}Stack;
Stack chess[ROW * COL + 5]; //存储每步的棋子位置
int top = -1; //栈顶指针
int out_stack = 0; //出栈次数
//入栈的时候会进行初始化
void push(int x, int y)
{
top++;
chess[top].x = x;
chess[top].y = y;
chess[top].dir = DIR;
map[x][y] = top + 1;//因为top是从负一开始的，而第一步是1
}
//出栈，要把栈顶数据给初始化，然后再top--；
void pop()
{
map[chess[top].x][chess[top].y] = 0;
chess[top].x = 0;
chess[top].y = 0;
chess[top].dir = DIR;
top--;
}
3.核心代码
void dfs()
{
while (1)
{
if (top >= 64 - 1) //top从0开始，【64】，最大就是63，共有64个
{
//打印棋盘
printMap();
break;
}
int x = chess[top].x;
int y = chess[top].y;
int next[8] = {
0,0,0,0,0,0,0,0 };
getNext(x, y, next);
int seq[8] = {
0,1,2,3,4,5,6,7 };
getSeq(next, seq);
bool flag = false;//用来标记是否进栈
for (int i = chess[top].dir + 1; i < 8; i++)
{
//i = chess[top].dir+1 是因为要先偏移一位，才能判断其他数据，不然当需要回溯时，先出栈，
//然后再到这个位置的时候，i还是等于之前那个需要回溯的dir，然后就成死循环了
int tx = x + dir[seq[i]][0];
int ty = y + dir[seq[i]][1];
chess[top].dir++;
if (in(tx, ty))
{
push(tx, ty);
flag = true;
break;
}
}
//如果前面8个方向已经判断完，且没有进栈，就说明目前没有方向可以走了，只能出栈
//这个dir方向中，只有输入7 5 才会发生回溯
if (chess[top].dir == 7 && flag == false)
{
out_stack++;
pop();
}
}
}
4.代码预览
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define ROW 8
#define COL 8
#define DIR -1 //方向默认为-1，-1表示不能走
int dir[8][2] = {
{
2,-1},{
-2,-1},{
-2,1},{
2,1},{
1,-2},{
-1,-2},{
-1,2},{
1,2} };
int map[ROW][COL];
//定义栈的结构体
typedef struct
{
int x;
int y;
int dir; //方向
}Stack;
Stack chess[ROW * COL + 5]; //存储每步的棋子位置
int top = -1; //栈顶指针
int out_stack = 0; //出栈次数
bool in(int x, int y)
{
return x >= 0 && x < ROW && y >= 0 && y < COL && !map[x][y];
}
//注意这里整合了 !map[x][y]
void printMap() //打印棋盘
{
printf("\n\n");
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
printf("%4d", map[i][j]);
}
printf("\n\n");
}
printf("\n\n");
}
void getNext(int x, int y, int* next)
{
for (int i = 0; i < 8; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty))
{
for (int j = 0; j < 8; j++)
{
int ttx = tx + dir[j][0];
int tty = ty + dir[j][1];
if (in(ttx, tty))
{
next[i]++;
}
}
}
}
}
void getSeq(int* next, int* seq)
{
int n[8];
for (int i = 0; i < 8; i++)
n[i] = next[i];
//防止原本的next数组被排序，复制个next数组来排序就可
//冒泡排序，不过捆绑了Seq数组，当然，这里也可以用结构体实现
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 7 - i; j++)
{
if (n[j] > n[j + 1])
{
int t = n[j];
n[j] = n[j + 1];
n[j + 1] = t;
//n数组交换时，让seq数组进行同样的交换
t = seq[j];
seq[j] = seq[j + 1];
seq[j + 1] = t;
}
}
}
}
//入栈的时候会进行初始化
void push(int x, int y)
{
top++;
chess[top].x = x;
chess[top].y = y;
chess[top].dir = DIR;
map[x][y] = top + 1;//因为top是从负一开始的，而第一步是1
}
//出栈，要把栈顶数据给初始化，然后再top--；
void pop()
{
map[chess[top].x][chess[top].y] = 0;
chess[top].x = 0;
chess[top].y = 0;
chess[top].dir = DIR;
top--;
}
void dfs()
{
while (1)
{
if (top >= 64 - 1) //top从0开始，【64】，最大就是63，共有64个
{
//打印棋盘
printMap();
break;
}
int x = chess[top].x;
int y = chess[top].y;
int next[8] = {
0,0,0,0,0,0,0,0 };
getNext(x, y, next);
int seq[8] = {
0,1,2,3,4,5,6,7 };
getSeq(next, seq);
bool flag = false;//用来标记是否进栈
for (int i = chess[top].dir + 1; i < 8; i++)
{
//i = chess[top].dir+1 是因为要先偏移一位，才能判断其他数据，不然当需要回溯时，先出栈，
//然后再到这个位置的时候，i还是等于之前那个需要回溯的dir，然后就成死循环了
int tx = x + dir[seq[i]][0];
int ty = y + dir[seq[i]][1];
chess[top].dir++;
if (in(tx, ty))
{
push(tx, ty);
flag = true;
break;
}
}
//如果前面8个方向已经判断完，且没有进栈，就说明目前没有方向可以走了，只能出栈
//这个dir方向中，只有输入7 5 才会发生回溯
if (chess[top].dir == 7 && flag == false)
{
out_stack++;
pop();
}
}
}
void run()
{
int x, y;
printf("请输入起始坐标：");
scanf("%d%d", &x, &y);
if (!in(x, y))
{
printf("\n\n坐标输入错误！！\n\n");
return;
}
push(x, y);
dfs();
printf("\n\n共回溯%d次\n\n", out_stack);
}
int main()
{
run();
return 0;
}
总结
马踏棋盘问题可以用搜索的方法解决，搜索的过程中可以通过栈或递归的方式进行回溯；普通的暴力搜索，其实就是穷举法，如果把所有可能都一一列举出来，则需要运算接近8 的64 次方 次，所以，需要优化，而这里是使用贪心的方式进行剪枝优化，将之后可能会发生回溯的点位先踩，减少回溯的情况发生。
文章评论