需求
将马随机放在国际象棋的Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。
分析
最基本的应该是深度优先搜索，但是对于一个8×8的棋盘，如果采取暴力搜索，将会耗费很长时间而得不到一个结果，如果采用贪心算法，对路径有目的地筛选，尽量选择出口少的路先走，也就是对当前点的下一个落脚点（可能是8个）进行排序，优先走可走的路最少的那个点，使得走法较好。通俗来讲，就是先预判下一个可能落脚点的出口数，出口数最少的先走掉。
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 ——百度百科
代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Row 8
#define Col 8
#define maxStep 64
typedef struct {
int abscissa; //横坐标
int ordinate; //纵坐标
int direction; //方向
}SqStack;
int ChessBoard[Row+1][Col+1]={}; //储存路径的棋盘
//分别有（1 ~ 8）个方向
int HTry1[8]={1, -1, -2, 2, 2, 1, -1, -2};
int HTry2[8]={2, -2, 1, 1, -1, -2, 2, -1};
SqStack PointStack[maxStep];
int top = -1; //栈顶
int flagOperate = 0; //操作标记
int num = 0; //记录结果数
void printChessBoard() {
printf("棋盘路径是:\n");
for(int i = 1;i <= Row;i++) {
for(int j = 1;j <= Col;j++) {
printf("%5d ", ChessBoard[i][j]);
}
printf("\n");
}
printf("\n\n");
}
//入栈
void push(int abscissa, int ordinate) {
++top;
PointStack[top].abscissa = abscissa;
PointStack[top].ordinate = ordinate;
PointStack[top].direction = -1; //初始化方向
}
//出栈
void pop() {
PointStack[top].abscissa = 0;
PointStack[top].ordinate = 0;
PointStack[top].direction = -1; //初始化方向
--top;
}
//打印栈
void printStack() {
printf("目前栈的情况:\n");
for(int i = 0;i < maxStep;i++) {
printf("x:%d , y:%d, d:%d\n", PointStack[i].abscissa, PointStack[i].ordinate, PointStack[i].direction);
}
printf("\n\n");
}
//标记棋盘
void markChessBoard(int abscissa, int ordinate) {
ChessBoard[ordinate][abscissa] = top+1;
}
void runChessBoard() {
int xNow, yNow; //当前马所在的坐标
while(1) {
if(flagOperate == 1) {
if(top == maxStep - 1) {
printChessBoard();
break;
}
}else if(flagOperate == 2 ) {
if(top == maxStep - 1){
printChessBoard();
num++;
printf("%d \n\n", num);
}
}
xNow = PointStack[top].abscissa;
yNow = PointStack[top].ordinate;
//对下面八个方向重新排序，出口最少的优先
int count[8]={};
for(int i = 0;i < 8;i++) {
int xNext = xNow, yNext = yNow;
xNext += HTry1[i];
yNext += HTry2[i];
if(xNext > 0 && xNext <= Col && yNext > 0 && yNext <= Row && ChessBoard[yNext][xNext] == 0) {
for(int j = 0;j < 8;j++) {
int xNextNext = xNext, yNextNext = yNext;
xNextNext += HTry1[j];
yNextNext += HTry2[j];
if(xNextNext > 0 && xNextNext <= Col && yNextNext > 0 && yNextNext <= Row && ChessBoard[yNextNext][xNextNext] == 0) {
count[i]++;
}
}
}
}
//对方向进行排序，实际要走的方向记录在directionNext中
int directionNext[8] = {};
int temp = 9;
int k = 0;
for(int i = 0;i < 8;i++) {
temp = 9;
for(int j = 0;j < 8;j++) {
if(count[j]<temp){
directionNext[i] = j;
temp = count[j];
k = j;
}
}
count[k] = 9;
}
//走下一步
int direnow = 0;
for(direnow = PointStack[top].direction + 1 ; direnow < 8 ; direnow++) {
int xRealNext = xNow, yRealNext = yNow;
xRealNext += HTry1[directionNext[direnow]];
yRealNext += HTry2[directionNext[direnow]];
PointStack[top].direction += 1;
if(xRealNext <= Col && xRealNext > 0 && yRealNext <= Row && yRealNext > 0 &&ChessBoard[yRealNext][xRealNext] == 0) {
push(xRealNext, yRealNext);
markChessBoard(xRealNext, yRealNext);
break;
}
}
//判断无路可走出栈
if(PointStack[top].direction >= 7) {
int x, y;
x = PointStack[top].abscissa;
y = PointStack[top].ordinate;
ChessBoard[y][x] = 0; //棋盘标记取消
pop();
}
}
}
void InitStartPoint() {
int x, y;
//输入起始坐标点
printf("请输入起始点（x，y）:");
scanf("%d %d", &x, &y);
printf("请输入需要运算的方式：\n 1.找出一个结果\n 2.找出所有结果(几乎不可能)\n输入:");
scanf("%d", &flagOperate);
while(((x > Col||x <= 0)&&(y > Row||y <= 0))||(flagOperate <= 0 && flagOperate >= 3)) {
if((x > Col||x <= 0)&&(y > Row||y <= 0)) {
printf("输入的坐标超出范围，请重新输入（0~8）：");
scanf("%d %d", &x, &y);
}else if(flagOperate <= 0 && flagOperate >= 3) {
printf("输入错误，请重新输入：\n");
printf("请输入需要运算的方式：\n 1.找出一个结果\n 2.找出所有结果(几乎不可能)\n输入:");
scanf("%d", &flagOperate);
}
}
//入首栈
push(x, y);
markChessBoard(x, y);
}
int main() {
InitStartPoint();
clock_t start,finish; //开始结束时间
double duration; //运行用时
start = clock();
runChessBoard();
finish = clock();
duration = (double) (finish - start) / CLOCKS_PER_SEC;
printf("运行用时: %f second\n", duration);
}
