个人技术笔记

八皇后问题

发布时间：2015-11-18  栏目：软件算法  评论：0 Comments

算法提出：

在国际象棋棋盘上（8*8）放置八个皇后，使得任意两个皇后之间不能在同一行，同一列，也不能位于同于对角线上。问共有多少种不同的方法，并且指出各种不同的放法。

算法思路：

首先我们分析一下问题的解，我们每取出一个皇后，放入一行，共有八种不同的放法，然后再放第二个皇后，同样如果不考虑规则，还是有八种放法。于是我们可以用一个八叉树来描述这个过程。从根节点开始，树每增加一层，便是多放一个皇后，直到第8层（根节点为0层），最后得到一个完全八叉树。

紧接着我们开始用深度优先遍历这个八叉树，在遍历的过程中，进行相应的条件的判断。以便去掉不合规则的子树。

那么具体用什么条件来进行子树的裁剪呢？

我们先对问题解的结构做一个约定。

用X[i]来表示，在第i行，皇后放在了X[i]这个位置。

于是我们考虑第一个条件，不能再同一行，同一列，于是我们得到x[i]不能相同。剩下一个条件是不能位于对角线上，这个条件不是很明显，我们经过分析得到，设两个不同的皇后分别在j，k行上，x[j],x[k]分别表示在j,k行的那一列上。那么不在同一对角线的条件可以写为abs((j-k))!=abs(x[j]-x[k])，其中abs为求绝对值的函数。

于是下面我们便可以利用一个递归的调用来遍历八叉树。

 

#include <iostream>
#include <math.h>
#include<cstdlib>

using namespace std;

static int num;
static int *x;
static int sum;

//k is the row number
bool place(int k)
{
for(int j = 1;j<k;j++)

if(abs(x[k] – x[j]) == abs(k-j)||x[j] == x[k])

return false;

//if valid, return true
return true;
}

//t is the row number
void backtrack(int t)
{

if(t>num)

{

//reach the leaf node, count

sum++;

for(int m = 1;m<num;m++)

{

cout<<x[m];

}

cout<<endl;

}

else

for(int i = 1;i<=num;i++)

{

//for the row t, try all columns in sequence

x[t] = i;

//for each colum, if valid,go on to place the next row

if(place(t)) backtrack(t+1);

}

}

 

int main()

{
num = 8;
sum = 0;
x = new int[num+1];
//initial values as 0, no placement

for(int i= 0;i<=num;i++)

x[i] = 0;

//handle it from the first row

backtrack(1);
cout<<“Solution number is: “<<sum;

return 0;
}

 

以上在Linux平台下编译通过，输出为92种。

留下评论

You must be logged in to post a comment.