汉扬编程 C语言入门 媳妇多就用分支修剪,解决婆娘纷争,C语言经典算法之八皇后问题

媳妇多就用分支修剪,解决婆娘纷争,C语言经典算法之八皇后问题

八皇后问题行文不易,新手上路,多多关注,这真的对我很重要,私信更有惊喜

媳妇多就用分支修剪,解决婆娘纷争,C语言经典算法之八皇后问题

西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无事的放置在棋盘上,1970年与1971年, E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。

媳妇多就用分支修剪,解决婆娘纷争,C语言经典算法之八皇后问题

分支修剪解法关于棋盘的问题,都可以用递回求解,然而如何减少递回的次数?在八个皇后的问题中,不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用再检查了,这个方法称为分支修剪。

相关源码行文不易,新手上路,多多关注,这真的对我很重要,私信更有惊喜

运行结果部分实例No 1

Q . . . . . . .

. . . . Q . . .

. . . . . . . Q

. . . . . Q . .

. . Q . . . . .

. . . . . . Q .

. Q . . . . . .

. . . Q . . . .

数据结构之8 皇后问题回溯算法的C语言实现

上篇文章,为大家分享了约瑟夫环C语言实现,这里为大家分享8皇后问题的C语言完整实现,大家有条件的话,可以在电脑上调试运行,加深对算法的理解和掌握。

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。

因为最近在学习算法,所以今天在这里对回溯法中的八皇后问题,进行一下归纳和总结。

一、基本定义

回溯法(back track method)是在包含问题的所有可能解的解空间树中,从根结点出发,按照深度优先的策略进行搜索,对于解空间树的某个结点,若满足约束条件,则进入该子树继续搜索,否则将以该结点为根结点的子树进行剪枝。

二、适用范围

可避免搜索所有的可能解,适用于求解组合数较大的问题。

三、八皇后问题

问题:在8 x 8的棋盘上摆放8个皇后,而且八个皇后中的任意两个是不能处于同一行、同一列、或同一斜线上。

/*

* File: queen.c

* Description: 求 8 皇后问题回溯算法

* Created: 2001/11/12

* Author: Justin Hou [mailto:justin_hou@hotmail.com]

*/

#include <stdio.h>

#define DelayTime 20000 /* 显示棋局时间 */

#define TopX 10 /* 棋盘左上角 x 坐标 */

#define TopY 5 /* 棋盘左上角 y 坐标 */

int N = 8; /* 皇后数量 */

int a[8], b[15], c[15];

/*

* a[col-1] 记录第 col 列有无皇后, 1 表示有。

* b[row+col-2] 记录从左上数第 row+col-1 条斜率为 1 的线上有无皇后。

* c[row-col+7] 记录从右上数第 row-col+8 条斜率为 -1 的线上有无皇后。

*/

int Num = 0;

int row;

void BackTrack (int row)

{

int col; /* 局部变量 */

for (col=1; col<=N; col++)

{

if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0)

{

a[col-1] = 1; /* 更改数据 */

b[row+col-2] = 1;

c[row-col+N-1] = 1;

gotoxy(col*2 + TopX, row + TopY); /* 画皇后 */

putch(\’Q\’);

if (row < N)

{

BackTrack (row + 1);

}

else

{

Num++; /* 递归终点 */

gotoxy(40, 9);

printf(\”Num: %d \”, Num);

delay(DelayTime);

}

a[col-1] = 0; /* 清空数据 */

b[row+col-2] = 0;

c[row-col+N-1] = 0;

gotoxy(col*2 + TopX, row + TopY); /* 清除图象 */

putch(\’.\’);

}/* end if */

}/* end for */

}/* end function BackTrack */

void main()

{

int i, j;

clrscr();

gotoxy(1, 10); /* 要求用户输入皇后数量 */

printf(\”Input the number of queen: \”);

while(N <= 0 || N > 14)

{

scanf(\”%d\”, &N);

if(N > 14) printf(\”Two huge number, input again:\”);

if(N <= 0) printf(\”Can\’s smaller than 1, again:\”);

}

clrscr();

for(i=1; i<=N; i++) /* 画棋盘(Chessboard) */

{

for(j=1; j<=N; j++)

{

gotoxy(i*2 + TopX, j + TopY);

putch(\’.\’);

}

}

BackTrack(1); /* 开始回溯算法 */

gotoxy(12, 17); /* 显示最后结果 */

printf (\”There are %d kinds of solution.\\n\”, Num);

getch();

}

想了解最新考研资讯和院校指导,点击上方头像关注我,或给我发私信,也可关注上方图片右下角的账号,为你提供最新考研干货。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/5916.html

再过4年C语言就50岁了,这么老的编程语言怎么还没有过时?

零基础学习c语言四 | 基本数据类型

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部