马踏棋盘是栈的一个十分经典的应用，最基本的完成思路其实就是深度优先搜索(dfs)，是一种十分暴力的处理方式，费时费力还不一定可以得到一个好的结果。使用贪心算法，将每一步，每一步的下一步都进行贪心，便会节省大量的时间，而且成功率十分客观，现就马踏棋盘的一种贪心算法做以下总结
题目
设计一个国际象棋的马踏遍棋盘的演示程序。将马随机放在国际象棋 8x8 棋盘 Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。编制递归或非递归程序，求出马的行走路线，并按求出的行走路线输出。
（1）将行走路线以坐标的形式输出。
（2）在方阵中输出 1~64 个行走足迹；
数据定义
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROW 8
#define COL 8
#define MAX_STEPS ROW*COL
//栈结构体
typedef struct stack{
int x_adr; //纵坐标
int y_adr; //横坐标
int direction; //方向
}HORSE_CHESS_STACK;
//存储路径棋盘
int chess[ROW+1][COL+1];
//下一步方向
//一号
int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1},
{1,-2},{-1,-2},{-1,2},{1,2}};
//二号
/* int dir[8][2] = {{1,2},{-1,-2},{-2,1},{2,1},
* {2,-1},{1,-2},{-1,2},{-2,-1}}; */
//栈顶
int top;
HORSE_CHESS_STACK Adr_Stack[MAX_STEPS];
//出栈次数
int out_stack;
值得注意的是，结构体中，x_adr 其实是真实的纵坐标，y_adr 其实是真实的横坐标（大家画个数组表示的棋盘，其实就懂了）。这个首先要明确，不然在后面的定义和赋值等操作时，会有很多不便。
程序各函数
//初始化数据
void init();
//debug 打印栈的情况
void print_stack();
//入栈
void push_stack(int x_real,int y_real);
//出栈
void pop_stack();
//标记位置
void mark_chess(int x,int y);
//打印路径
void print_chess_board();
//打印每一步的位置
int t = 1;
void print_steps();
//马踏棋盘（贪心）算法
void run_horse_tanxin();
主要思想
我们算法最核心的部分，是在下一步到底应该如何选择这件事上，主要的贪心思路就是：
我们先判断下一步都有哪些位置可以走，然后我们再判断其可走位置的再下一步，有几个位置可以走，并统计这几个末端位置的在下一步有几个位置可以走。
也就是 分别计算当前位置下下一步的权，之后我们将下下一步的权都加起来，算成下一步的权，并存储到 next 数组里面。
之后，我们建立 real_next 数组，通过查找遍历，依次将 next 中最小元素的下标赋值给 real_next 数组，这样，我们就得到了一个下一步走的方向顺序的数组 real_next。
这时，我们就可以开始按照 real_next 的顺序来走下一步
以下是核心代码(注释已加)：
//现在位置
x_now = Adr_Stack[top].x_adr;
y_now = Adr_Stack[top].y_adr;
//对方向进行排序
int next[ROW] = {};
for(int i = 0;i < ROW;i++){
//下一步坐标
int x_next = x_now + dir[i][0];
int y_next = y_now + dir[i][1];
if((x_next > 0 && x_next <= COL) && (y_next > 0 && y_next <= ROW) && chess[y_next][x_next] == 0 ){
//对下一步的下一步判断是否可以走
for(int j = 0;j < ROW;j++){
int x_next_next = x_next + dir[j][0];
int y_next_next = y_next + dir[j][1];
//可以走,next 对应下标+1
if((x_next_next > 0 && x_next_next <= COL) && (y_next_next > 0 && y_next_next <= ROW) && chess[y_next_next][x_next_next] == 0){
next[i]++;
}
}
}
}
//依次返回 next 中最小元素的下标，返回后将元素赋值为最大
int real_next[8] = {0};
int k = 0;
int t = ROW + 1;
for(int i = 0;i < ROW;i++){
t = ROW + 1;
for(int j = 0;j < 8;j++){
if(next[j] < t){
real_next[i] = j;
t = next[j];
k = j;
}
}
next[k] = ROW + 1;
}
//走下一步
int dir_now = 0;
for(dir_now = Adr_Stack[top].direction + 1;dir_now < ROW;dir_now++){
int x_real = x_now + dir[real_next[dir_now]][0];
int y_real = y_now + dir[real_next[dir_now]][1];
Adr_Stack[top].direction += 1;
if((x_real <= COL && x_real > 0) && (y_real <= ROW && y_real > 0) && chess[y_real][x_real] == 0){
//入栈
push_stack(x_real,y_real);
//标记棋盘
mark_chess(x_real,y_real);
break;
}
}
流程图
输出分析
下面环境是Linux Ubuntu 18.04
经过一系列实验输入，最终64个位置，无论是从哪个开始，都可以走完全部棋盘，且大部分情况下，没有出栈回溯的情况
以下是一号方向数组在起始位置是（1,1）所得出的答案：
在一号方向数组中，只有在 8,6这个位置，有回溯发生：
我们还应该注意的是，当方向数组的顺序定义得不同时，得到的走的方案也很大可能是不同的
下面，是二号方向数组数组的同样 （1 1）位置所得出的路径
同时我们通过观察其用时发现，贪心的效率十分可观
源码
注释已加
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROW 8
#define COL 8
#define MAX_STEPS ROW*COL
//栈结构体
typedef struct stack{
int x_adr; //纵坐标
int y_adr; //横坐标
int direction; //方向
}HORSE_CHESS_STACK;
//存储路径棋盘
int chess[ROW+1][COL+1];
//下一步方向
//一号
int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1},
{1,-2},{-1,-2},{-1,2},{1,2}};
//二号
/* int dir[8][2] = {{1,2},{-1,-2},{-2,1},{2,1},
{2,-1},{1,-2},{-1,2},{-2,-1}}; */
//栈顶
int top;
HORSE_CHESS_STACK Adr_Stack[MAX_STEPS];
//出栈次数
int out_stack;
//初始化数据
void init(){
int n = MAX_STEPS;
while(n--){
Adr_Stack[n].x_adr = 0;
Adr_Stack[n].y_adr = 0;
Adr_Stack[n].direction = -1;
}
Adr_Stack[0].x_adr = 0;
Adr_Stack[0].y_adr = 0;
Adr_Stack[0].direction = -1;
for(int i = 1;i <= ROW;i++){
for(int j = 1;j <= COL;j++){
chess[ROW][COL] = 0;
}
}
top = -1;
out_stack = 0;
}
//debug 打印栈的情况
void print_stack(){
printf("栈的情况:\n");
for(int i = 0;i < MAX_STEPS;i++){
printf("x:%d y:%d direction = %d\n",Adr_Stack[i].y_adr,Adr_Stack[i].x_adr,Adr_Stack[i].direction);
}
printf("\n\n");
}
//入栈
void push_stack(int x_real,int y_real){
top++;
Adr_Stack[top].x_adr = x_real;
Adr_Stack[top].y_adr = y_real;
Adr_Stack[top].direction = -1; //初始化走的方向
}
//出栈
void pop_stack(){
Adr_Stack[top].x_adr = 0;
Adr_Stack[top].y_adr = 0;
Adr_Stack[top].direction = -1; //初始化走的方向
top--;
}
//标记位置
void mark_chess(int x,int y){
chess[y][x] = top + 1;
}
//打印路径
void print_chess_board(){
printf("\nroute:\n");
for(int i = 1;i <= ROW;i++){
for(int j = 1;j <= ROW;j++){
printf("%4d ",chess[i][j]);
}
printf("\n");
}
printf("\n");
}
//打印每一步的位置
int t = 1;
void print_steps(){
printf("(%d,%d)",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
t++;
if(t == ROW){
printf("\n");
t = 0;
}
}
//马踏棋盘（贪心）算法
void run_horse_tanxin(){
int x_now,y_now;
while(1){
//已经走完全图
if(top >= MAX_STEPS - 1){
//打印棋盘
print_chess_board();
break;
}
//现在位置
x_now = Adr_Stack[top].x_adr;
y_now = Adr_Stack[top].y_adr;
//对方向进行排序
int next[ROW] = {};
for(int i = 0;i < ROW;i++){
//下一步坐标
int x_next = x_now + dir[i][0];
int y_next = y_now + dir[i][1];
if((x_next > 0 && x_next <= COL) && (y_next > 0 && y_next <= ROW) && chess[y_next][x_next] == 0 ){
//对下一步的下一步判断是否可以走
for(int j = 0;j < ROW;j++){
int x_next_next = x_next + dir[j][0];
int y_next_next = y_next + dir[j][1];
//可以走,next 对应下标+1
if((x_next_next > 0 && x_next_next <= COL) && (y_next_next > 0 && y_next_next <= ROW) && chess[y_next_next][x_next_next] == 0){
next[i]++;
}
}
}
}
//依次返回 next 中最小元素的下标，返回后将元素赋值为最大
int real_next[8] = {0};
int k = 0;
int t = ROW + 1;
for(int i = 0;i < ROW;i++){
t = ROW + 1;
for(int j = 0;j < 8;j++){
if(next[j] < t){
real_next[i] = j;
t = next[j];
k = j;
}
}
next[k] = ROW + 1;
}
//走下一步
int dir_now = 0;
for(dir_now = Adr_Stack[top].direction + 1;dir_now < ROW;dir_now++){
int x_real = x_now + dir[real_next[dir_now]][0];
int y_real = y_now + dir[real_next[dir_now]][1];
Adr_Stack[top].direction += 1;
if((x_real <= COL && x_real > 0) && (y_real <= ROW && y_real > 0) && chess[y_real][x_real] == 0){
//入栈
push_stack(x_real,y_real);
//标记棋盘
mark_chess(x_real,y_real);
break;
}
}
//如果下一步走不了，则出栈回溯
if(Adr_Stack[top].direction >= 7){
printf("\n out:(%d,%d) \n",Adr_Stack[top].y_adr,Adr_Stack[top].x_adr);
chess[Adr_Stack[top].y_adr][Adr_Stack[top].x_adr] = 0;
//记录出栈次数
out_stack++;
pop_stack();
}
//打印栈
/* print_stack(); */
//打印走了以后所处位置
print_steps();
}
}
int main(){
int st_x,st_y;
while(1){
printf("Please input: x y :");
scanf("%d %d",&st_x,&st_y);
if(st_x > 0 && st_x <= ROW && st_y > 0 && st_y <= COL){
printf("Get x and y success!\n");
break;
}
printf("Input wrong!please input x y again:");
}
init();
/* print_stack(); */
//获得开始时间
clock_t start = clock();
//将起始位置入栈
push_stack(st_x,st_y);
//标记起始位置
mark_chess(st_x,st_y);
printf("\nroute address:\n");
printf("(%d,%d)",st_x,st_y);
//开始算法
run_horse_tanxin();
//计算结束时间
clock_t finish = clock();
double run_time = (double)(finish - start) / CLOCKS_PER_SEC;
printf("Running time：%f seconds \nOut stack times:%d\n",run_time,out_stack);
}
暴力和简单贪心
总结至此，希望对大家可以有帮助，同时如果大家有兴趣的话，可以看一下朋友的这篇博客，里面讲解了暴力方法和简单贪心。
感谢阅读！