Question

程序设计，马踏棋盘，求指教

求这个程序的TryPath函数思想，算法，以及为什么这么做
程序在一楼

Answer 1

#include<stdio.h>
#define MAXSIZE 100
#define N 8
int board[8][8]; //定义棋盘
int Htry1[8]={1,-1,-2,2,2,1,-1,-2};
/*存储马各个出口位置相对当前位置行下标的增量数组*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1};
/*存储马各个出口位置相对当前位置列下标的增量数组*/
struct Stack{ //定义栈类型
int i; //行坐标
int j; //列坐标

}stack[MAXSIZE]; //定义一个栈数组
int top=0; //栈指针

void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标
int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘
void Display(); //输出马儿行走的路径

void InitLocation(int xi,int yi)
{
int x,y; //定义棋盘的横纵坐标变量
stack[top].i=xi; //将起始位置的横坐标进栈
stack[top].j=yi; //将起始位置的纵坐标进栈

board[xi][yi]=top+1; //标记棋盘
x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标
y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标
if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0
Display(); //输出马儿的行走路径

}

int TryPath(int i,int j)
{
int find,number,min; //定义几个临时变量
int i1,j1,h,k,s; //定义几个临时变量
int a[8],b1[8],b2[8],d[8]; //定义几个临时数组
while(top>-1) //栈不空时循环
{
for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
for(k=0;k<8;k++)
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)
//如果找到下一位置
number++; //记录条数
}
a[h]=number; //将条数存入数组a[8]中
}
}
for(h=0;h<8;h++) //根据可行路径条数小到大按下表排序放入数组d[8]中
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
d[h]=k; //将下表存入数组d[8]中
s=k;
}
a[s]=9;
}

if(top>=63) //如果走完整个棋盘返回1
return (1);
find=0; //表示没有找到下一个位置
for(h=0;h<8;h++) //向八个方向进行探寻
{
i=stack[top].i+Htry1[d[h]];
j=stack[top].j+Htry2[d[h]];
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
find=1; //表示找到下一个位置
break;
}
}
if(find==1) //如果找到下一个位置进栈
{

top++; //栈指针前移进栈
stack[top].i=i;
stack[top].j=j;

board[i][j]=top+1; //标记棋盘
}
else //否则退栈
{
board[stack[top].i][stack[top].j]=0; //清除棋盘的标记
top--; //栈指针前移退栈
}
}
return (0);
}

void Display()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("\t%d ",board[i][j]); //输出马儿在棋盘上走过的路径
printf("\n\n");
}
printf("\n");
}

void main()
{
int i,j;
int x,y;
for(i=0;i<N;i++) //初始化棋盘
for(j=0;j<N;j++)
board[i][j]=0;
for(;;)
{
printf("Please input importpoint(1<=x<=8 and 1<=y<=8)\n");
printf("Input x = ");
scanf("%d",&x); //输入起始位置的横坐标
printf("Input y = ");
scanf("%d",&y); //输入起始位置的纵坐标
if(x>=1&&x<=8&&y>=1&&y<=8)break;
printf("Your input is worng!!!\n");
}
printf("begin with %d board:\n\n", 8*(x-1)+y);
InitLocation(x-1,y-1); //调用起始坐标函数
}

Answer 2

马踏棋盘的贪心算法
【问题描述】 　　马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。 　　【初步设计】 　　首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下： 　　1、 输入初始位置坐标x,y； 　　2、 步骤 c: 　　如果c> 64输出一个解，返回上一步骤c-- 　　(x,y) ← c 　　计算(x,y)的八个方位的子结点，选出那此可行的子结点 　　循环遍历所有可行子结点，步骤c++重复2 　　显然（2）是一个递归调用的过程，大致如下： 　　#define N 8 　　…… 　　…… 　　void dfs(int x,int y,int count) 　　{ 　　int i,tx,ty; 　　if(count> N*N) 　　{ 　　output_solution();//输出一个解 　　return; 　　} 　　for(I=0;i <8;++i) 　　{ 　　tx=hn[i].x;//hn[]保存八个方位子结点 　　ty=hn[i].y; 　　s[tx][ty]=count; 　　dfs(tx,ty,count+1);//递归调用 　　s[tx][ty]=0; 　　} 　　}