C语言四皇后问题

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

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

//author: Liping Chen

//email: alaclp@qq.com

//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

}

四皇后问题是将4个皇后放置在4x4的棋盘上，使得它们塌销互相不攻击（即不在同一行、列或对角线上）。这个问题有两种可能的解决方案。

第一个解决方案是将皇后放置在每行中的一个不同的列上。这种情况下，我们可以按照以下方式放置皇后：

第一行：第一列，第二行：第二列，第三行：第三列，第四行：第四列

第二个解决方案是将皇后放置在每列中的一个不同的行上。这种情况下，我们可以按照以下方式放置毁游皇后：

第一列：第一行，纤衫销第二列：第三行，第三列：第四行，第四列：第二行

因此，四皇后问题有两个解决方案。

---