回溯法之二---8皇后问题

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上.
问题分析:
第一步定义问题的解空间
这个问题解空间就是8个皇后在棋盘中的位置.
第二步定义解空间的结构
可以使用8*8的数组，但由于任意两个皇后都不能在同行，我们可以用数组下标表示
行，数组的值来表示皇后放的列，故可以简化为一个以维数组x[9]。
第三步以深度优先的方式搜索解空间，并在搜索过程使用剪枝函数来剪枝
根据条件:x[i] == x[k]判断处于同一列
abs(k-i) == abs(x[k]-x[i]判断是否处于同一斜线
我们很容易写出剪枝函数：

Cpp代码

bool canPlace( int k){
for ( int i=1;i<k;i++){
//判断处于同一列或同一斜线
if (x[i]==x[k]||abs(k-i)==abs(x[k]-x[i])) return false ;
}
return true ;
}

      bool canPlace(int k){
	for(int i = 1; i < k; i++){
        //判断处于同一列或同一斜线
	   if(x[i] == x[k] || abs(k-i) == abs(x[k]-x[i])) 		       return false;
	}
	return true;
}

然后我们按照回溯框架一，很容易写出8皇后的回溯代码：

Cpp代码

void queen( int i){
if (i>8){
print();
return ;
}
for ( int j=1;j<=8;j++){
x[i]=j; //记录所放的列
if (canPlace(i))queen(i+1);
}
}

      void queen(int i){
	if(i > 8){
		print();
		return;
	}
	for(int j = 1; j <= 8; j++){
	  x[i] = j;//记录所放的列
	  if(canPlace(i)) queen(i+1);
	}
}

整个代码：

Cpp代码

#include<iostream>
#include<cmath>
using namespace std;
int x[9];
void print(){
for ( int i=1;i<=8;i++)
cout<<x[i]<< "" ;
cout<<endl;
}
bool canPlace( int k){
for ( int i=1;i<k;i++){
//判断处于同一列或同一斜线
if (x[i]==x[k]||abs(k-i)==abs(x[k]-x[i]))
return false ;
}
return true ;
}
void queen( int i){
if (i>8){
print();
return ;
}
for ( int j=1;j<=8;j++){
x[i]=j;
if (canPlace(i))queen(i+1);
}
}
int main(){
queen(1);
return 0;
}

回溯法之二---8皇后问题

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

2元

5元

10元

20元

自定义