n皇后问题

8皇后问题

个人信息：就读于燕大本科软件工程专业 目前大三;

本人博客：google搜索“cqs_2012”即可;

个人爱好：酷爱数据结构和算法，希望将来搞科研为人民作出自己的贡献

博客内容：n皇后问题

博客时间：2014-4-9

编程语言：C++

编程坏境：Windows 7 专业版 x64

编程工具：vs2008 32位编译器

制图工具：office 2010 ppt

引言

好久不见的system（"pause"） and  goto 又见面了，见到老朋友很开心。

题目

n皇后问题

思路

回溯算法，个人感觉和老鼠走迷宫有异曲同工之妙。

n皇后问题规则如下

每两个皇后棋子不能落在同一条直线上

解决算法 回溯算法

需要工具 栈

实验

程序截图如下

solution 如下

结果共有 92 ，solution 如下

solution 1
* O O O O O O O 
O O O O * O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
solution 2
* O O O O O O O 
O O O O O * O O 
O O O O O O O * 
O O * O O O O O 
O O O O O O * O 
O O O * O O O O 
O * O O O O O O 
O O O O * O O O 
solution 3
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
O O * O O O O O 
solution 4
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
O O O O O * O O 
O O * O O O O O 
solution 5
O * O O O O O O 
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
solution 6
O * O O O O O O 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
solution 7
O * O O O O O O 
O O O O * O O O 
O O O O O O * O 
O O O * O O O O 
* O O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
solution 8
O * O O O O O O 
O O O O O * O O 
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
O O O O O O O * 
O O * O O O O O 
O O O O * O O O 
solution 9
O * O O O O O O 
O O O O O * O O 
O O O O O O O * 
O O * O O O O O 
* O O O O O O O 
O O O * O O O O 
O O O O O O * O 
O O O O * O O O 
solution 10
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
O O O O * O O O 
* O O O O O O O 
O O O * O O O O 
solution 11
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O O O O O O * 
* O O O O O O O 
O O O * O O O O 
O O O O O * O O 
O O * O O O O O 
solution 12
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
O O O O O O * O 
O O O * O O O O 
solution 13
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
O O O O O * O O 
solution 14
O O * O O O O O 
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
O O O O O * O O 
solution 15
O O * O O O O O 
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
solution 16
O O * O O O O O 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
solution 17
O O * O O O O O 
O O O O * O O O 
O O O O O O O * 
O O O * O O O O 
* O O O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
solution 18
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O * O O O 
O O O O O O O * 
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
solution 19
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
* O O O O O O O 
O O O * O O O O 
O O O O O O O * 
O O O O * O O O 
solution 20
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 
* O O O O O O O 
O O O O O O O * 
O O O * O O O O 
solution 21
O O * O O O O O 
O O O O O * O O 
O O O * O O O O 
* O O O O O O O 
O O O O O O O * 
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
solution 22
O O * O O O O O 
O O O O O * O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
solution 23
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
* O O O O O O O 
O O O * O O O O 
O O O O O O * O 
O O O O * O O O 
O * O O O O O O 
solution 24
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
* O O O O O O O 
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
solution 25
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
solution 26
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O O O * 
O O O O * O O O 
* O O O O O O O 
O O O * O O O O 
O O O O O * O O 
solution 27
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
* O O O O O O O 
O O O O * O O O 
solution 28
O O * O O O O O 
O O O O O O O * 
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O * O O O 
solution 29
O O O * O O O O 
* O O O O O O O 
O O O O * O O O 
O O O O O O O * 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
solution 30
O O O * O O O O 
* O O O O O O O 
O O O O * O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
solution 31
O O O * O O O O 
O * O O O O O O 
O O O O * O O O 
O O O O O O O * 
O O O O O * O O 
* O O O O O O O 
O O * O O O O O 
O O O O O O * O 
solution 32
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
* O O O O O O O 
O O O O * O O O 
solution 33
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
O O O O O O O * 
O O O O * O O O 
* O O O O O O O 
solution 34
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 
* O O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
solution 35
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
solution 36
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
O O O O O O * O 
solution 37
O O O * O O O O 
O O O O O * O O 
* O O O O O O O 
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
O O * O O O O O 
O O O O O O * O 
solution 38
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
solution 39
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O * O O O O O O 
solution 40
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
O O O O O O O * 
O O O O * O O O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
solution 41
O O O * O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
* O O O O O O O 
O O O O O * O O 
solution 42
O O O * O O O O 
O O O O O O * O 
O O O O * O O O 
O * O O O O O O 
O O O O O * O O 
* O O O O O O O 
O O * O O O O O 
O O O O O O O * 
solution 43
O O O * O O O O 
O O O O O O * O 
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
solution 44
O O O * O O O O 
O O O O O O O * 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 
solution 45
O O O * O O O O 
O O O O O O O * 
* O O O O O O O 
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
solution 46
O O O * O O O O 
O O O O O O O * 
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
solution 47
O O O O * O O O 
* O O O O O O O 
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
solution 48
O O O O * O O O 
* O O O O O O O 
O O O O O O O * 
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
solution 49
O O O O * O O O 
* O O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
solution 50
O O O O * O O O 
O * O O O O O O 
O O O * O O O O 
O O O O O * O O 
O O O O O O O * 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
solution 51
O O O O * O O O 
O * O O O O O O 
O O O * O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O O O * 
O O O O O * O O 
* O O O O O O O 
solution 52
O O O O * O O O 
O * O O O O O O 
O O O O O * O O 
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
O O O O O O O * 
O O * O O O O O 
solution 53
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
* O O O O O O O 
O O O * O O O O 
O O O O O O * O 
O O * O O O O O 
O O O O O * O O 
solution 54
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
O O O O O O * O 
solution 55
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
solution 56
O O O O * O O O 
O O * O O O O O 
O O O O O O O * 
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
O O O O O * O O 
O * O O O O O O 
solution 57
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
O * O O O O O O 
solution 58
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
O O * O O O O O 
solution 59
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
O O O O O O O * 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
solution 60
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O * O O O O 
O O O O O O O * 
solution 61
O O O O * O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O O * 
O O O * O O O O 
solution 62
O O O O * O O O 
O O O O O O * O 
O O O * O O O O 
* O O O O O O O 
O O * O O O O O 
O O O O O O O * 
O O O O O * O O 
O * O O O O O O 
solution 63
O O O O * O O O 
O O O O O O O * 
O O O * O O O O 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
solution 64
O O O O * O O O 
O O O O O O O * 
O O O * O O O O 
* O O O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
solution 65
O O O O O * O O 
* O O O O O O O 
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
O O * O O O O O 
O O O O O O * O 
O O O * O O O O 
solution 66
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
O O O O O O O * 
O O O * O O O O 
solution 67
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
* O O O O O O O 
O O O * O O O O 
O O O O O O O * 
O O O O * O O O 
O O * O O O O O 
solution 68
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
solution 69
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O O * 
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 
solution 70
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O O * 
O O O O * O O O 
O * O O O O O O 
O O O * O O O O 
O O O O O O * O 
solution 71
O O O O O * O O 
O O * O O O O O 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
solution 72
O O O O O * O O 
O O * O O O O O 
O O O O * O O O 
O O O O O O O * 
* O O O O O O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O * O 
solution 73
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
O O O O O O O * 
* O O O O O O O 
O O O O * O O O 
solution 74
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O * O O O O O O 
O O O O O O O * 
O O O O * O O O 
* O O O O O O O 
O O O * O O O O 
solution 75
O O O O O * O O 
O O * O O O O O 
O O O O O O * O 
O O O * O O O O 
* O O O O O O O 
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
solution 76
O O O O O * O O 
O O O * O O O O 
* O O O O O O O 
O O O O * O O O 
O O O O O O O * 
O * O O O O O O 
O O O O O O * O 
O O * O O O O O 
solution 77
O O O O O * O O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O * O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
solution 78
O O O O O * O O 
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
O * O O O O O O 
O O O O O O O * 
solution 79
O O O O O * O O 
O O O * O O O O 
O O O O O O * O 
* O O O O O O O 
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
O O * O O O O O 
solution 80
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O * O O O O O 
solution 81
O O O O O O * O 
* O O O O O O O 
O O * O O O O O 
O O O O O O O * 
O O O O O * O O 
O O O * O O O O 
O * O O O O O O 
O O O O * O O O 
solution 82
O O O O O O * O 
O * O O O O O O 
O O O * O O O O 
* O O O O O O O 
O O O O O O O * 
O O O O * O O O 
O O * O O O O O 
O O O O O * O O 
solution 83
O O O O O O * O 
O * O O O O O O 
O O O O O * O O 
O O * O O O O O 
* O O O O O O O 
O O O * O O O O 
O O O O O O O * 
O O O O * O O O 
solution 84
O O O O O O * O 
O O * O O O O O 
* O O O O O O O 
O O O O O * O O 
O O O O O O O * 
O O O O * O O O 
O * O O O O O O 
O O O * O O O O 
solution 85
O O O O O O * O 
O O * O O O O O 
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
* O O O O O O O 
O O O O O * O O 
O O O * O O O O 
solution 86
O O O O O O * O 
O O O * O O O O 
O * O O O O O O 
O O O O * O O O 
O O O O O O O * 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
solution 87
O O O O O O * O 
O O O * O O O O 
O * O O O O O O 
O O O O O O O * 
O O O O O * O O 
* O O O O O O O 
O O * O O O O O 
O O O O * O O O 
solution 88
O O O O O O * O 
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O * O O 
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
solution 89
O O O O O O O * 
O * O O O O O O 
O O O * O O O O 
* O O O O O O O 
O O O O O O * O 
O O O O * O O O 
O O * O O O O O 
O O O O O * O O 
solution 90
O O O O O O O * 
O * O O O O O O 
O O O O * O O O 
O O * O O O O O 
* O O O O O O O 
O O O O O O * O 
O O O * O O O O 
O O O O O * O O 
solution 91
O O O O O O O * 
O O * O O O O O 
* O O O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O * O O O 
O O O O O O * O 
O O O * O O O O 
solution 92
O O O O O O O * 
O O O * O O O O 
* O O O O O O O 
O O * O O O O O 
O O O O O * O O 
O * O O O O O O 
O O O O O O * O 
O O O O * O O O 

代码

test.cpp(程序运行结果会保存在 huanghou.txt 文件里，请注意查看)

#include<iostream>
#include<utility>
#include<stack>
#include<fstream>
using namespace std;

// function: check huanghou
// input: a new 位置 with i and j ,and the stack( 值传递 )
// output: bool
// 功能：判断当前位置时候是皇后问题的答案
bool _check_huanghou( int i,int j,stack<std::pair<int,int>> result );

// function: output huanghou
// input: the result stack( 值传递 )
// output: void
// 功能：输出皇后问题的答案
void _OUTput_huanghou(stack<std::pair<int,int>> result,ofstream & writer);


// function: n 皇后问题
// input: n
// output: bool
// 功能：n皇后问题（回溯算法，application of stack）
void _Eight_huanghou(int n);

// function: main
int main()
{
	int n;
	cout<<"请输入皇后的个数"<<endl;
	while(cin>>n)
	{
		_Eight_huanghou(n);
		cout<<"请输入皇后的个数"<<endl;
	}
	system("pause");
	return 0;
}


// function: n 皇后问题
// input: n
// output: bool
// 功能：n皇后问题（回溯算法，application of stack）
void _Eight_huanghou(int n)
{
	ofstream writer;
	writer.open("huanghou.txt");
	writer.clear();
	
	stack<std::pair<int,int>> result  ;
	std::pair<int,int> top ;
	bool r = false;
	int number = 0 ;

	result.push(std::make_pair(0,0));
	while(! result.empty())
	{	
		top = result.top();
		if(top.first < n-1)
		{
			int j;
			// push stack
			for( j = 0;j<n;j++)
			{
				// check

				r = _check_huanghou( top.first+1,j,result );
				if(r == true)
				{
					result.push(std::make_pair(top.first+1,j));
					break;
				}
			}
			// pop stack
			if( j == n )
			{
				while( j == n && !result.empty())
				{
					A:
					top = result.top() ;
					result.pop() ;						
					for( j = top.second + 1; j<n; j++ )
					{
						r = _check_huanghou( top.first,j,result );
						if( r == true )
						{
							result.push(std::make_pair(top.first,j));
							break ;
						}
					}
				}
			}
		}
		// get the result;
		else
		{
			cout<<" one solution "<<++ number<<endl;
			writer<<"solution "<<number<<"\n";
			
			_OUTput_huanghou(result,writer);
			goto A;
		}
		
	}

	writer.close();
	//delete & result;
}


// function: check huanghou
// input: a new 位置 with i and j ,and the stack( 值传递 )
// output: bool
// 功能：判断当前位置时候是皇后问题的答案
bool _check_huanghou( int i,int j,stack<std::pair<int,int>> result )
{
	std::pair<int,int> top ;
	while(! result.empty())
	{
		top = result.top();
		result.pop();
		if(top.first == i || top.second == j || top.first - top.second == i - j || top.first + top.second == i+j )
		{
			return false;
		}
	}
	return true;
}


// function: output huanghou
// input: the result stack( 值传递 )
// output: void
// 功能：输出皇后问题的答案
void _OUTput_huanghou(stack<std::pair<int,int>> result,ofstream &writer)
{
	std::pair<int,int> top;
	int n = result.size();
	char ** data = new char*[n];
	for(int i=0;i<n;i++)
	{
		data[i] = new char[n];
		for(int j =0;j<n;j++)
		{
			data[i][j] = ‘O‘;
		}
	}
	while(! result.empty())
	{
		top = result.top();
		data[top.first][top.second] = ‘*‘;
		result.pop();
	}
	for(int i = 0;i<n;i++)
	{
		for(int j =0;j<n;j++)
		{
			writer<<data[i][j]<<‘ ‘;
		}
		writer<<"\n";
	}
}

 

 

n皇后问题,布布扣,bubuko.com

n皇后问题

原文：http://blog.csdn.net/cqs_experiment/article/details/23480415