首页 > 递归/回溯：八皇后问题N-Queens

递归/回溯：八皇后问题N-Queens

N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年，由国 际西洋棋棋手马克斯·贝瑟尔于提出了8皇后问题。

将N个皇后放摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆 放方式具体是怎样的?

8皇后即 8*8的棋盘中，将8个皇后放置在棋盘上，且皇后之间无法俩俩攻击到对方。

关于国际象棋中皇后的实力：国际象棋棋局中实力最强的一种棋子，也是最容易被吃掉的棋子。后可横直斜走，且格数不限

类似4*4的棋盘上，有如下两种皇后的放置方法:

.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

分析：

N*N的棋盘放置N个皇后，即至少每一行需要一个皇后；

  1. 将一个皇后放置到棋盘上之后，棋盘如何演变（一个皇后放到棋盘，她的影响区域为上，下，左，右，左上，左下，右上，右下）
  2. 针对每一个皇后，如何能够确认下一个皇后，以及下下一个皇后。。。直到能够放置N个皇后的棋盘分布？

针对问题一，我们可以实现如下算法：

针对棋盘打标:

void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) { /*维护两个方向数组可以取到皇后的八个方向即可这里定义了const型是为了节省内存，即整个进程代码运行期间，此时的const两个数组是存放在常量内存区，且定义为了static，则整个代码仅仅会有一份拷贝*/static const int dx[] = { 0,0,-1,1,-1,1,-1,1}; static const int dy[] = { -1,1,0,0,-1,-1,1,1}; if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) { return ;}mark[x][y] = 1;for (int i = 0;i < mark.size(); ++i) { for (int j = 0;j < 8; ++j) { int new_x = x + i * dx[j];int new_y = y + i * dy[j];if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) { mark[new_x][new_y] = 1;}}}
}

回到问题2上，我们想要获取棋盘上能够放置皇后的方法的个数以及具体的放置位置；

可以先尝试一个一个放，当然这放置可以按照行放，也可以按照列放（八皇后问题最终的表现形式就是每行只能有一个，每一列只能有一个）。

我们这里的放置皇后的方式都按照行放，第一行第一个：

Q111
1100
1010
1001

接下来皇后的放置的规则肯定就是在不能被第一个Q影响的情况下放置了，我们这里仍然按照行进行放置，放第二个,如下红色1则为重新放置后打入的标记

Q111
11Q1
1111
1011

再次进行放置，发现第三行已经没有位置可以放了，此时可以定论，最开始的第一次放置位置不合理，需要进行回溯，回溯到第一次放置Q之前棋盘的位置，即

0000
0000
0000
0000

综上过程我们可以知道我们算法实现有以下几个点

  1. 按行（或者列）进行棋盘遍历，每一次放置一个皇后，并对皇后区域进行打标
  2. 以上过程需要递归完成，递归过程中发现无法达到N*N放置N个皇后时即终止递归，并回滚棋盘状态为第一次放置皇后之前的棋盘状态。

实现算法如下(文末有完整测试代码):

/*标记棋盘放置皇后的数组*/
void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) { static const int dx[] = { 0,0,-1,1,-1,1,-1,1};static const int dy[] = { -1,1,0,0,-1,-1,1,1};if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) { return ;}mark[x][y] = 1;for (int i = 0;i < mark.size(); ++i) { for (int j = 0;j < 8; ++j) { int new_x = x + i * dx[j];int new_y = y + i * dy[j];if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) { mark[new_x][new_y] = 1;}}}
}/*递归+回溯棋盘状态*/
void generate(int k, int n, std::vector<string> &location, //用字符表示放置策略std::vector<std::vector<string>> &result, //最终的放置策略的汇总std::vector<std::vector<int> > &mark) {  //保存每一次放置皇后的棋盘状态if (k == n) {  //结束条件就是发现当前放置策略支持N个皇后result.push_back(location);return;}/*按行遍历*/for (int i = 0;i < n; ++i) { /*备份初始棋盘状态*/std::vector<std::vector<int>> tmp_mark = mark;/*放置位置就是没有被打标的位置，即不会被其他皇后影响的位置*/if (mark[k][i] == 0) { /*放置一个皇后，针对其进行打标*/mark_queen(k, i, mark);location[k][i] = 'Q';generate(k+1, n, location, result, mark);/*递归之后回滚到最初备份的状态*/mark = tmp_mark;location[k][i] = '.';}}
}
/*初始化棋盘*/
std::vector<std::vector<string> > solve_N_queen(int n) { std::vector<std::vector<int> > mark;std::vector<std::vector<string> > result;std::vector<string> location;for (int i = 0;i < n; ++i) { mark.push_back(std::vector<int> ());for (int j = 0;j < n; ++j) { mark[i].push_back(0);}location.push_back("");location[i].append(n,'.');}generate(0,n,location,result,mark);return result;
}

测试代码如下:

#include 
#include 
#include 
#include /*
N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年
由国际西洋棋棋手马克斯·贝瑟尔于提出了8皇后问题。 将N个皇后放摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆 放方式具体是怎样的?类似 N = 4
那么如下输出
solution1:
.Q..
...Q
Q...
..Q.solution2:
..Q.
Q...
...Q
.Q..
*/using namespace std;/*标记棋盘放置皇后的数组*/
void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) { static const int dx[] = { 0,0,-1,1,-1,1,-1,1};static const int dy[] = { -1,1,0,0,-1,-1,1,1};if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) { return ;}mark[x][y] = 1;for (int i = 0;i < mark.size(); ++i) { for (int j = 0;j < 8; ++j) { int new_x = x + i * dx[j];int new_y = y + i * dy[j];if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) { mark[new_x][new_y] = 1;}}}
}void generate(int k, int n, std::vector<string> &location, std::vector<std::vector<string>> &result, std::vector<std::vector<int> > &mark) { if (k == n) { result.push_back(location);return;}for (int i = 0;i < n; ++i) { std::vector<std::vector<int>> tmp_mark = mark;if (mark[k][i] == 0) { mark_queen(k, i, mark);location[k][i] = 'Q';generate(k+1, n, location, result, mark);mark = tmp_mark;location[k][i] = '.';}}
}std::vector<std::vector<string> > solve_N_queen(int n) { std::vector<std::vector<int> > mark;std::vector<std::vector<string> > result;std::vector<string> location;for (int i = 0;i < n; ++i) { mark.push_back(std::vector<int> ());for (int j = 0;j < n; ++j) { mark[i].push_back(0);}location.push_back("");location[i].append(n,'.');}generate(0,n,location,result,mark);return result;
}int main(int argc, char const *argv[])
{ int n;cin >> n;std::vector<std::vector<string>> result; result = solve_N_queen(n);cout << "num of method is " << result.size() << endl;cout << "method is " << endl;for (int i = 0; i < result.size(); ++i) { for (int j = 0;j < result[i].size(); ++j) { cout << result[i][j];cout << endl;}cout << endl;}return 0;
}

编译:g++ -std=c++11 test.c -o test

输出如下:

#输入
8
#输出
num of method is 92
method is 
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....
#以下输出较多，可自行编译查看
...#输入
4
#输出
num of method is 2
method is 
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 基于C++实现线程池加速

    经过长期探索，发现一个不需要手动设置线程休眠时间(e.g. std::this_thread::sleep_for(std::chrono::microseconds(1)))的代码: Github: https://github.com/log4cplus/ThreadPool #ifndef THREAD_POOL_H_7e...

  • STL nth_element

    nth_element(first,nth,last) first，last 第一个和最后一个迭代器，也可以直接用数组的位置。  nth，要定位的第nn 个元素，能对它进行随机访问. 将第n_thn_th 元素放到它该放的位置上，左边元素都小于它，右边元素都大于它. 测试代码: http://www.cplusplus.com...

  • c++11随机数产生器default_random_engine

    c/c++老版本的rand（）存在一定的问题，在转换rand随机数的范围，类型或者分布时，常常会引入非随机性。 定义在 中的随机数库通过一组协作类来解决这类问题：随机数引擎 和 随机数分布类 一个给定的随机数发生器一直会生成相同的随机数序列。一个函数如果定义了局部的随机数发生器，应该将（引擎和分布对象）定义为 st...

  • Jsoncpp 在C++开发中的一些使用记录

    jsoncpp 是一个C++ 语言实现的json库，非常方便得支持C++得各种数据类型到json 以及 json到各种数据类型的转化。 一个json 类型的数据如下： {"code" : 10.01,"files" : "","msg" : "","uploadid" : "UP000000" } 这种数据类型方便我们人阅读以...

  • 递归/回溯：Combination Sum II数组之和

    问题如下： 已知一组数(其中有重复元素)，求这组数可以组成的所有子集中，子 集中的各个元素和为整数target的子集，结果中无重复的子集。 例如: nums[] = [10, 1, 2, 7, 6, 1, 5]， target = 8 结果为: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 同样之前有...

  • 基于SfM计算相机姿态

    具体过程为： ① 通过相机标定方法，预先计算相机的内参矩阵； ② 相邻帧特征点匹配，并结合内参矩阵计算本征矩阵； ③ 本征矩阵分解获得相机的外参矩阵[R | T]，最终的相机移动距离等于矩阵T的Frobenius范数。 #include #include

  • 剑指offer：面试题34. 二叉树中和为某一值的路径

    题目：二叉树中和为某一值的路径 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22，               5              /             4   8    ...

  • vector容器 begin()与end()函数、front()与back()的用法

    begin函数： 函数原型: iterator begin(); const_iterator begin(); 功能： 返回一个当前vector容器中起始元素的迭代器。 end函数： 函数原型： iterator end(); const_iterator end(); 功能： 返回一个当前vector容器中末尾元素的迭代器。...

  • C++ STL: 容器vector源码分析

    文章目录前言vector的核心接口vector push_back实现vector 的 Allocatorvector 的 push_back总结...

  • leetcode-102 二叉树的层次遍历

    给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 方法一（非递归） 二叉树的层次遍历即二叉树的广度遍历，可以使...

©2024 11GX.COM