对八皇后问题的拓展探究
探究 拓展 皇后 问题
2023-09-11 14:20:13 时间
对八皇后问题的拓展探究
至繁归于至简,这次自己仍然用尽可能易理解和阅读的解决方式。
1、问题说明:
西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八个皇后如何相安无事的放置在棋盘上,1970年与1971年, E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。
2、解法:
关于棋盘的问题,都可以用递回求解,然而如何减少递回的次数?在八个皇后的问题中,不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用再检查了,这个方法称为分支修剪。下面自己写的的具体代码,以棋盘上的八皇后为例,修改下面的N = 8,即可从八皇后问题拓展至此类所有的棋盘问题。
3、具体代码:
/** * @Title 对八皇后问题的拓展探究 * @Author 孙琨 * @Date 2013-11-18 * @At XUST * @All Copyright by 孙琨 * */ #include <iostream> using namespace std; #define N 8 int column[N + 1]; // 同栏是否有皇后,1表示有 int rup[2 * N + 1]; // 右上至左下是否有皇后 int lup[2 * N + 1]; // 左上至右下是否有皇后 int queen[N + 1] = {0}; int num; // 解答编号 void backtrack(int); // 递归求解 int main(void) { int i; num = 0; for(i=1; i<=N; i++) column[i] = 1; for(i=1; i<=2*N; i++) rup[i] = lup[i] = 1; backtrack(1); cout <<endl << N << "个皇后在棋盘上总共有" << num << "种排法" << endl; return 0; } void showAnswer() { int x,y; cout << endl << "解答 " << ++num << endl; for(y=1; y<=N; y++) { for(x=1; x<=N; x++) { if(queen[y] == x) // 放置皇后 cout << "●"; else cout << "○"; } cout << endl; } } void backtrack(int i) { int j; if(i > N) { showAnswer(); } else { for(j=1; j<=N; j++) { if(column[j]==1 && rup[i+j]==1 && lup[i-j+N]==1) { queen[i] = j; // 设定为占用 column[j] = rup[i+j] = lup[i-j+N] = 0; backtrack(i+1); column[j] = rup[i+j] = lup[i-j+N] = 1; } } } }
4、结果部分截图:
相关文章
- 分布式异步队列RabbitMQ 探究
- 【深入了解cocos2d-x 3.x】定时器(scheduler)的使用和原理探究(2)
- Java之戳中痛点 - (3)三目运算符的两个操作数类型尽量一致 Java之戳中痛点 - (4)i++ 和 ++i 探究原理 Java之戳中痛点 - (1)易变业务使用脚本语言编写 Java之戳中痛点 - (2)取余用偶判断,不要用奇判断 (5)switch语句break不能忘以及default不同位置的用法 Java之戳中痛点 - (7)善用Java整型缓存池
- 探究活动Activity(2)界面跳转及生命周期
- 探究活动Activity
- zookeeper使用和原理探究(一)
- android vector pathData探究,几分钟绘制自己的vectordrawable
- Android UI测量、布局、绘制过程探究
- 【无标题】谈谈对音视频开发的探究
- iOS H5 容器的一些探究(一):UIWebView 和 WKWebView 的比较和选择
- 【SystemVerilog基础】关于随机化约束solve...before的深入探究
- 【SystemVerilog基础】合并数组与非合并数组深入探究
- 【SystemVerilog基础】关联数组的一点探究
- 探究“补阶乘大法的本质“——糖水不等式
- iOS中block实现的探究
- 探究机器码,深入研究C语言程序的机制