算法[回溯]-八皇后问题

Posted on

回溯法解题思路：

（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索.

问题描述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解决思路

1、使用一个一维数组表示皇后的位置,
其中数组的下标表示皇后所在的行,
数组元素的值表示皇后所在的列.
2、假设前n-1行的皇后已经按照规则排列好，
那么可以使用回溯法逐个试出第n行皇后的合法位置，
所有皇后的初始位置都是第0列，
那么逐个尝试就是从0试到N-1，
如果达到N，仍未找到合法位置，
那么就置当前行的皇后的位置为初始位置0，
然后回退一行，且该行的皇后的位置加1，继续尝试，
如果目前处于第0行，还要再回退，说明此问题已再无解。
3、如果当前行的皇后的位置还是在0到N-1的合法范围内，
那么首先要判断该行的皇后是否与前几行的皇后互相冲突
如果冲突，该行的皇后的位置加1，继续尝试，
如果不冲突，判断下一行的皇后，
如果已经是最后一行，说明已经找到一个解，输出这个解，
然后最后一行的皇后的位置加1，继续尝试下一个解。

C代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>

int Queen(int queen_num);                                    //求解n皇后问题有多少种解的主要函数
int queen_check(int k,int *X);                               //判断是否和前面几个已放置好的皇后是否冲突的函数


int main()
{
    int queen_num;

    printf("please int the number of queen : \n");            //请用户输入皇后的个数
    scanf("%d",&queen_num);

    Queen(queen_num);

    return 0;

}


int queen_check(int k,int *X)
{
    int j;
    for (j = 1;j < k; j++){
        if((abs(k - j) == abs (X[j] - X[k])) || (X[j] == X[k]))  //两个判断条件，前者的意义为是否在同一对角线上，后者为是否在同一列
            return 0;
      }
    return 1;
}

int Queen(int queen_num)
{
    int *X;
    X = (int *)malloc((queen_num + 1) * sizeof(int));            //malloc申请一个一维数组，数组大小比皇后个数大一个，下标为0的不存，目的是为了存储，理解时方便
    int k = 1;
    int i = 0;
    int sum = 0;

    for(i = 0; i <= queen_num; i++){                         //初始置数组为0
    X[i] = 0;
    }

    while( k > 0  ){        //如果找到k<=0了，说明此问题再无解了，退出
        X[k] += 1;
        while((X[k] <= queen_num) && (queen_check(k,X) == 0)){   //一直找到第k个皇后的合适位置
            X[k] += 1;
                                     
        }
        if (X[k] <= queen_num){
            if ( k == queen_num ){
                sum++;             //此时得到一个可行解
                                                 
            }
            else{
                k++;
                X[k] = 0;    //将下一个皇后的初始位置定为0，再按要求进行排列
                                                                    
            }
                           
        }
        else{
            k--;          //当第k行一直找到n列，依然未找到合适的解，那便退回上一层再寻找
                                       
        }
    }
                 
    printf("%d\n",sum);
                      
    return 0;
}

感谢阅读，欢迎指正。

-------------本文结束感谢您的阅读-------------