C语言四皇后问题

//title：4皇后问题的回溯算法求解

//Demo: 1）回溯算法实现4皇后问题；2）难点：树形结构的表达；3）用线性容器表达树形结构，并实现树的扫描??降低了树实现的难度

//author: Liping Chen

//email: [email protected]

//published date: 20125-4-11

#include <iostream>

#include <string.h>

#include <vector>

#include <stdlib.h>

using namespace std

//定义4皇后棋局的数据结构及方法

typedef struct Queen4 {

int vals[16]

int nQueens

int parent

//默认构造函数

Queen4() {

for(int i = 0i <16i++)

vals[i] = 0

parent = 0

nQueens = 0

}

//构造函数1

Queen4(int nvals[16]) {

for(int i = 0i <16i++)

vals[i] = nvals[i]

parent = 0

nQueens = 0

}

//找到当前布局中不为0的位置

int getPosition() {

for(int i = 0i <16i++)

if (vals[i] == 0) {

return i

}

return -1

}

//当设置皇后位置时，标记水平、垂直和斜线位置掩码

void setQueen(int pos) {

int row, col

vals[pos] = 1

nQueens++

row = pos / 4

col = pos % 4

for(int c = 1c <= 3c++) {

//右下

if (row + c <4 &&col + c <4)

if (vals[(row + c) * 4 + (col + c)] == 0)

vals[(row + c) * 4 + (col + c)] = 2

//左上

if (row - c >= 0 &&col - c >= 0)

if (vals[(row - c) * 4 + (col - c)] == 0)

vals[(row - c) * 4 + (col - c)] = 2

//左下

if (row + c <4 &&col - c >= 0)

if (vals[(row + c) * 4 + (col - c)] == 0)

vals[(row + c) * 4 + (col - c)] = 2

//右上

if (row - c >= 0 &&col + c >= 0)

if (vals[(row - c) * 4 + (col + c)] == 0)

vals[(row - c) * 4 + (col + c)] = 2

//右水平

if (col + c <4)

if (vals[row * 4 + (col + c)] == 0)

vals[row * 4 + (col + c)] = 2

//左水平

if (col - c >= 0)

if (vals[row * 4 + (col - c)] == 0)

vals[row * 4 + (col - c)] = 2

//下

if (row + c <4)

if (vals[(row + c) * 4 + col] == 0)

vals[(row + c) * 4 + col] = 2

//上

if (row - c >= 0)

if (vals[(row - c) * 4 + col] == 0)

vals[(row - c) * 4 + col] = 2

}

}

//输出当前棋局

void output(int level) {

int cnt = 0

char chars[100]

for(int k = 0k <levelk++)

chars[k] = ' '

chars[level] = '\0'

cout <<chars <<"Queen4=" <<endl <<chars

for(int i = 0i <16i++) {

cout <<vals[i] <<" "

cnt++

if (cnt % 4 == 0) cout <<endl <<chars

}

}

//递归调用输出历史棋局

void outputHist(vector<Queen4>&tr) {

if (parent)

tr[parent].outputHist(tr)

output(0)

}

//由棋的当前布局产生下一布局

void reproduce(vector<Queen4>&tr, int pos) {

int nvals[16]

bool inserted

//思考：为什么要使用nvals

for(int i = 0i <16i++)

nvals[i] = vals[i]

for(int i = 0i <16i++) {

if (nvals[i] == 0) {

nvals[i] = 1

//新结果加入容器

Queen4 q(tr[pos].vals)

q.setQueen(i)

q.parent = pos

tr.push_back(q)

}

}

}

}Queen4

//程序主函数

int main() {

Queen4 q0 //调用默认构造函数

vector<Queen4>tr //向量容器??作用相当于队列，可以向期中添加新的棋盘布局

int levels[1024] = {0} //记录每层的孩子数量??用于分层

tr.push_back(q0) //将初始棋盘加入容器

int oldn = 0, newn = 1, level = 0 //存储变量

//让根节点产生新孩子，并把新孩子加入容器

//若不再产生新孩子了，则认为已找到答案

//那么，最底层的就是答案（需要记录每层所产生的孩子数）

while(newn != oldn) {

//让最后的孩子再产生新孩子

for(int i = oldni <newni++) tr[i].reproduce(tr, i)

//更新老孩子和新孩子的数量

oldn = newn

levels[++level] = newn

newn = tr.size()

}

oldn = 1

//输出4皇后问题共有多少种解法

for(int i = levels[level-1]i <levels[level]i++) {

cout <<"4皇后放置走法：" <<oldn++ <<endl

tr[i].outputHist(tr)

}

return 0

}

本章内容来自《妙趣横生的算法》一书中。

回溯法是一种非常有效，适用范围相当广泛的算法设计思想。许多复杂的问题，规模较大的问题都可以使用回溯法求解。因此回溯法又有“通用解题方法”的美称。

回溯法的基本思想是：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度 探索 解空间树。当 探索 到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续 探索 下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含“剪枝” *** 作。

如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被 探索 到才结束。如果只要求解问题的一个解，问题的最终解，因此要跳过对以该结点为根的子树的系统 探索 ，逐层向其祖先结点回溯。这个过程叫做解空间树的那么在 探索 解空间树时，只要搜索到问题的一个解就可以结束了。

应用回溯法的思想求解四皇后问题

分析：

上面一节中已经详细介绍了回溯法解决四皇后问题的基本过程。在这里将给出具体的算法描述和程序清单。

其实在解决四皇后问题时，并不一定要真的构建出这样一棵解空间树，它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构来真实地创建出一棵解空间树，不过那样会比较浪费空间资源。

运行结果：

利用回溯算法解决

program Exp1(input,output)

const

n=4//皇后数

var

ans:longint

a,b,c:array[-100..100] of boolean

//a[i]表示第i列是否被占有

//b[i]表示第i条左斜对角线是否被占有

//c[i]表示第i条右斜对角线是否被占有

procedure search(i:longint)//按行搜索摆放第i个皇后

var

j:longint

begin

if i>n then //摆完了

begin

inc(ans)//计数器加1

exit

end

for j:=1 to n do //搜索摆在第几列上

if a[j] and b[i+j] and c[i-j] then

begin

a[j]:=false //标志为占有

b[i+j]:=false

c[i-j]:=false

search(i+1)

a[j]:=true //回溯

b[i+j]:=true

c[i-j]:=true

end

end

begin

fillchar(a,sizeof(a),true)

fillchar(b,sizeof(b),true)

fillchar(c,sizeof(c),true)

ans:=0

search(1)

writeln(ans)

end.

---