八皇后问题学习笔记

 1.       问题描述&＃xff1a;

在n×n的棋盘上放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋中的一个问题。皇后是棋盘上最具杀伤力的一个棋子&＃xff0c;她可以捕捉与她在同一行&＃xff0c;或同一列&＃xff0c;或同一斜线&＃xff08;有两条&＃xff09;上的所有棋子。如下图所示&＃xff0c;红线经过的格子都会被皇后捕捉。

2.       问题分析&＃xff1a;

1)    皇后的杀伤力在她所对应的行&＃xff0c;列&＃xff0c;和两条斜线上&＃xff0c;所以应该满足该皇后所在的行、列和两条斜线都不存在其它皇后。

2)    所以为了避免皇后冲突&＃xff0c;一个可行的办法是将棋盘上所有的行&＃xff0c;列&＃xff0c;和斜线的占用状态分别用数组存起来&＃xff0c;初始状态为未占用。在每成功放入一个皇后以后&＃xff0c;将该皇后所对应的行&＃xff0c;列&＃xff0c;和两条斜线的状态更新为占用。在每次尝试将某个皇后放置到某个位置的时候&＃xff0c;需要检查该位置所对应的行&＃xff0c;列&＃xff0c;和斜线的占用状态&＃xff0c;只有全部未被占用&＃xff0c;才可以将该皇后放到该位置。

3)    接下来的问题有两个&＃xff1a;一是如何用数组来存储棋盘上所有的行&＃xff0c;列&＃xff0c;和斜线的占用状态&＃xff1f;二是对棋盘上每一个位置如何找到它所对应的行、列和斜线在状态数组中的位置。以下分行、列、左低右高斜线和左高右低斜线四种情况来讨论&＃xff1a;

4)    行&＃xff1a;对n×n的棋盘有n行&＃xff08;1 &＃xff5e; n&＃xff09;&＃xff0c;用一个n &＃43; 1维的数组row[n &＃43; 1]&＃xff08;row[0]不用&＃xff09;来表示每一行的占用状态。位置&＃xff08;i&＃xff0c;j&＃xff09;对应的行的占用状态为row[i]。

5)    列&＃xff1a;对n×n的棋盘有n列&＃xff08;1 &＃xff5e; n&＃xff09;&＃xff0c;用一个n &＃43; 1维的数组col[n &＃43; 1]&＃xff08;col[0]不用&＃xff09;来表示每一列的占用状态。位置&＃xff08;i&＃xff0c;j&＃xff09;对应的列的占用状态为col[j]。

6)    左低右高斜线&＃xff1a;n×n的棋盘总共有2n – 1条左低右高斜线&＃xff0c;所以可以用2n维的数组b[2n]&＃xff08;b[0]不用&＃xff09;来存储每一条左低右高斜线的占用状态。。对某一条斜线&＃xff0c;其特点是它所经过的每一个格子的&＃xff08;列号 &＃43; 行号&＃xff09;相等&＃xff0c;所以可以用这个值作为数组下标来唯一标记每一条左低右高斜线&＃xff0c;为了使下标从1开始&＃xff0c;对所有的下标减1。如下图所示。位置&＃xff08;i&＃xff0c;j&＃xff09;对应的左低右高斜线的占用状态为b[i &＃43; j – 1]。

7)    左高右低斜线&＃xff1a;n×n的棋盘总共有2n – 1条左高右低斜线&＃xff0c;所以可以用2n维的数组c[2n]&＃xff08;c[0]不用&＃xff09;来存储每一条左高右低斜线的占用状态。。对某一条斜线&＃xff0c;其特点是它所经过的每一个格子的&＃xff08;列号 – 行号&＃xff09;相等&＃xff0c;所以可以用这个值作为数组下标来唯一标记每一条左高右低斜线&＃xff0c;为了避免出现负值&＃xff0c;将所有的下标值都加上一个n。如下图所示。位置&＃xff08;i&＃xff0c;j&＃xff09;对应的左高右低斜线的占用状态为c[n &＃43; j - i]。

3.       解题思路&＃xff1a;

1)    要将n个皇后放到n×n的棋盘中&＃xff0c;则每一列必须且只能放一个皇后。所以问题转化为确定皇后在每一列中的位置&＃xff08;在第几行上&＃xff09;。

2)    从第一列开始&＃xff0c;依次考察每一列。

3)    在考察每一列的时候&＃xff0c;总是从第一行开始&＃xff0c;尝试将皇后放入&＃xff0c;如果可以放入&＃xff0c;就接着考察下一列的第一行。如果不可以放入&＃xff0c;就接着考察这一列的下一行&＃xff0c;直到成功&＃xff0c;然后接着考察下一列的第一行。

4)    如果这一列的每一行都不可以放入&＃xff0c;说明这一列前面各列的皇后放置有问题&＃xff0c;导致这一列无法放入&＃xff0c;需要回溯。

5)    回溯的时候&＃xff0c;如果前面的一列每一行都已经被尝试过了&＃xff0c;就需要接着往前回溯&＃xff0c;直到找到还有行未被尝试过的列&＃xff0c;然后尝试这一列的下一行。

6)    在回溯过程中经过的每一列都需要将已经放入的皇后取出来&＃xff0c;以备后面重新选择位置放入。

7)    如果每一列都被考察完毕&＃xff0c;即每一列中的皇后都找到了合适的位置&＃xff0c;则找到一个解。

8)    在找到一个解后&＃xff0c;如果还要寻找其它解&＃xff0c;则需要回溯&＃xff0c;尝试其它情况。

9)    当回溯到第0列时&＃xff0c;说明1 ~ n列的所有行都已经被尝试过了&＃xff0c;没有其它情况可以尝试&＃xff0c;结束程序。

4.       代码&＃xff1a;

Code
void QueenLayout(int n)
{
    int j;
    char next;    
    int* row &＃61; new int[n &＃43; 1]; //每一行的状态&＃xff08;是否已经被占用&＃xff1a;0 - 未被占用&＃xff0c;1 - 被占用&＃xff09;。
    int* col &＃61; new int[n &＃43; 1]; //皇后在每一列中的位置&＃xff08;行号&＃xff09;
    int* b &＃61; new int[2 * n]; //每一条正斜线&＃xff08;左低右高&＃xff09;的状态&＃xff08;是否已经被占用&＃xff1a;0 - 未被占用&＃xff0c;1 - 被占用&＃xff09;。
    int* c &＃61; new int[2 * n]; //每一条反斜线&＃xff08;左高右低&＃xff09;的状态&＃xff08;是否已经被占用&＃xff1a;0 - 未被占用&＃xff0c;1 - 被占用&＃xff09;。    
    bool occupied &＃61; false; //用于判断在每一列中放置皇后时&＃xff0c;她所对应的行和两条斜线&＃xff0c;是否至少有一条已经被占用。

    int m &＃61; 1; //当前被考察的列
    col[0] &＃61; col[1] &＃61; 1; //从第一列开始的第一行开始考察&＃xff0c;如果可以就考察第二列的第一行&＃xff0c;如果不可以就考察第一列的第二行&＃xff08;即col[1] &＃61; 2&＃xff09;

    //初始化所有的行为未被占用状态
    for (j &＃61; 0; j <&＃61; n; j&＃43;&＃43;)
    {
        row[j] &＃61; 0;
    }

    //初始化所有的斜线为未被占用状态
    for (j &＃61; 0; j < 2*n; j&＃43;&＃43;)
    {
        b[j] &＃61; c[j] &＃61; 0;
    }

    do
    {
        if (!occupied)
        {
            //已经考察到第n列&＃xff0c;所以一次考察完毕。
            if (m &＃61;&＃61; n)
            {
                //打印找到的一个解
                cout << "Column\tRow\n";
                for (j &＃61; 1; j <&＃61; n; j&＃43;&＃43;)
                {
                    printf("%3d\t%d\n", j, col[j]);
                }

                //是否接着寻找下一个解
                cout << "Find next solution? (Y/N)\n";
                cin >> next;
                if (next !&＃61; &＃39;Y&＃39; && next !&＃61; &＃39;y&＃39;)
                {
                    return;
                }

                //已经找到一个解&＃xff0c;回溯找下一个解。
                //一直回溯到还有行未被考察过的列
                while(col[m] &＃61;&＃61; n)
                {
                    m--;
                    //在回溯过程中经过的每一列都需要将已经放入的皇后取出来&＃xff0c;以备后面重新选择位置放入。
                    row[col[m]] &＃61; b[m &＃43; col[m] - 1] &＃61; c[n &＃43; m - col[m]] &＃61; 0;
                }
                //考察这一列的下一行
                col[m]&＃43;&＃43;;
            }
            else
            {
                //因为occupied&＃61;&＃61;false&＃xff0c;所以皇后可以被放在当前考察列的当前考察行
                //将该皇后对应的行和两条斜线置为被占用状态
                row[col[m]]&＃61;b[m &＃43; col[m] - 1] &＃61; c[n &＃43; m - col[m]] &＃61; 1;
                //考察下一列的第一行
                col[&＃43;&＃43;m] &＃61; 1;
            }
        }
        else
        {
            //因为occupied&＃61;&＃61;true&＃xff0c;所以皇后不可以被放在当前考察列的当前考察行
            //一直回溯到还有行未被考察过的列
            while(col[m] &＃61;&＃61; n)
            {
                m--;
                //在回溯过程中经过的每一列都需要将已经放入的皇后取出来&＃xff0c;以备后面重新选择位置放入。
                row[col[m]] &＃61; b[m&＃43;col[m] - 1] &＃61; c[n &＃43; m - col[m]] &＃61; 0;
            }
            //考察这一列的下一行
            col[m]&＃43;&＃43;;
        }
        //考察皇后是否可以被放在当前考察列的当前考察行&＃xff0c;即她对应的行和两条斜线是否全部未被占用
        occupied &＃61; row[col[m]] || b[m &＃43; col[m] - 1] || c[n &＃43; m -col[m]];
    }while (m !&＃61; 0);//退到m &＃61;&＃61; 0, 表示 1 ~ n 列的所有行都被考察过了&＃xff0c;即考察过了所有可能的情况&＃xff0c;整个考察过程结束。

    delete []row;
    delete []col;
    delete []b;
    delete []c;    
}