本科学生综合性实验报告

姓名 刘春云刘春云        学号 0103918＿＿  ＿

    专业 软件工程  班级＿软件103班   ＿   ＿

实验项目名称＿n皇后问题的回溯算法实验

指导教师及职称＿   赵晓平＿＿教授＿＿

开课学期    20##   至＿  20## 学年＿  三＿学期

上课时间      20##  年   2    月    20  日

学生实验报告（3）

一、问题描述

n后问题是指在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击。而一个皇后可以攻击与它处在同一行或同一列或同一斜线上的任何棋子。故n后问题可以理解为：在一个n*n的棋盘内放置n个皇后，使任意两个皇后不处在同一行或同一列或同一斜线上。

在这个问题中，我用了一个n*n的数组来存储棋盘，由于n后问题的典型是8皇后问题，所以我做的是8皇后问题。得出的解以以下形式出现在文件中：

8皇后问题

第1个解为:

oxxxxxxx

xxxxoxxx

xxxxxxxo

xxxxxoxx

xxoxxxxx

xxxxxxox

xoxxxxxx

xxxoxxxx

二、解题思路

根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组c[cur]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。

我用递归来做这问题。要求皇后所在的位置必须和其他皇后的位置不在同一行、列和斜线上，所以这个限定条件可以用来判断一个皇后是否能放在当前位置。既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现。

这小问题是什么呢？不难发现我们要在n*n的方格里放好n个皇后那我们就要知道在n（列）*n-1（行）是怎么放的，再有我们事先写好的判断条件放好最后行就搞定了。以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了。所以我们是以一行怎么放作为一个单元，每一行有n个位置可以放，每一个位置我们都要去判断一下所以我们就用循环来搞定。在这个循环里面我们让c[cur]=i也就是从这一行的第一个开始判断。先尝试放再去判断是否符合条件。如果符合条件我们就在调用这个函数本身向下一行搜索     

在进行判断下一行之前我们要判断一下cur是不是大于n也就是已经是最后一行了，如果是最后一行了我们就可以将其进行输出。打印n*n的矩阵皇后的位置用o表示出来没有的用x表示。

       三、算法描述

             分析：每个皇后在一行。做个n重循环，把每个皇后安排在每行的每个位置都试一遍。

1、棋盘是n*n数组，定义n+1个空棋盘。

2、第一个皇后从1行1列到1行n列循环。 

3、第二个皇后从2行1列到2行8列循环。

用 c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j]来判断是否与前面放置的皇后冲突若本点不符合，则此点能放棋子，继续搜索。否则退出循环

4、以此类推

在算法中#define n  8控制皇后个数 int *c; 指向n*n的数组指针 search函数是搜索下一行中哪列符合条件 

for(j=1;j<cur;j++)

         if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])//同列、同正对角线、同负对角线

{

                               ok=0;

                               break;

}/这个for循环检测是否与前cur-1行的皇后有冲突

四、算法实现

具体代码：

#include <iostream>

#include<fstream>

using namespace std;

#define n  8      //控制皇后个数

int *c;           //指向n*n的数组指针

void search(int cur)

{  

   void show();

   int i,j;

   if(cur==n+1)  

          show();//只要走到这，就一定可以有一组解并将它们输出

   else

          for(i=1;i<=n;i++)//按列搜索

          {

             bool ok=1;

             c[cur]=i;      //尝试将第cur行的皇后放入第i列

             for(j=1;j<cur;j++)//检测是否与前cur-1行的皇后有冲突

                    if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])//同列、同正对角线、同负对角线

                       {

                          ok=0;

                          break;

                       }

             if(ok)

                   search(cur+1);//不冲突，继续搜索

          }

}

void show()

{

       ofstream outfile;

       outfile.open("output.txt",ios::app);//打开output文件

    static       int count=0;//静态变量计算解的个数

    outfile<<"第"<<++count<<"个解为:"<<endl;

    for(int i=1;i<=n;i++)//在文件中输出结果：o表示皇后在，x表示皇后不在

       {

              for(int j=1;j<=n;j++)

              {

                if(c[i]==j)

            outfile<<"o";

                else

                       outfile<<"x";

              }

        outfile<<endl;

       }

}

void main()

{

       c=new int[n+1];

       ofstream outfile;

       outfile.open("output.txt",ios::app);//创建output文件

       outfile<<n<<"皇后问题"<<endl;        

       search(1);//由第一行开始搜索

outfile.close();

}

五、程序测试及分析

        

结果输出：

 

六、总结

回溯法是一种最一般的算法设计方法，特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。我解决n皇后问题用的算法正是基于回溯算法的思想提出的一种递归算法，并且找出了八皇后问题的92个真正不同的解，此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题，例如汉诺塔等。与非递归算法设计相比，它往往更容易一些，但是会耗费更多的时间和空间，执行效率不高。

七、导教师评语及成绩：

评语：

成绩：       指导教师签名：

                                               批阅日期：

第二篇：算法分析实验报告--回溯法

《算法设计与分析》实验报告

回溯法

一、试验名称：回溯法

（1）    写出源程序，并编译运行

（2）    详细记录程序调试及运行结果

二、实验目的

(1)   掌握回溯算法思想

(2)   掌握回溯递归原理

(3)   了解回溯法典型问题

三、实验内容

(1)   编写一个简单的程序，解决8皇后问题

(2)   批处理作业调度

(3)   数字全排列问题

四、算法思想分析

（1）    编写一个简单的程序，解决8皇后问题

（2）    批处理作业调度

[问题描述]给定n个作业的集合J=(J1, J2, … , Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器i的处理时间为tji，i=1,2, … ,n; j=1,2。对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。

要求输入：

1、作业数

2、每个作业完成时间表：

要求输出：

1、最佳完成时间

2、最佳调度方案

提示

提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。

（3）数字全排列问题：

任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。

注意：数字不能重复，N由键盘输入（N<=9）。

五、算法源代码及用户程序

(1)   编写一个简单的程序，解决8皇后问题

N皇后问题

代码1：

#include<stdio.h>

#define NUM 8                //定义数组大小int a[NUM + 1];

int main ()

{

 int a[100];

     int number;

     int i;

     int k;

     int flag;

     int notfinish = 1;

     int count = 0;     i = 1;                    //正在处理的元素下标，表示前i－1个元素已符合要求，正在处理第i个元素

     a[1] = 1;                 //为数组的第一个元素赋初值

     printf ("Result:\n");     while (notfinish)             //处理尚未结束

     {

   while (notfinish && i <= NUM)         //处理尚未结束且还没处理到第NUM个元素

   {

    for (flag = 1, k = 1; flag && k < i; k++)         //判断是否有多个皇后在同一行

             {

     if (a[k] == a[i])

     flag = 0;

    }

  

    for (k = 1; flag && k < i; k++)         //判断是否有多个皇后在同一对角线

             {

     if ((a[i] == a[k] - (k - i)) || (a[i] == a[k] + (k - i)))

     flag = 0;

    }    if (!flag)             //若存在矛盾不满足要求，需要重新设置第i个元素

             {

     if (a[i] == a[i - 1])         //若a［i］的值已经经过一圈追上a［i－1］的值

     {

      i--;             //退回一步，重新试探处理前的一个元素

      if (i > 1 && a[i] == NUM)

      {

       a[i] = 1;         //当a［i］的值为NUM时将a［i］的值置1

      }

      else if (i == 1 && a[i] == NUM)

      {

       notfinish = 0;         //当第一位的值达到NUM时结束

      }

      else

      {

       a[i]++;         //将a［i］的值取下一个值

      }

     }

     else if (a[i] == NUM)

     {

      a[i] = 1;

     }

     else

     {

      a[i]++;             //将a［i］的值取下一个值

     }

             }

    else if (++i <= NUM)         //第i位已经满足要求则处理第i＋1位

    {

     if (a[i - 1] == NUM)         //若前一个元素的值为NUM则a[i]＝1

     {

      a[i] = 1;

     }

     else

     {

      a[i] = a[i - 1] + 1;         //否则元素的值为前一个元素的下一个值

     }

    }

         }     

   if (notfinish)

   {

    ++count;

    printf ((count - 1) % 3 ? "[%2d]:" : "\n[%2d]:", count);

   

    for (k = 1; k <= NUM; k++)         //输出结果

             {

     printf (" %d", a[k]);

    }    if (a[NUM - 1] < NUM)         //修改倒数第二位的值

    {

     a[NUM - 1]++;

    }

    else

    {

     a[NUM - 1] = 1;

    }    i = NUM - 1;             //开始寻找下一个满足条件的解

         }}//while

     printf ("\n");

     return 0;

}

(2)   批处理作业调度

import java.util.*;

public class FlowShop

{

static int n; //作业数

static int f1; //机器1完成处理时间

static int f; //完成时间和

static int bestf; //当前最优值

static int[][] m; //各作业所需要的处理时间

static int[] x; //当前作业调度

static int[] bestx; //当前最优作业调度

static int[] f2; //机器2完成处理时间

public static void trackback(int i) {

if (i == n) {

for (int j = 0; j < n; j++) {

bestx[j] = x[j];

}

bestf = f;

} else {

for (int j = i; j < n; j++) {

f1 += m[x[j]][0];

if (i > 0) {

f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + m[x[j]][1];

} else {

f2[i] = f1 + m[x[j]][1];

}

f += f2[i];

if (f < bestf) {

swap(x, i, j);

trackback(i + 1);

swap(x, i, j);

}

f1 -= m[x[j]][0];

f -= f2[i];

}

}

}

private static void swap(int[] x, int i, int j) {

int temp = x[i];

x[i] = x[j];

x[j] = temp;

}

private static void test() {

n = 3;

int[][] testm = {{2, 1}, {3, 1}, {2, 3}};

m = testm;

int[] testx = {0, 1, 2};

x = testx;

bestx = new int[n];

f2 = new int[n];

f1 = 0;

f = 0;

bestf = Integer.MAX_VALUE;

trackback(0);

System.out.println(Arrays.toString(bestx));

System.out.println(bestf);

}

public static void main(String[] args)

{

test();

System.out.println("Hello World!");

}

}

(3)   数字全排列问题

#include "stdio.h"

#include "conio.h"

int num,cont=0;

main()

{   int i,n,a[30];

    printf("enter N :");

    scanf("%d",&num);

    for(i=1;i<=num;i++)

    a[i]=i;

    perm(a,1);

    printf("\n%d",cont);

    getch();

}

int perm(int b[], int i)

{int k,j,temp;

 
if(i==num)

    {for(k=1;k<=num;k++)

      printf("%d ",b[k]);

    printf("\t");

    cont++;

    }

 
else

   for(j=i;j<=num;j++)

   {temp=b[i];b[i]=b[j],b[j]=temp;

    perm(b,i+1);

    temp=b[i];b[i]=b[j],b[j]=temp;

    }

  return(0);

}

六、实验结果与思想

     这次的实验是回溯法，我也对回溯法有了一个基本印象，所谓回溯法，就是把所有的可行解都遍历一遍，遇到不可行的就回溯到上一步，然后通过添加约束条件和限界条件就可以得到最优解。