八皇后问题

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。而且仅当 n = 1 或 n ≥ 4 时问题有解。

image
image
image

历史发展

  • 1848年，国际象棋作曲家马克斯·贝泽尔发表了八个皇后拼图。
  • 弗朗茨·瑙克在1850年发表了第一个解决方案。瑙克还将这个拼图延伸到n皇后问题，其中n个皇后位于n×n个方格的棋盘上。此后，包括卡尔弗里德里希高斯在内的许多数学家都参与了八个皇后拼图和其广义的n-queens版本。
  • 1874年，S.冈瑟提出了一种使用决定因素来寻找解决方案的方法。 JWL Glaisher改进了Gunther的方法。
  • 1972年，Edsger Dijkstra用这个问题来说明他称之为结构化编程的力量。他发表了深度优先 回溯算法的高度详细的描述。

分析

这是典型的回溯算法.从根结点开始,依次遍历所有的结点,若有一个节点错误，则说明该路径走不通，返回上一节点，以此类推，直到遍历所有节点。

针对这一类的回溯问题，有以下步骤：

  • 定义一个解空间，该解空间至少包含一个问题的解；
  • 组织解空间；
  • 按深度优先的遍历方法进行节点搜索，在搜索执行的同时产生解空间。

解题思路

  1. 要将n个皇后放到n×n的棋盘中，则每一列必须且只能放一个皇后。所以问题转化为确定皇后在每一列中的位置（在第几行上）。
  2. 从第一列开始，依次考察每一列。
  3. 在考察每一列的时候，总是从第一行开始，尝试将皇后放入，如果可以放入，就接着考察下一列的第一行。如果不可以放入，就接着考察这一列的下一行，直到成功，然后接着考察下一列的第一行。
  4. 如果这一列的每一行都不可以放入，说明这一列前面各列的皇后放置有问题，导致这一列无法放入，需要回溯。
  5. 回溯的时候，如果前面的一列每一行都已经被尝试过了，就需要接着往前回溯，直到找到还有行未被尝试过的列，然后尝试这一列的下一行。
  6. 在回溯过程中经过的每一列都需要将已经放入的皇后取出来，以备后面重新选择位置放入。
  7. 如果每一列都被考察完毕，即每一列中的皇后都找到了合适的位置，则找到一个解。
  8. 在找到一个解后，如果还要寻找其它解，则需要回溯，尝试其它情况。
  9. 当回溯到第0列时，说明1~n列的所有行都已经被尝试过了，没有其它情况可以尝试，结束程序。

代码实现

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
c语言:
    #include <stdio.h>  
    #include <stdlib.h>  

    #define max 8  

    int queen[max], sum=0; /* max为棋盘最大坐标 */  

    void show() /* 输出所有皇后的坐标 */  
    {  
        int i;  
        for(i = 0; i < max; i++)  
        {  
             printf("(%d,%d) ", i, queen[i]);  
        }  
        printf("\n");  
        sum++;  
    }  

    int check(int n) /* 检查当前列能否放置皇后 */  
    {  
        int i;  
        for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */  
        {  
            if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))  
            {  
                return 1;  
            }  
        }  
        return 0;  
    }  

    void put(int n) /* 回溯尝试皇后位置,n为横坐标 */  
    {  
        int i;  
        for(i = 0; i < max; i++)  
        {         
            queen[n] = i; /* 将皇后摆到当前循环到的位置 */  
            if(!check(n))  
            {             
                if(n == max - 1)  
                {  
                    show(); /* 如果全部摆好，则输出所有皇后的坐标 */  
                }           
                else  
                {  
                    put(n + 1); /* 否则继续摆放下一个皇后 */  
                }  
            }  
        }  
    }  

    int main()  
    {  
        put(0); /* 从横坐标为0开始依次尝试 */  
        printf("%d", sum);  
        return 0;  
    }

八皇后问题历来被研究已久，本文档只介绍了用回溯思想解体的方法，网上还有更多的研究资料和优化算法，感兴趣的同学可以深入学习。