• 国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘的64个方格。
• 将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按照走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，3，…，...
• 自己写的马踏棋盘程序和实验报告，提供给大家参考。
• 完整代码，还有实验报告，这么好， 你绝对需要的
• 使用C语言实现的马踏棋盘，利用的贪心算法，效率大大提升
• 课程实验要求做马踏棋盘的问题，并且我实现了设置阻塞棋子的功能 代码比较简单如下，注释已经写得很多了，基本上每条代码都有解释 #include<stdio.h> #include<stdlib.h> #include<conio.h> #...
 课程实验要求做马踏棋盘的问题，并且我实现了设置阻塞棋子的功能

代码比较简单如下，注释已经写得很多了，基本上每条代码都有解释

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<math.h>
#pragma warning(disable:4996)
#define MAXN 10
#define STALL_PIECE 123
int board[MAXN][MAXN] = { 0 };			//define the board , 0 denotes that hasn't been traveld , 1 denotes the contrary
int moveHorizental[8] = { 2,1,-1,-2,-2,-1,1,2 };//move horizental , as well as Y
int moveVertical[8] = { 1,2,2,1,-1,-2,-2,-1 };//move vertical , as well as X
int stallPieceNumber;					//number of stall piece
bool Check(int x, int y,int N);
/*
check wether the horse is out of extent
x and y is the current position of horse
N is the size of the board
if position(x,y) is walkable,return true , else return false
*/

void HorseTraversal(int thisX, int thisY, int N,int stepNumer);
/*
main function to solve the problem
thisX and thisY is the current position of horse
N is the size of the board
stepNumber is the recursion times and is also the horse's travel number
*/

int main()
{
/*
stall piece test data : board size = 5 , start position = (2,2)
stall piece number = 1 , stall piece position = (0,0)
*/
int horseX, horseY;		//position of the horse
int N;	//size of the board
int stallPieceX, stallPieceY;
printf("Please input the size of the board : ");
scanf("%d", &N);
if (N >= 5 && N <= 10)
{
printf("Please input horse original position : ");
scanf("%d %d", &horseX, &horseY);
//set the original point
board[horseX][horseY] = 1;

//check the input validity
if (horseX < 0 || horseX >= N || horseY < 0 || horseY >= N)
printf("The original position is out of extent !\n");
else {
printf("How many stall pieces do you want to set : ");
scanf("%d", &stallPieceNumber);
if (stallPieceNumber < 0) {
printf("Input error , will excute the default mode ! (No pieces)\n");
stallPieceNumber = 0;
}
else if (stallPieceNumber > 0) {
printf("Please input the pieces's position : ");
for (int i = 0; i < stallPieceNumber; i++) {
scanf("%d %d", &stallPieceX, &stallPieceY);
board[stallPieceX][stallPieceY] = STALL_PIECE;			//initialize the board
}
}
HorseTraversal(horseX, horseY, N, 2);
}
}
else
printf("the size of the board is too small or big!\n");
//if the work is finished
printf("Over!\n");
getch();
return 0;
}
bool Check(int x, int y,int N)
{
if (x < 0 || x >= N || y < 0 || y >= N || board[x][y] != 0 )	//out of extent or the position is already conquered
return false;
return true;
}
bool IsStalled(int currentX,int currentY,int nextX,int nextY)
{
bool flag = false;		//verdict wether the piece stalls the horse , false represents no , true represents yes
//caculate the delt position
int deltX = nextX - currentX;
int deltY = nextY - currentY;
//find the piece which can stall the horse
//pieces[0] represents the piece on current position's top , the rest can be deduced by anology (by clockwise)
bool pieces[4] = { false };
if (board[currentX - 1][currentY] == STALL_PIECE)
pieces[0] = true;
else if (board[currentX][currentY + 1] == STALL_PIECE)
pieces[1] = true;
else if (board[currentX + 1][currentY] == STALL_PIECE)
pieces[2] = true;
else if (board[currentX][currentY - 1] == STALL_PIECE)
pieces[3] = true;
//do discretions
if (pieces[0] && abs(deltY) == 1 && deltX == -2)
flag = true;
if (pieces[1] && abs(deltX) == 1 && deltY == 2)
flag = true;
if (pieces[2] && abs(deltY) == 1 && deltX == 2)
flag = true;
if (pieces[3] && abs(deltX) == 1 && deltY == -2)
flag = true;
return flag;
}
//step number has two functions :
// 1.flag the board			2.record the horse step number
void HorseTraversal(int thisX, int thisY,int N,int stepNumber)
{
int i;
int nextX, nextY;		//next position of the horse
for (i = 0; i < 8; i++)
{
//move to next position
nextX = thisX + moveVertical[i];
nextY = thisY + moveHorizental[i];
//if next step is walkable
if (Check(nextX, nextY, N) && !IsStalled(thisX,thisY,nextX,nextY)) {
board[nextX][nextY] = stepNumber;
if (stepNumber == N * N - stallPieceNumber) {
//print the path
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
if (board[i][j] != STALL_PIECE)
printf("%2d ", board[i][j]);
else
//print stall piece
printf("** ");
printf("\n");
}
printf("\n");
}
else
HorseTraversal(nextX, nextY, N,stepNumber+1);
//flash back
board[nextX][nextY] = 0;
}
}
}


展开全文
• 利用栈实现马踏棋盘 可以实现棋盘遍历并输出棋盘 有方格 算法:深度优先遍历搜索
• 按国际象棋中马的走法,走遍整个M*M的棋盘,并且不重复，用贪心法能迅速找到，并无误的输出。
• 马踏棋盘C语言算法，经过多次测试，代码运行良好。
• 马踏棋盘C语言的完整算法 vs2013下编译运行通过
• 关于马踏棋盘C语言源代码，里面有注释的
• 马踏棋盘C语言贪心算法 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格
• 数据结构课程设计（c语言版）马踏棋盘，教学计划编制问题。给出了源代码和实验报告
• #include #include #define stack_size 100 #define n 8 int a[n][n]; int sort[n][n][8]; int i, j, k,h,l; struct seat { int x, y;//坐标 int direct; }; struct stack { struct seat *top, *base;...struct
#include<stdio.h>
#include<stdlib.h>
#define stack_size 100
#define n 8
int a[n][n];
int sort[n][n][8];
int i, j, k,h,l;

struct seat
{
int x, y;//坐标
int direct;
};

struct stack
{
struct seat *top, *base;
};

struct stack s;

int initstack()
{
s.base=(struct seat*)malloc( stack_size*sizeof(struct seat) );
if( !s.base )
return 0;
s.top=s.base;
return 1;
}

void push(struct seat elem)
{
*s.top++=elem;
}

int pop()
{
if(s.top==s.base)
return 0;

s.top--;
return 1;
}

struct seat gettop()
{
if(s.top==s.base)
exit(0);
return *(s.top-1);
}

int empty()
{
if(s.top==s.base)
return 0;
return 1;
}

int pass(struct seat point)
{

if(point.x<0 || point.x>n-1 || point.y<0 || point.y>n-1)
{
return 0;
}

{
return 0;
}
return  1;
}

struct seat next_point(struct seat point, int direct)
{
switch(direct)
{
case 1:
point.x+=1, point.y-=2;
break;
case 2:
point.x+=2, point.y-=1;
break;
case 3:
point.x+=2,point.y+=1;
break;
case 4:
point.x+=1,point.y+=2;
break;
case 5:
point.x-=1,point.y+=2;
break;
case 6:
point.x-=2,point.y+=1;
break;
case 7:
point.x-=2,point.y-=1;
break;
case 8:
point.x-=1,point.y-=2;
break;
}
return point;
}

void setweight()
{
struct seat point1, point2;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
a[i][j]=0;
point1.x=i;
point1.y=j;
for(k=1; k<=8; k++)
{
point2 = next_point(point1, k);
if(point2.x>=0 && point2.x<=n-1 && point2.y>=0 && point2.y<=n-1)
a[i][j]++;
}
}
}

void next_direct()
{
struct seat point1, point2;
int  count[8], min, r;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
{
point1.x=i;
point1.y=j;
for(k=0; k<8; k++)
{
point2 = next_point(point1, k+1);//现在点的8个方向可走点的：下一个位置
if(point2.x>=0 && point2.x<=n-1 && point2.y>=0 && point2.y<=n-1)
count[k]=a[point2.x][point2.y];
else
count[k]=0;
}

for(h=0; h<8; h++)
{
min=9;
for(l=0; l<8; l++)
{
if(min > count[l])
{
min=count[l];
sort[i][j][h]=l;//可走的方向由小到大
r=l;//标志最小可走的方向
}

}
count[r]=9;//选过的设为比8大的数
}
}
}

int horse_stack(struct seat start)
{
struct seat next_seat;
int next_direct;
int horsestep=0;
start.direct=0;

next_seat=start;
do
{
if( pass(next_seat) )
{
horsestep++;
push(next_seat);
if(horsestep==n*n)
return 0;

next_direct=sort[(s.top-1)->x][(s.top-1)->y][(s.top-1)->direct]+1;

next_seat = next_point( *(s.top-1), next_direct);//贪心策略，试着走下一步，还未入栈
next_seat.direct=0;

}
else
{
while( empty() && (s.top-1)->direct==7)
{
pop();
horsestep--;
}
if( empty() && (s.top-1)->direct<7)
{

next_direct = sort[(s.top-1)->x][(s.top-1)->y][++(s.top-1)->direct]+1;
next_seat = next_point( *(s.top-1), next_direct);
next_seat.direct=0;
}

}
}while( empty() );
return 1;
}
void output()
{
int path[n][n];
struct seat *point=s.base;
for(i=0; point != s.top; i++)
{
path[point->x][point->y]=i+1;
point++;

}

for(i=0; i<n; i++)
{
printf("\n");
for(j=0; j<n; j++)
{
printf("\t%d", path[i][j]);
}
}
printf("\n");
}

void main()
{
struct seat start;
printf("start x(0--7): ");
scanf("%d", &start.x);

printf("\nstart y(0--7): ");
scanf("%d", &start.y);
start.direct=0;

initstack();

setweight();
next_direct();

horse_stack(start);
output();
}

展开全文
• 贪心算法实现在8*8国际棋盘上马儿从任意位置起跳遍历整个棋盘
• 数据结构课程设计，马踏棋盘，C，谁想要的话，赶紧下载啦！！！！哈哈哈哈
• 骑士巡游的C语言算法实现
• title: 基于C语言用递归算法实现马踏棋盘解法的计算 date: 2020-03-17 21:11:41 summary: categories: 编程实例 tags: C语言 img: 基于C语言用递归算法实现马踏棋盘解法的计算 如有不懂欢迎提问 #include<stdio.h...

title: 基于C语言用递归算法实现马踏棋盘解法的计算
date: 2020-03-17 21:11:41
summary:
categories: 编程实例
tags: C语言
img:
基于C语言用递归算法实现马踏棋盘解法的计算
如有不懂欢迎提问
#include<stdio.h>

#define X 7//棋盘x
#define Y 7//棋盘y
#define A 1//起始横坐标
#define B 1//起始纵坐标

void house (int , int);//递归求解，依次传入横纵坐标
void printboard();//打印具体解法
void initialization();//棋盘初始化

int board[X + 4][Y + 4];//其中下标2至X+1或Y+1为棋盘
int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标

int main() {
if (X <= 2 || Y <= 2 || X * Y > 10000) {
//经测试，个人计算机计算10*10已经有些吃力
printf("棋盘不合法!");
return 0;
}
if (A > X || B > Y || A <= 0 || B <= 0) {
printf("初始坐标不合法!");
return 0;
}
printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
initialization();
board[A + 1][B + 1] = ++step;
house(A, B);
printf("\n\n计算完毕!\n");
printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
printf("共找到%d组解\n",sum);
return 0;
}

void initialization() {
int i, j;
//给棋盘赋值0，周围赋值-1即不可走
for (i = 0; i <= X + 3; i++) {
for (j = 0; j <= Y + 3; j++) {
if (i == 0 || i == 1 || i == X + 3 || i == X + 2 || j == 0 || j == 1 || j == Y + 3 || j == Y + 2)
board[i][j] = -1;
else
board[i][j] = 0;
}
}
return;
}

void house(int a , int b) {
if (step == X*Y) {
sum++;
printboard();
return;
}
for (int i = 0; i <= 7; i++) {
if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
step++;
board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
house(a+move[i][0], b+move[i][1]);
board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
step--;
}
}
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard() {
int i, j, k;
printf("\n第%d种解法：\n",sum);
printf("┌───");
for (i = 1; i <= Y- 1; i++)
printf("┬───");
printf("┐\n");
for ( i = 2; i <= X + 1; i++) {
for ( j = 2; j <= Y + 1; j++)
printf("│%3.2d", board[i][j]);
printf("│\n");
if (i <= X) {
printf("├───");
for(k=1;k<=Y-1;k++)
printf("┼───");
printf("┤\n");
}
}
printf("└───");
for (i = 1; i <= Y - 1; i++)
printf("┴───");
printf("┘\n");
return;
}

上文为了方便使用define来确定棋盘尺寸X、Y。如果想用scanf来确定，需要用到动态数组，并且需要向函数传递地址
#include<stdio.h>
#include<stdlib.h>//包含malloc

void house(int, int, int**);//递归求解，依次传入横纵坐标ab，二维数组指针
void printboard(int**);//传入二维数组指针，打印具体解法
void initialization(int**);//棋盘初始化，依次传入二维数组指针

int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标
int x, y;//定义全局变量

int main() {
printf("马踏棋盘v2.0\n");
printf("请输入棋盘大小x*y：\n");
printf("x=");
scanf("%d", &x);
printf("y=");
scanf("%d", &y);
int a, b;//无需全局变量
printf("请输入起始位置(a, b)，其中最小为(1, 1)：\n");
printf("a=");
scanf("%d", &a);
printf("b=");
scanf("%d", &b);
int **board;
board = (int**)malloc(sizeof(int *) * (x + 4));
for (int i = 0; i < x + 4; i++) {
board[i] = (int*)malloc(sizeof(int *) * (y + 4));
}
//相当于声明了动态数组board[x + 4][y + 4];其中下标2至X+1或Y+1为棋盘
if (x <= 2 || x <= 2 || x * y > 10000) {
//经测试，由于递归算法，计算10*10已经极为吃力
printf("棋盘不合法!");
return 0;
}
if (a > x || a > y || a <= 0 || a <= 0) {
printf("初始坐标不合法!");
return 0;
}
printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
initialization(board);
board[a + 1][a + 1] = ++step;
house(a, b, board);
printf("\n\n计算完毕!\n");
printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
printf("共找到%d组解\n", sum);
return 0;
}

void initialization(int** board) {
int i, j;
//给棋盘赋值0，周围赋值-1即不可走
for (i = 0; i <= x + 3; i++) {
for (j = 0; j <= y + 3; j++) {
if (i == 0 || i == 1 || i == x + 3 || i == x + 2 || j == 0 || j == 1 || j == y + 3 || j == y + 2)
board[i][j] = -1;
else
board[i][j] = 0;
}
}
return;
}

void house(int a, int b, int** board) {
if (step == x*y) {
sum++;
printboard(board);
return;
}
for (int i = 0; i <= 7; i++) {
if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
step++;
board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
house(a + move[i][0], b + move[i][1], board);
board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
step--;
}
}
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard(int **board) {
int i, j, k;
printf("\n第%d种解法：\n", sum);
printf("┌───");
for (i = 1; i <= y - 1; i++)
printf("┬───");
printf("┐\n");
for (i = 2; i <= x + 1; i++) {
for (j = 2; j <= y + 1; j++)
printf("│%3.2d", board[i][j]);
printf("│\n");
if (i <= x) {
printf("├───");
for (k = 1; k <= y - 1; k++)
printf("┼───");
printf("┤\n");
}
}
printf("└───");
for (i = 1; i <= y - 1; i++)
printf("┴───");
printf("┘\n");
return;
}


交流讨论等具体内容请访问我的博客
原文地址：https://boyinthesun.cn/post/c-house/


展开全文
• 马踏棋盘算法 马踏棋盘 数据结构课程设计 马踏棋盘课程设计 C语言编写
• 程序演示图 源程序 #include #include #define ROW 100 #define COL 100 int ...贪心算法求解马踏棋盘问题效率极高，up主亲测90行90列的棋盘也是秒解。（贪心算法对于本问题成立的理论可以参考度娘，这里不再赘述）
程序演示图

源程序
#include<stdio.h>
#include<stdlib.h>
#define ROW 100
#define COL 100

int chess[ROW][COL]={0};
int row;
int col;
int x,y;
int min;
int turn[][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int max;
int result;

typedef struct direct	//方向
{
int count;			//可能
int index;			//下标
}Direct;

//确定地图
void input()
{
printf("行:");
scanf("%d",&row);
printf("列:");
scanf("%d",&col);
printf("起始坐标(x,y):");
scanf("%d %d",&x,&y);
x+=2;
y+=2;
}

//初始化
void init()
{
int i,j;
for(i=0;i<row+4;i++)
{
for(j=0;j<col+4;j++)
{
if(i<2||i>=row+2||j<2||j>=col+2)
{
chess[i][j]=-1;
}
else
{
chess[i][j]=0;
}
}
}
min=1;
max=row*col;
result=0;
}

//结果
void print()
{
int i,j;
for(i=2;i<row+2;i++)
{
for(j=2;j<col+2;j++)
{
printf("%3d ",chess[i][j]);
}
printf("\n");
}
}

//获取一个位置的可走数量
int getNext(int m,int n)
{
if(chess[m][n]!=0)
{
return 10;
}
int count=0;
int i;
int p,q;
for(i=0;i<8;i++)
{
p=m+turn[i][0];
q=n+turn[i][1];
if(chess[p][q]==0)
{
count++;
}
}
return count;
}

//深度搜索答案
void dfs(int m,int n,int num)
{
if(num>=max)
{
print();
result++;
exit(0);
//		return;
}
chess[m][n]=num;

Direct direct[8];
int i,j;
int p,q;
for(i=0;i<8;i++)
{
p=m+turn[i][0];
q=n+turn[i][1];
direct[i].index=i;
direct[i].count=getNext(p,q);
}
//将可走数量较少的排在前面
for(i=0;i<7;i++)
{
for(j=i+1;j<8;j++)
{
if(direct[i].count>direct[j].count)
{
Direct t=direct[i];
direct[i]=direct[j];
direct[j]=t;
}
}
}

//继续深度搜索
for(i=0;i<8;i++)
{
p=turn[direct[i].index][0]+m;
q=turn[direct[i].index][1]+n;
if(chess[p][q]==0)
{
dfs(p,q,num+1);
chess[p][q]=0;
}
}
}

int main()
{
input();
init();
dfs(x,y,min);
printf("解的个数:%d\n",result);
return 0;
}

设计思路
1.按人的搜索答案思想，馬每次到达一个位置后依次像八个方向的可走位置试探，直到踏满棋盘。
2.馬每次到达一个位置时，先计算下一个位置的八个方向中的可走位置个数，分别存入8个数组中，然后我们将该数组排好序。接着按照出路少到多的方向依次试探（贪心算法思想）。
3.贪心算法求解马踏棋盘问题效率极高，up主亲测90行90列的棋盘也是秒解。（贪心算法对于本问题成立的理论可以参考度娘，这里不再赘述）


展开全文
• 编写一个c程序，实现马踏棋盘操作，要求1～64这64个数字标注马移动的路径，也就是按照求出的行走路线，将数字1，2，3，......，64依次填入棋盘的方格中，并输出。 问题分析： 国际象棋中，“马”的移动...
• 马踏棋盘问题是旅行商问题（TSP）或哈密顿回路问题（HCP）的一个特例。在 8×8（在本例中采用5*5） 的象棋棋盘上，用一个马按照马步跳遍整个棋盘，要求每个格子都只跳到一次，最后回到出发点。这是一个 NP问题，通常...
• ## 马踏棋盘C语言实现

千次阅读 2015-08-17 18:01:38
该代码为未优化算法实现，8*8棋盘，挑选效率高的起始点(2,0),以及效率高的走法 每一次走法的尝试都是回溯法，一条路走到黑，直到行不通，再重新开始 ////////////////回溯法+递归//////////////图的深度优先遍历//...
• 马踏棋盘问题（骑士巡游问题）的基于贪心算法优化深度搜索可视化实现 用c语言实现的，在命令台中会动态的显示棋盘上棋子路径
• 有趣的数据结构算法18——马踏棋盘问题（骑士周游问题）的C语言实现（回溯法）及其解析问题复述题目分析利用c语言实现马踏棋盘问题GITHUB下载连接 马踏棋盘问题就是要求使用国际象棋的棋子马
• 使用贪心算法，每次选择最少度数的点作为下一个位置的选择。
• 马踏棋盘算法: 图的深度遍历算法 DFS应用 国际象棋棋盘8*8方格棋盘,现将马放在任意指定的方格中, 要求每个方格只能进入一次,最终使得马,走遍棋盘64个格子 实现马踏棋盘的操作,要求用1-64来标注马移动的路径 ...
• 数据结构——马踏棋盘题解（贪心算法） 使用循环建立棋盘与权值棋盘 将当前步数写入棋盘数组中 开始探测下一步该走的位置， 分别测试八个方向 对可走位置进行查询权值，将权值最少的作为下一步的位置（每次都...

c语言 订阅