精华内容
下载资源
问答
  • 八皇后问题C语言解法(递归、回溯)
    2020-06-11 16:48:09

    本算法是经过学习B站UP主讲解后,整理出来的代码,编译无误,可生成92种方式。 

    #include "stdafx.h"
    #include"stdlib.h"
    
    int place[8] = {0};//用来记录当前行的皇后在第几列
    bool flag[8] = {1,1,1,1,1,1,1,1};//那一列有皇后占领
    bool d1[15] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};//上对角线是否占领
    bool d2[15] = { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 };//下对角线是否占领
    int number = 0;//技术总共有多少解法
    
    void print(int n)
    {
    	int i,j;
    	int table[8][8]={0};
    	for(i=0;i<8;i++)
    	table[i][place[i]]=1;
    	printf_s("\n第 %d 种\n",n);
    	for(i=0;i<8;i++)
    	for(j=0;j<8;j++)
    	{
    		printf_s("%d ",table[i][j]);
    		if(j==7)printf_s("\n");
    	}
    }
    
    void generate(int n)
    {
    	int col;//当前列
    	for(col=0;col<8;col++)//八列都需要判断完
    	{
    		if(flag[col]==1 && d1[n-col+7] == 1 && d2[n+col] == 1)//查看占领状态
    		{
    			//符合条件即占领
    			place[n]=col;
    			flag[col] = 0;
    			d1[n - col + 7] = 0;
    			d2[n + col] = 0;
    			if(n<7)//八个皇后全部放置完毕判断
    				generate(n+1);
    			else
    			{
    				++number;
    				print(number);
    			}
    			//所有的检查完,再继续回溯,确保得出所有解
    			flag[col] = 1;
    			d1[n - col + 7] = 1;
    			d2[n + col] = 1;
    		}
    	}
    }
    
    
    
    int main()
    {  
    	printf_s("八皇后放法:\n");
    	generate(0);
    	printf_s("总共有 %d 种八皇后放法\n", number);
    	system("pause");
    	return 0;
    }

     

    更多相关内容
  • 八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出:在一个8*8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后之间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列...
  • C语言求解出八皇后所有解,稍作修改可以推至n皇后问题
  • 主要介绍了C语言八皇后问题解决方法,简单描述了八皇后问题并结合实例形式分析了C语言基于暴力法与回溯法解决八皇后的具体操作技巧,需要的朋友可以参考下
  • 八皇后问题 C语言

    2018-07-12 23:14:31
    八皇后问题C语言版本,无注释但是代码简洁清楚,变量名皆可望文生义。
  • 八皇后问题 C语言实现

    千次阅读 2020-11-17 21:56:53
    在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 思路: 对于计算机问题的求解,我们完全可以模仿人类的解题思路,并将其抽象化,...

     问题:

    在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

     思路:

    对于计算机问题的求解,我们完全可以模仿人类的解题思路,并将其抽象化,形成可供计算机执行的代码。

    首先,我们考虑使用枚举的方式,但应保证枚举不重复。故我们将八个棋子分别编号,并让编号小的棋子永远在编号大的棋子前,从左到右,从上到下,从编号小的棋子依次排列到编号大的棋子。

    按照这个思路,我们可以定义一个8*8的二维数组,二维数组的值代表这个棋子的编号。我们先将第一个棋子放置于0*0的位置,然后距离最近可能的第二个棋子的位置,即1*3,依次类推。这种方法很像一个循环,不过普通的循环显然无法实现这个方案。因此我们参考递归的实现思路,定义一个函数,用来处理这个问题。

    当按照这个思路做完,我们会发现没有一个结果符合我们的要求。因此我们回去寻找问题。很容易发现,第七个棋子并不一定放在离第六个棋子最近可能的地方,同理,第二个棋子也不一定放在离第一个棋子最近可能的地方(即位置1*3)。因此,我们要重新对上一个棋子定义位置,直到第一个棋子到达最后的位置,我们才做完了所有可能。

    对问题进一步抽象,我们假设对第n个棋子进行操作,在定下第n个棋子的一个位置后再定第n+1个棋子,同时我们还应重新定第n个棋子的位置。至此,我们就能解决这个问题。

    代码:

    #include<stdio.h>
    int find(int m, int n, int count);
    int fight(int m, int n);
    void show();
    int queen[8][8] = { 0 };   //数字下标为棋盘位置,数值为第几个棋子,0代表无棋子
    int methods = 0;     //统计总共有多少种情况
    
    int main() {
    	find(0, 0, 1);
    	printf("总共有:%d", methods);
    	return 0;
    }
    
    //从m行 n列寻找   第count个  
    int find(int m, int n,int count) {
    	if (n == 8) {
    		m++;
    		n = 0;
    	}
    	int q;                   //q为当前列
    	for (q = n; q < 8; q++) {
    		if (fight(m, q) == 0) {
    			queen[m][q] = count;
    			goto NEXT;         //计算下一个棋子
    		}
    	}
    	for (m++; m < 8; m++) {
    		for (q = 0; q < 8; q++) {
    			if (fight(m, q) == 0) {
    				queen[m][q] = count;
    				goto NEXT;
    			}
    		}
    	} 
    		return 0;     //查找到最后一个都没找到,则停止查找
    	NEXT:
    	if (count == 8) {
    		show();
    		methods++; 
    	}
    	if (count < 8) {
    		
    		find(m, q+1, count+1);   //向后查找
    		
    	}
    	queen[m][q] = 0;      //重新查找当前棋子
    	find(m, q+1, count);   
    }
    
    //判断是否会相互攻击   攻击返回1 不会攻击返回0
    int fight(int m, int n) {
    	for (int q = 0; q < 8; q++) {
    		if (queen[m][q] > 0)
    			return 1;
    	}
    	for (int q = 0; q < 8; q++) {
    		if (queen[q][n] > 0)
    			return 1;
    	}
    	for (int a = m, b = n; a<=7&&a>=0&&b<=7&&b>=0; a++, b++) {
    		if (queen[a][b] > 0)
    			return 1;
    	}
    	for (int a = m, b = n; a <= 7 && a >= 0 && b <= 7 && b >= 0; a++, b--) {
    		if (queen[a][b] > 0)
    			return 1;
    	}
    	for (int a = m, b = n; a <= 7 && a >= 0 && b <= 7 && b >= 0; a--, b++) {
    		if (queen[a][b] > 0)
    			return 1;
    	}
    	for (int a = m, b = n; a <= 7 && a >= 0 && b <= 7 && b >= 0; a--, b--) {
    		if (queen[a][b] > 0)
    			return 1;
    	}
    	return 0;
    }
    
    //将当前棋盘展示
    void show() {
    	for (int m = 0; m < 8; m++) {
    		for (int n = 0; n < 8; n++) {
    			printf("%d ", queen[m][n]);
    		}
    		printf("\n");
    	}
    	printf("\n");
    }

    总结(回溯算法):

    本问题的解题思路使用的是典型的回溯算法。我们可以将该算法思路类比为走迷宫。我们可以先在所有岔路口上左转,一直走到路的尽头。若此方法无法走到终点,我们回到上一个选择点,选择一条不同的路,依此类推。这种方法可以在不出现重复的情况下走完所有的路,并在计算机中可以很好的通过函数嵌套的方式( 子问题与原始问题为同样的事)实现。

    拓展:

    数独问题

    展开全文
  • 用回溯法解决八皇后问题C语言实现

    热门讨论 2011-02-22 18:26:23
    有多种方法解决八皇后问题,在这里我用的是回溯法解决八皇后问题。大家一起来学习呀!!
  • 八皇后问题C语言程序设计终稿.pdf
  • 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
  • 八皇后问题C语言解法

    2021-05-20 05:00:41
    偶遇八皇后问题,随即自己写了一个仅供参考#include#include#define SIZE 8void Circumsribe(int(*checkerboard)[SIZE], int x, int y, int flag);int EightQueen(int(*checkerboard)[SIZE], int num, int begin_x, ...

    偶遇八皇后问题,随即自己写了一个仅供参考

    #include

    #include

    #define SIZE 8

    void Circumsribe(int(*checkerboard)[SIZE], int x, int y, int flag);

    int EightQueen(int(*checkerboard)[SIZE], int num, int begin_x, int begin_y);

    void main()

    {

    int checkerboard[SIZE][SIZE] = {}, result;

    result = EightQueen(checkerboard, , , );

    printf_s("%d\n", result);

    }

    //划定或解除皇后攻击范围

    void Circumsribe(int(*checkerboard)[SIZE], int x, int y, int flag)

    {

    int i, j;

    for (i = ; i < SIZE; i++)

    {

    for (j = ; j < SIZE; j++)

    {

    if (flag == )

    {

    //flag为1表示放置皇后,划定攻击范围

    checkerboard[i][j] = (i == x || j == y || abs(j - y) == abs(i - x)) ? checkerboard[i][j] + : checkerboard[i][j];

    }

    else

    {

    //flag为0表示移走皇后,解除攻击范围

    checkerboard[i][j] = (i == x || j == y || abs(j - y) == abs(i - x)) ? checkerboard[i][j] - : checkerboard[i][j];

    }

    }

    }

    }

    //num表示放置皇后的序号,begin_x与begin_y表示此序号皇后放置的坐标

    //返回值表示余下num个皇后有多少种允许的摆法

    int EightQueen(int(*checkerboard)[SIZE], int num, int begin_x, int begin_y)

    {

    int x, y, sum = ; //sum理解为皇后在不同位置上允许的摆法总和

    if (num <= || num > SIZE || begin_x < || begin_y < || begin_x > SIZE || begin_y > SIZE)

    {

    //数据非法则返回0

    return ;

    }

    else if (num == )

    {

    //若只有1个皇后,则从指定的(begin_x,begin_y)开始,往后统计摆法

    for (x = begin_x; x < SIZE; x++)

    {

    for (y = (x == begin_x ? begin_y : ); y < SIZE; y++)

    {

    sum = checkerboard[x][y] == ? sum + : sum;

    }

    }

    return sum;

    }

    else

    {

    //若多于1个皇后,则先将多余的皇后从指定的(begin_x,begin_y)开始摆好,在此基础上,统计最后1个皇后的摆法

    //引入(begin_x,begin_y)是为了避免重复放置,每个皇后的位置都应该从上个皇后的位置处开始,否则有重复

    for (x = begin_x; x < SIZE; x++)

    {

    for (y = (x == begin_x ? begin_y : ); y < SIZE; y++)

    {

    if (checkerboard[x][y] == )

    {

    Circumsribe(checkerboard, x, y, ); //若此(x,y)处可放置皇后,则划定这个皇后的攻击范围

    sum = sum + EightQueen(checkerboard, num - , x, y); //在此基础上确定余下皇后的摆法

    Circumsribe(checkerboard, x, y, ); //将此皇后移到下个位置前需要先解除其攻击范围

    }

    }

    }

    return sum;

    }

    }

    C&num;中八皇后问题的递归解法——N皇后

    百度测试部2015年10月份的面试题之——八皇后. 八皇后问题的介绍在此.以下是用递归思想实现八皇后-N皇后. 代码如下: using System;using System.Collections. ...

    八皇后问题 -- python面向对象解法

    # [8*8棋盘八皇后问题] class Queen: def __init__(self, row, col): self.row = row self.col = col self.pos = ( ...

    比赛组队问题 --- 递归解法 --- java代码 --- 八皇后问题

    两队比赛,甲队为A.B.C3人,乙队为X.Y.Z3人.已知A不和X比,C不和X.Z比,请编程序找出3队赛手名单 采用了与八皇后问题相似的解法,代码如下: 如有疑问请链接八皇后问题的解法:http:// ...

    回溯算法-C&num;语言解决八皇后问题的写法与优化

    结合问题说方案,首先先说问题: 八皇后问题:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 嗯,这个问题已经被使用各种语言解 ...

    java递归求八皇后问题解法

    八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处 ...

    使用java语言实现八皇后问题

    八皇后问题,在一个8X8的棋盘中,放置八个棋子,每个棋子的上下左右,左上左下,右上右下方向上不得有其他棋子.正确答案为92中,接下来用java语言实现. 解: package eightQuen; / ...

    R语言-八皇后问题

    老师给我出了个暑期作业:用R语言解决八皇后问题. 八皇后问题:国际象棋棋盘(8×8)上放8个“后”,使8个“后”之间互相不能被进攻.(即:每个“后”所在行.列.两条斜线都没有其它子) 查看网上,大多用 ...

    C语言解决八皇后问题

    #include #include /* this code is used to cope with the problem of ...

    八皇后问题 --- 递归解法 --- java代码

    八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后 ...

    随机推荐

    OSI模型

    1.物理层 •设备间接收或发送比特流 •说明电压.线速和线缆等 例子: EIA/TIA-232 V.35 2. 数据链路层 •将比特组合成字节进而组合成帧 •用MAC地址访问介质 •错误发现但不能纠正 ...

    NET中MSMQ的使用----附例子

    目录 一:MSMQ的一些理论上的知识 二:队列类型(Queue Type) 三:安装消息队列 四:在C#中Messagequeue class 五:MSMQ-发送消息到远程专用队列 六:例子   一. ...

    二、Hadoop学习笔记————架构学习

    1.成百上千台服务器组成集群,需要时刻检测服务器是否故障 2.用流读取数据更加高效快速 3.存储节点具有运算功能,省略了服务器之间来回传数据的网络带宽限制 4.一次写入,多次访问,不修改数据 5.多平 ...

    微信小程序中的组件使用2

    需求    上面两个页面是同一个小程序的不同页面,两个页面中都是用到了label,有相似的地方,但是也有不同之处,这个时候,如果我们想要将这些label做出组件,然后复用,有该怎么做呢? 基础组件 首 ...

    自己开发能在asp&period;net项目正常使用的定时器WebTimer,让定时器听话起来

    简述: iis是一个很不错的服务器,有很多很好用的特性来支持网站运行,但有时候这些特性却会影响到我们开发者的一些操作.比如我们需要定时运行做一些操作,但由于iis的利用应用程序池来管理这种方式会让网站 ...

    机器学习评价方法 - Recall &amp&semi; Precision

    刚开始看这方面论文的时候对于各种评价方法特别困惑,还总是记混,不完全统计下,备忘. 关于召回率和精确率,假设二分类问题,正样本为x,负样本为o: 准确率存在的问题是当正负样本数量不均衡的时候: 精心设 ...

    response&period;encodeURL的用法

    Java Servlet API 中引用 Session 机制来追踪客户的状态.Servlet API 中定义了 javax.servlet.http.HttpSession 接口,Servlet 容 ...

    js实现放大镜的效果

    leetcode&lowbar;11&period; Container With Most Water

    leetcode_11. Container With Most Water 一,问题: Given n non-negative integers a1, a2, ..., an, where ea ...

    linux 下的mysql 连接报错

    报错: Fri Jul 28 16:28:52 CST 2017 WARN: Establishing SSL connection without server’s identity verific ...

    展开全文
  • 八皇后问题 C语言

    2011-09-08 13:36:13
    八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...
  • 递归解决八皇后问题 使用的是VS2010(编译通过) 代码有注释说明
  • 八皇后问题的源代码,自己用C语言编写的源代码,绝对可以运行。
  • C语言实现N皇后问题非递归求解 ---- Word版本。
  • n皇后问题c语言编程

    2013-04-19 19:29:14
    完整的n皇后问题C语言源码,可正常运行,采用文件输入输出,部分代码为: #include"stdio.h" #include"stdlib.h" #define MAX 100 int x[MAX]; int Place(int k)//规范函数 { int i; for(i=1;i;i++) { if((x[i...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 八皇后问题4种c语言算法

    千次阅读 2021-04-26 10:58:49
    八皇后问题 1.递归回溯法 B站懒猫老师讲的(我在这里学的) 八皇后问题的递归回溯算法思路:从第一行开始当某一行皇后位置不与前面所有皇后位置冲突那么记录该行皇后位置并调用递归函数进入下一行,摆放下一个皇后,...

    八皇后问题

    1.递归回溯法

    B站懒猫老师讲的(我在这里学的)
    八皇后问题的递归回溯算法思路:从第一行开始当某一行皇后位置不与前面所有皇后位置冲突那么记录该行皇后位置并调用递归函数进入下一行,摆放下一个皇后,逐个位置摆放,若该行所有位置都被其他皇后占领,那么就回溯到上一行重新摆放上一行皇后直至所有皇后都不冲突那么记录一次方法然后回溯寻找其他摆放方法。

    冲突算法思路:一个8*8的棋盘每一个位置若用其行号加上其列号我们可以得到下图,由图可知在同一条上对角线的数值都相同,因此我们可以利用该规律设计判断上对角线是否冲突的函数,类似的,下对角线则是由列号减去行号可得在同一条下对角线的数值相等。为了方便后面的程序中我把下对角线的数值都加7为正数(实际效果不变)
    行号+列号
    行号-列号

    #include<stdio.h>
    int place[8]={0};//皇后位置
    bool flag[8]={1,1,1,1,1,1,1,1};//定义列
    bool d1[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};/*定义上对角线(共有15个对角线,
    因此定义一个长度为15的bool型数组,初值为1代表该对角线没有被皇后占领,
    若被皇后占领则赋值为0*/
    bool d2[15]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} ;//定义下对角线
    int number=0;//记录输出次数
    void print()//定义输出函数
    {
    	int col,i,j;
    number++;//每调用一次输出函数number自加一次,记录摆放方法个数
    	printf("No.%2d\n",number);
    	int table[8][8]={0};//设置一个8*8的棋盘
    	for (i=0;i<8;i++)
    	{
    		table[i][place[i]]=1;//将每一行皇后所在位置赋值为1
    	}
    	for (i=0;i<8;i++)
    	{
    		for (j=0;j<8;j++)
    		{
    	printf("%d|",table[i][j]);
    		}printf("\n");
    	}
    }
    int queen(int n )//定义递归回溯函数
    {
    	int col;
    	for (col=0;col<8;col++)
    	{
    		if (flag[col]&&d1[n-col+7]&&d2[n+col])//判断皇后是否冲突
    		{
    			place[n]=col;//放置皇后
    			flag[col]=false;
    			d1[n-col+7]=false;
    	
    	d2[n+col]=false;//将该皇后所在的行、列、对角线设置为被占领
    			if(n<7)	{queen(n+1);}//当行数小于7时;递归调用下一行
    		else{print();}//调用输出函数
    			flag[col]=true;//回溯
    			d1[n-col+7]=true;
    			d2[n+col]=true;
    		}
    	}
    	return number;
    }
    int main()
    {
    number=queen(0);//从第0行开始执行
    printf("共有%d种摆放方法",number);//输出方法的个数
    	return 0;}
    

    利用递归回溯的方法来解决八皇后问题的程序步骤较少且可读性强,代码量少,不用尝试所有错误的摆放方法,遇到错误就回溯,效率较高。但递归算法占用空间更大,且每调用一次函数都要在内存栈中分配一定的空间,而栈的空间是有限的,若递归调用的层次太多就容易造成栈的溢出。

    2 回溯法(非递归)

    位置冲突算法:建立一个一维数组a[9](a[0]不用),a[1]~a[9]八个数分别代表棋盘的一行,其中的数值代表该行皇后所在的列数,若任意两个数的数值相等则表明在同一列(冲突),若任意两个数所在的行数差值的绝对值等于列数的差值的绝对值(在同一对角线上冲突)

    #include <stdio.h>
    #include <math.h>
    
    bool Chongtu( int a[], int n) {
    	int i = 0 , j = 0 ;
    	for (i = 2 ; i <= n; ++i)          
    for (j = 1 ; j <= i- 1 ; ++j)              
    if ((a[i] == a[j]) || (abs(a[i]-a[j]) ==abs(i-j)))//1:在一列;2:在对角线上。每一行都要与前面所有行进行判断是否冲突
    		return false ;   //冲突
    	return true ;} //不冲突
    //八皇后问题:迭代法(回溯)
    void Queens8(){
    	int n = 8 ;        //8个皇后
    	int count = 0 ;//记录当前第几情况
    	int a[ 9 ] = { 0 };   //存放皇后位置,(第0行0列不用,便于直观看出皇后位置)
    	int i = 0 ,k = 1 ;  //初始化k为第一行
    	a[ 1 ] = 0 ;     //初始化a[1] = 0
    	while (k > 0 )    
    	{
    		a[k] += 1 ;    //a[k]位置,摆放一个皇后
    		while ((a[k] <= n) && (!Chongtu(a,k))) //如果a[k](即皇后摆放位置)没有到k行最后,且摆放冲突。
    	  a[k] += 1 ; //将皇后向后移一位直至不冲突或a[k]>n超出范围则结束循环
    		if (a[k] <= n) //皇后摆放位置没有到达该行最后一个位置
    		{
    	if (k == n) //8行皇后全部摆放完毕
    {
    printf( "第%d种情况:\n" ,++count);
    	for (i = 1 ; i <= n; ++i) //打印该种摆放方法情况
    	{
    	for (int j=1;j<=8;j++)		
    {    	
    if (j!=a[i])		
    {   
    printf("0|");
    		   }
    	else{printf("1|");}
    			}
    printf("\n");
    		}
    printf("\n");
    	}
    	else      //皇后还未摆放完毕
    	{
    		k += 1 ;    //继续摆放下一行
    				a[k] = 0 ;  //此行初始化a[k] = 0;表示第k行,从第一行开始摆放皇后
    			}
    		}
    		else  //回溯:当a[k]>8进入else,表示在第k列中没有找到合适的摆放位置
    			k -= 1 ; //回溯到k-1步:k表示第几个皇后,a[k]表示第k个皇后摆放的位置
    	}
    	return ;
    }
    //主函数
    int main()
    {
    	Queens8();
    	return 0 ;
    }
    

    回溯法实质上是利用迭代实现递归回溯的方法,该方法运行效率高,但是代码量更大也更加复杂。

    3 枚举法(1)

    枚举法即列举出所有摆放方法(无论是否冲突),当八个皇后摆放完毕后再判断该方法是否合理。
    冲突算法与回溯(非递归)法相同

    #include <stdio.h>
    #include <math.h>
    
    bool Chongtu( int a[], int n) //判断皇后是否冲突的函数
    {
    	int i = 0 , j = 0 ;
    	for (i = 2 ; i <= n; i++) //i:皇后的位置
    		for (j = 1 ; j <= i- 1; j++) //j:皇后的位置
    			if ((a[i]== a[j]) || (abs(a[i]-a[j]) ==abs(i-j))) //1:在一列;2:在对角线上。每一行都要与前面所有行进行判断是否冲突
    			{return false ;} //冲突
    			return true ;}//不冲突
    void Queens8()//枚举
    {
    	int a[ 9 ] = { 0 }; //用于记录皇后位置:(第0行0列不用,便于直观看出皇后位置)。
    	int i = 0 ,count = 0 ;  
    //枚举出八个皇后摆放位置的所有情况
    //利用八重循环列举出所有方法并逐一验证
    	for (a[ 1 ] = 1 ; a[ 1 ] <= 8 ; ++a[ 1 ])
    	for (a[ 2 ] = 1 ; a[ 2 ] <= 8 ; ++a[ 2 ])
    	for (a[ 3 ] = 1 ; a[ 3 ] <= 8 ; ++a[ 3 ])
    	for (a[ 4 ] = 1 ; a[ 4 ] <= 8 ; ++a[ 4 ])
    	for (a[ 5 ] = 1 ; a[ 5 ] <= 8 ; ++a[ 5 ])
    	for (a[ 6 ] = 1 ; a[ 6 ] <= 8 ; ++a[ 6 ])
    	for (a[ 7 ] = 1 ; a[ 7 ] <= 8 ; ++a[ 7 ])
    	for (a[ 8 ] = 1 ; a[ 8 ] <= 8 ; ++a[ 8 ])
    {	
    if (!Chongtu(a, 8 )) /*调用判断该种摆放方法是否冲突的函数,
    若冲突则枚举下一种方法,若不冲突则记录此种摆放方式	*/
    	{continue ;}
    	else {							
    printf( "第%d情况:\n" ,++count);
     
    	for (i = 1;i<= 8 ;i++)
    	{
    		for (int j=1;j<=8;j++)
    		{
    			if (j!=a[i])
    			{
    				printf("0|");
    			}else{printf("1|");}
    	}printf("\n");
    	}
     //打印该种摆放方法
    printf( "\n" );
    		}
    	}
    }
    int main()//主函数
    {
         Queens8();
         return 0 ;
    }
    

    枚举法思路和代码都简单易懂,但程序的计算量大,方法较基础。

    4 枚举法(2)

    枚举法(2)的冲突算法及思路与枚举法(1)类似,该方法虽然简化了部分代码,但是时间复杂度更大。(大家可以对照着枚举法1理解我就没加注释了)。

    #include <stdio.h>
    #include <math.h>
    int count = 0;//记录方法次数
     
    //输出函数
    void showAnswer(int *queen){
    	int i,j;
    count++;
    printf("第%d种解法:\n",count);
    for(i = 0; i < 8; ++i)
    {
    	for(j = 0; j < 8; ++j)
    	{
    		if(queen[i] == j)
    			printf("1|");
    		else
    			printf("0|");
    	}
    	printf("\n");
    }
    		printf("\n");}
    //判断是否皇后位置是否冲突算法
    void chongtu(int *queen){
    	int i,j,flag=1;
    	for(i = 0; i < 8; ++i)
    	{
    		for(j = 0; j < 8; ++j)
    		{
    			if(i != j)
    			{
    		if(queen[i] == queen[j])
    					{flag = 0;}
    	else if(abs(queen[i] - queen[j]) == abs(i-j))
    			flag = 0;
    			}
    		}
    	}
    	if(flag == 1)
    	{
    showAnswer(queen);//若该方法可行则调用输出函数
    }
     }
    //枚举出所有摆放方法(相较于枚举法(1)简化了八重循环)
    void set_queen(int *queen)
    {
        int i,flag;
        while(queen[8] != 1)
        {
            ++queen[0];
            for(i = 0;i<8; ++i)
            {
                if(queen[i]==8)            
                {   
     queen[i]=0;
                   { ++queen[i+1];}
                }
            }
            flag =1;
    		chongtu(queen);//摆放后调用位置冲突算法
        }
    }
    int main()
    {
        int queen[9] = {0};
        set_queen(queen);
        return 0;
    }
    

    目前我只学了这四种方法(在原作者方法上进行了部分更改也增加了一下注释和个人的理解),这四种方法比较好理解,希望能帮助到大家。
    ps:我还用java写了这几种方法(基本上差不多),如果大家有需要可以联系我。

    展开全文
  • 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是19世纪著名的数学家高斯于1850年提出的:在8*8格的国际象棋棋盘上,安放八个皇后,要求没有一个皇后能够“吃掉”任何其他一个皇后,即任意两个...
  • 八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出:在一个8*8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后之间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列...
  • 解决八皇后问题 #include #include int c = 0; //外部变量C记录合法布局的个数 void Going(int queens[],int i); void Print(int queens[]); int Check(int queens[],int i); void main() { int queens[8] = {0}; ...
  • 八皇后问题算法(C语言实现)

    万次阅读 多人点赞 2018-05-15 18:52:01
    1. 八皇后的由来和问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都...
  • 最适合C语言初学者的八皇后问题问题的最优解
  • 什么是八皇后问题八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能...
  • 八皇后问题的实现(C语言)》由会员分享,可在线阅读,更多相关《八皇后问题的实现(C语言)(3页珍藏版)》请在人人文库网上搜索。1、八皇后问题的实现(C语言)#include #define N 8 / 定义棋盘的格数, 通过改变,也可以...
  • linux c语言实现八皇后问题。希望对你的学习

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,366
精华内容 946
关键字:

八皇后问题c语言