八皇后问题 （7）
要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。
提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45o都不能有另一个皇后。解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。首先
将第一个皇后放于第一行第一列，然后开始向下一行递归。每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置。

#include<iostream>
#include<vector>
#include<windows.h>
using namespace std;
void search1(vector<int> a,int x,int N,int& s){//其中999代表皇后，1代表皇后的攻击范围
for(int ix=0;ix<N;ix++)//0表示能够放皇后的位置
{
if(a[ix+x*N]==0){
vector<int> bb;
a[ix+x*N]=999;
int ih=0,is=0;
while(ih<N){//行改变
if(a[ih+x*N]!=999)
{
if(a[ih+x*N]!=1)bb.insert(bb.end(),(ih+x*N));
a[ih+x*N]=1;
}
ih++;
}
while(is<N){//列改变
if(a[ix+is*N]!=999)
{
if(a[ix+is*N]!=1) bb.insert(bb.end(),(ix+is*N));
//cout << ix+is*N <<endl;
a[ix+is*N]=1;
}
is++;
}
for(int iy=0;iy<N;iy++){//左上斜线改变
//cout << ix+x*N-iy*(N+1) <<endl;
//cout << ix <<endl;
if((ix-iy)>=0&&(x-iy)>=0) {
//cout << ix+x*N-iy*(N+1) <<endl;
if(a[ix+x*N-iy*(N+1)]==0) {bb.insert(bb.end(),(ix+x*N-iy*(N+1)));
//cout << ix+x*N-iy*(N+1) <<endl;
a[ix+x*N-iy*(N+1)]=1;}
}
else break;
}
for(int iy=0;iy<N;iy++){//右上斜线改变
if((x-iy)>=0&&(ix+iy)<N) {
if(a[ix+x*N-iy*(N-1)]==0) {bb.insert(bb.end(),(ix+x*N-iy*(N-1)));
// cout << ix+x*N-iy*(N-1) <<endl;
a[ix+x*N-iy*(N-1)]=1;}
}
else break;
}
for(int iz=0;iz<N;iz++){//右下斜线改变
//cout <<ix <<endl;
//cout << (ix+x*N+iz*(N+1))%N <<endl;
if((ix+iz)<N&&(x+iz)<N){
// cout << ix <<endl;
if(a[ix+x*N+iz*(N+1)]==0) {bb.insert(bb.end(),(ix+x*N+iz*(N+1)));
//cout << ix+x*N+iz*(N+1) <<endl;
a[ix+x*N+iz*(N+1)]=1;}

}
else break;
}
for(int iz=0;iz<N;iz++){//左下斜线改变
if((x+iz)<N&&(ix-iz)>=0){
if(a[ix+x*N+iz*(N-1)]==0) {bb.insert(bb.end(),(ix+x*N+iz*(N-1)));
a[ix+x*N+iz*(N-1)]=1;}
}
else break;
}
if(x+1<N)
search1(a,x+1,N,s);
else { cout <<"搜索得到 :" <<endl;
for(int ii=0;ii<N*N;ii++)
if(a[ii]==999) cout << ii/N << " " << ii%N <<endl;
s++;
//system("pause");
}
a[ix+x*N]=0;
vector<int>::const_iterator it=bb.begin();
while(it!=bb.end()){
a[*it]=0;
it++;
//cout << *it++ <<endl;
}
}
}
}
int main(){
int n,s=0;
//Sleep(2000);
cout <<"输入皇后个数N=";
cin >> n;
vector<int> aa;
for(int i=0;i<n*n;i++)
aa.insert(aa.end(),0);
search1(aa,0,n,s);
cout <<endl;
cout <<s <<endl;
system("pause");
return 0;
}
//cout <<endl;
/* is=ih=0;
while(ih<N){
if(a[ih+x*N]==1)
a[ih+x*N]=0;
ih++;
}
while(is<N){
if(a[ix+is*N]==1)
a[ix+is*N]=0;
is++;
}
for(int iy=0;iy<=x;iy++){
if(ix+x*N-iy*(N+1)>=0&&(ix-iy)%N<ix/*&&a[ix+x*N-iy*(N+1)]!=999) a[ix+x*N-iy*(N+1)]=0;
else break;
}
for(int iy=0;iy<=x;iy++){
if(ix+x*N-iy*(N-1)>=0&&(ix+iy)%N>ix/*&&a[ix+x*N-iy*(N+1)]!=999) a[ix+x*N-iy*(N-1)]=0;
else break; }
for(int iz=0;iz<N-x;iz++){
if(ix+x*N+iz*(N+1)<N*N&&(ix+iz)%N>ix/*&&a[ix+x*N-iz*(N+1)]!=999) a[ix+x*N+iz*(N+1)]=0;
else break;
}
for(int iz=0;iz<N-x;iz++){

if(ix+x*N+iz*(N-1)<N*N&&(ix-iz)%N<ix/*&&a[ix+x*N-iz*(N+1)]!=999) a[ix+x*N+iz*(N-1)]=0;
else break;
} */

谢谢2楼 不过好象有个错误。。。。

#include<stdio.h>
#include<math.h>
#define N 8
void check(int p[])
{int i, j,a;
for (i=0; i<N-1; i++)
for (j=i+1; j<N; j++)
if (abs(p[j]-p[i])==j-i) return;
for (a=1, i=0,printf(" "); i<N; printf ("%d",p[i++]),a++ );

}
void permute(int n, int p[])
{
int i, j;
if (n==1) check(p);
for (i=0, j=n-1; i<N; i++)
if (!p[i]) {p[i]=j; permute(j,p); p[i]=0;}
}
void main()
{
int p[N]={0}, n=N;
printf("\n");
permute(n+1,p);
printf("\n");
}

2楼：
8皇后问题需要写那么多代码吗？

好像有不了啊,怎么搞的啊,