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++)
     {