n皇后问题实验报告.doc

N后问题算法
一、实验目的及要求
所要涉及或掌握的知识：
1.       了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。
2.       运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解
3.       在运用迭代的方法实现编程时，要注意回溯点
二、问题描述及实验容
对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。
最后程序运行的结果是c[1…6]={1,5,8,6,3,7 }
三、问题分析和算法描述
6-QUEENS的算法表示：
输入：空。
输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7}
1.       for k=1 to 6
2.       c[k]=0          //没有放皇后
3.       end for
4.       flag=false
5.       k=1
6.       while k>=1
7.          while c[k]<=5
8.                c[k]=c[k]+1
9.                if c为合法着色  then set flag=ture 且从两个while循环退出
10.             else if c是部分解 then k=k+1
11.       end while
12.    c[k]=0               //回溯并c[k]=0
13.    k=k-1
14.    end while
15.    if flag  then output c
16.    else output “no solution”
四、具体实现
# include <>
#include <>
#include <>
#include <>
#include "iostream"
using namespace std;
int total = 0; //方案计数
void backtrace(int queen[],int N)
{
int i, j, k;
cout<<"★为皇后放置位置\n";
for (i=1;;)
{ //首先安放第1行
   if(queen[i]<N)
   { //皇后还可调整
    k=0; //检查与第k个皇后是否互相攻击
    while(k<i&&abs(queen[k]-queen[i])&&(abs(queen[k]-queen[i])-abs(k-i))) k++;
    if (k<=i-1)
    { //与第k个皇后互相攻击
     queen[i]++; //第i个皇后右移一列，重测
     continue;
    }
    i++; //无冲突，安置下一行皇后
    if(i<N) continue;
     cout<<"第"<<total+1<<"种为：\n";
     for(int i=0;i<N;i++)
     {
     
      
      for(int j=0;j<queen[i];j++)
       cout<<"□";
      cout<<"★";
      for(int k=queen[i]+1;k<N;k++)
       cout<<"□";
      cout<<endl;
     }
    
    total++; //方案数加1
    if(total%5==0) cout<<endl;
    queen[N-1]++; // 将第8个皇后右移一列，前8个不动
    i=N-1; //此处是制造机会，如不成功则回溯，关键一步
   }
   else //当前行皇后无法安置，回溯
   {
    queen[i]=0; //当前行皇后回归1列
    i--; //回溯到前一行皇后
    if(i<0)
    { //回溯到数组1行之前，结束
     cout<<"\n针对 "<<N<<" 皇后问题，"<<"一共找到 "<<total<<" 种放置方法。 "<<endl;
     cout<<endl;
     return;
    }
    else queen[i]++; //前一行皇后右移一列
   }
}