实验四 回溯法求n皇后问题.doc

实验四回溯法求n皇后问题
本科实验报告
课程名称:
实验项目:回溯法求
实验地点:
专业班级:
学生姓名:
指导教师: 算法设计与分析 n皇后问题学号:
一、实验目的
1. 掌握回溯算法的基本思想
2. 通过n皇后问题求解熟悉回溯法
3. 使用蒙特卡洛方法分析算法的复杂度
二、实验内容
要求在一个8*8的棋盘上放置8个皇后,使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上,则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。
三、实验环境
程序设计语言:c++
编程工具:microsoft visual studio 2010
四、算法描述和程序代码
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int queen[8];
int total = 0; //方案计数
int i, j, k;
for (i=0;i<8;i++) queen[i] = 0; //八皇后全放在第0列
for (i=1;;){ //首先安放第0行皇后
if(queen[i]<8){ //皇后还可调整
k=0; //检查与第k个皇后是否互相攻击 while(k<i&&(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<8) continue;
for(j=0;j<8;j++) cout<<queen[j]; //已完成,输出结果
cout<<" ";
total++; //方案数加1