算法学习笔记之三:八皇后问题(递归、回溯)

news/2024/11/29 12:54:49/

(一)题记

从去年下半年开始找工作,大大小小也被“鄙”试、“面”试了n多回了。说实话只怪自己并未对常见的笔试题、面试题进行准备,导致败下阵来。一门学问要想学透学精是需要时间的,慢慢来吧……

第一次听到“八皇后”问题是在参加百度计算机视觉算法工程师面试时听中科院来面试的一个博士说的,当时隐约记得他是搞机器学习、模式识别的,所以自己以为这是很难的一个问题,回来简单想了一下也就没有细究。到后来去本行业初创公司“春雨”面试的时候,面试官让当场码代码解决这个问题,由于之前有印象,就定式思维地一直以为很难,所以从开始内心有些许的恐惧,最后在面试官的提示下写了个大概,最终结果不是很令人满意。

废话不多说了,一句话“不要被思维定式所困扰“,其实很简单的一个问题。

下面直奔主题:

(二)问题

http://zh.wikipedia.org/wiki/八皇后问题

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n当且仅当 n = 1 或 n ≥ 4 时问题有解。

(三)思路分析

其实该问题并不难,利用递归方法很容易解决。没放置一个皇后,就将其能够攻击的区域进行标记,然后放置下一个皇后,一次类推……;此外,如果有解最终肯定是每一行有且只有一位皇后,所以放置的时候按照逐行放置的顺序进行。此问题难点在于如何把控递归函数的返回条件,一种条件是8个皇后放置完成后,返回成功,一种条件是该行中已经没有可以放置的位置,此时返回失败,需要重新放置。此时要额外注意,所谓的“重新放置”指的并不是将所有皇后清除重新来过,而是只返回上一层,将上一个导致本次放置失败的皇后进行清除,然后重新更新其位置,通过逐级放置、或逐级回溯可以达到遍历所有情况找到所有解(下文中给出的自己的代码的计算结果不是独立解的个数,而是所有可行解的情况)

(四)自己码代码

//--------------------------------------
//利用函数递归,解决八皇后问题
//
//	zssure	2014-03-12
//--------------------------------------#include <stdio.h>
#include <cmath>int count=0;//全局计数变量/*--------------------四个皇后----------------------*/
//#define QUEEN_NUM 4
//int label[QUEEN_NUM][QUEEN_NUM]={	0,0,0,0,	
//									0,0,0,0,
//									0,0,0,0,
//									0,0,0,0	};/*--------------------五个皇后----------------------*/
//#define QUEEN_NUM 5
//int label[QUEEN_NUM][QUEEN_NUM]={	0,0,0,0,0,
//									0,0,0,0,0,
//									0,0,0,0,0,
//									0,0,0,0,0,
//									0,0,0,0,0		};/*--------------------六个皇后----------------------*/
//#define QUEEN_NUM 6
//int label[QUEEN_NUM][QUEEN_NUM]={	0,0,0,0,0,0,
//									0,0,0,0,0,0,
//									0,0,0,0,0,0,
//									0,0,0,0,0,0,
//									0,0,0,0,0,0,
//									0,0,0,0,0,0
//													};/*--------------------七个皇后----------------------*/
//#define QUEEN_NUM 7
//int label[QUEEN_NUM][QUEEN_NUM]={	0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0,
//									0,0,0,0,0,0,0
//													};/*--------------------八个皇后----------------------*/
#define QUEEN_NUM 8
int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};void FillChessbox(int m,int n,int num)
{for(int i=0;i<QUEEN_NUM;++i)for(int j=0;j<QUEEN_NUM;++j)if(abs(i-m)==abs(j-n))//对角区域填充{if(label[i][j]==0)label[i][j]=num;}int i=0,j=0;while(i<QUEEN_NUM)//行填充{if(label[i][n]==0)label[i][n]=num;++i;}while(j<QUEEN_NUM)//列填充{if(label[m][j]==0)	label[m][j]=num;++j;}}
void ClearChessBox(int m,int n,int num)
{for(int i=0;i<QUEEN_NUM;++i)for(int j=0;j<QUEEN_NUM;++j)if(abs(i-m)==abs(j-n) && label[i][j]==num)label[i][j]=0;int i=0,j=0;while(i<QUEEN_NUM){if(label[i][n]==num)label[i][n]=0;++i;}while(j<QUEEN_NUM){if(label[m][j]==num)label[m][j]=0;++j;}
}
void AllClear()
{for(int i=0;i<QUEEN_NUM;++i)for(int j=0;j<QUEEN_NUM;++j)label[i][j]=0;}
void PrintResult()
{for(int i=0;i<QUEEN_NUM;++i){for(int j=0;j<QUEEN_NUM;++j)printf("%d ",label[i][j]);printf("\n");}
}
bool EightQueen(int n/*皇后个数*/,int c/*已经放置的皇后个数*/)
{//static int count=0;//小于3x3的棋盘是无解的if(n<4)return false;for(int i=0;i<n;++i){if(label[c-1][i]==0)//存在可以放置第c个皇后的位置{label[c-1][i]=c+1;if(c==n)/*已经放置完毕所有的皇后*/{++count;PrintResult();printf("**************************\n");ClearChessBox(c-1,i,c+1);//AllClear();return true;}FillChessbox(c-1,i,c+1);EightQueen(n,c+1);ClearChessBox(c-1,i,c+1);/*-------------------------------------------------------------------------------------------------------------------------//	现场恢复,无论下一个皇后是否顺利放置,都应该恢复现场。原因是////	如果下一个皇后放置失败,那么自然应该将本次放置的皇后去除,重新放置,所以需要进行现场恢复(即回溯);//	如果下一个皇后放置成功,意味着本次放置已经满足条件,是一个解,此时需要恢复现场,进行下一次的重新放置,寻找下一个解。////------------------------------------------------------------------------------------------------------------------------*///if(!EightQueen(n,c+1))//	ClearChessBox(c-1,i,c+1);}}return false;
}int main()
{EightQueen(QUEEN_NUM,1);printf("%d\n",count);return 0;
}
【注】:本次的代码使用了二维数组来标记皇后的位置,且最后输出结果中皇后位置并未准确显示,还有待改进。
参考博文:

http://blog.csdn.net/feixiaoxing/article/details/6877965

http://blog.csdn.net/sandyzhs/article/details/4250563


Author:zssure

E-mail:zssure@163.com

Date:2014-03-12


http://www.ppmy.cn/news/721854.html

相关文章

动态规划学习总结

本文结合 代码随想录 leetcode官方解答&#xff0c;做了学习和总结&#xff0c;仅个人记录学习。 代码随想录网址代码随想录 动态规划大致分为以下几个问题&#xff1a; 1.基础动态规划 2.背包问题 3.打家劫舍 4.股票问题 5.子序列问题 1.基础动态规划 基础使用场景&am…

高等数学-微积分

高数微积分 宋浩 奇函数和偶函数&#xff1a; 判断奇函数和偶函数两点 1、x的定义域关于原点对称&#xff0c;是奇函数。关于y轴对称是偶函数。 2、通过这个规则判断。单调增和减函数&#xff1a; 函数有界 上届和下界&#xff1a; 反函数: 图像&#xff1a;反函数和原函数关…

4.Julia数组、向量化和广播

数组的基本概念和用法不在这里多说了。对于科学计算&#xff0c;数组是不可或缺的。我们先写一个函数&#xff1a; function f(x,y)return x*yend 再调用这个函数&#xff1a; print(f(3,5)) 运行这个函数得&#xff1a; 15 现在我们有A,B两数组&#xff0c;元素一样多。我们…

【考研数学】数一-数学概念anki卡片合集-547张-23000字-22电子科大考研上岸整理

样本空间的定义 定义&#xff1a;一切基本事件的集合 样本空间的表示方法 记做Ω 事件的表示方式 表示方式&#xff1a;字母A,B,C… 随机事件与样本空间的关系 随机事件可视为样本空间的子集 事件A发生的含义 事件A发生 事件A所包含的某一基本事件出现 不可能事件的表示 ∅…

算法笔记(二)暴力递归回溯搜索

文章目录 前缀树贪心算法有限时间完成最多次的会议最省钱的切割金条方法赚钱最多的项目安排方案 字典序比较方法一个数据流中随时可以取得中位数N皇后问题位运算优化的N皇后问题 汉诺塔问题打印一个字符的全部子序列获得字符串的全排列两聪明人玩牌不借助额外数据结构逆序一个栈…

高数第一章思维导图(目前待录取,原件在评论区分享)

高数 第一章 数列 函数 连续 函数 如果对于每个数x属于D&#xff0c;变量x按照一定的法则总有一个确定的y和它对应&#xff0c;则称x是y的函数。 记为yf(x)。常称x为自变量&#xff0c;y为因变量&#xff0c;D为定义域 极限 极限类别 数列极限 设为数列{an}&#xf…

转贴:定式中的“纳什均衡”与“有限理性”

关于围棋的定式&#xff0c;棋界有不同解说&#xff0c;但也有一些基本共识&#xff0c;如定式之“定”只有相对含义&#xff0c;定式经历历史沿革&#xff0c;可见其非自然法则&#xff0c;乃人之发明&#xff0c;而且行棋中出“变着”也为常见。甚至有求道者如小林光一痛思“…

【微积分】数形结合

数学分析 笛卡尔坐标系是由实数集组成的。 Y集合包含值域&#xff0c;但不等于值域 逆映射 看起来和 反函数 的写法一样 复合映射&#xff0c;看起来像复合函数&#xff0c;成立的条件要求中间集合满足定义域 Rg表示g映射的值域&#xff0c;Df 表示f映射的定义域 隐函数 开…