经典回溯算法之n皇后问题

素颜马尾好姑娘i 2022-06-07 00:24 239阅读 0赞

这是**来源**于国际象棋的一个问题。n皇后问题要求在一个n×n格的棋盘上放置n个皇后，使得它们彼此不受攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一条斜线上的其他任何棋子。因此，n后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。

**求解过程**从空棋盘开始，设在第1行至第m行都已经正确放置了m个皇后，再在第m+1个行上找合适的位置放第m+1个皇后，直到在第n行也找到合适的位置放置第n个皇后，就找到了一个解。接着改变第n行上皇后的位置，希望获得下一个解。另外，在任一行上有n种可选的位置。开始时，位置在第1列，以后改变时，顺次选择第2列、第3列、....... 、第n列。当第n列也不是一个合理的位置时，就要回溯，去改变前一行的位置。

回溯法**解题步骤**：

（1）针对所给问题，定义问题的解空间。

（2）确定易于搜索的解空间结构。

（3）以深度优先的方式搜索解空间。

回溯法求解4皇后问题的搜索过程如下图所示：

![20170930162223618][]

很显然，由上述搜索过程我们可以看出第i个皇后一定在第i行上，所以我们可以利用一个数组来保存每一个皇后所在的列。

**C\#版代码**如下：

private void button1_Click(object sender, EventArgs e)
            {
                int n =8;  //皇后的个数
                N_Queen(n);
            }
    
            public Boolean Place(int[] Column, int index)
            {          
                for (int i = 1; i < index; i++)
                {   //当两个皇后所在列的差值等于所在行的差值时，表明两个皇后在同一斜线上
                    int Colunm_differ = System.Math.Abs(Column[index] - Column[i]);  //两个皇后所在列的差
                    int Row_differ = System.Math.Abs(index - i);  //两个皇后所在行的差
                    if (Column [i]==Column [index ] || Colunm_differ==Row_differ  ) //有皇后与其在同列或同一斜线上
                    {
                        return false ;
                    }
                }
                return true ;  //没有皇后与其同行、同列、同对角线
            }
    
            public void N_Queen(int n)
            {
                int[] Column_Num = new int[n + 1];
                int index = 1;  //index是当前行，初值为1，从第1个皇后开始放置          
                int answer_num = 0;  //记录n皇后问题解的个数
    
                //其实是为了初始化各皇后的位置，可以不写：
                //for (i = 1; i <= n; i++)
                //{
                //    Column_Num[i] = 0;
                //}
    
                while (index > 0)
                {
                    Column_Num[index]++;
                    while (Column_Num[index] <= n && !Place(Column_Num, index)) //寻找皇后的位置
                    {
                        Column_Num[index]++;  //移到下一列
                    }
                    if (Column_Num[index] <= n)
                    {
                        if (index == n)  //n个皇后全部放置完毕
                        {
                            answer_num++;
    
                            //输出每一种方案的结果：
                            txt1.Text = txt1.Text + "\r\n" + "方案" + answer_num;
                            for (int i = 1; i <= n; i++)
                            {
                                txt1.Text = txt1.Text +"  "+ "(" + i + "," + Column_Num[i] + ")"; //（皇后i，位置）
                            }
    
                            //继续寻找另一种方案：以下三种均可以
                            index--;
    
                            //或者：
                            //Column_Num[index] += n;
    
                            //又或者：
                            //for (int i = 1; i < n; i++)
                            //{
                            //    Column_Num[index]++;
                            //}
                        }
                        else  //继续寻找下一个皇后的位置
                        {
                            index++;
                            Column_Num[index] = 0;
                        }
                    }
                    else
                    {
                        index--;  //当前皇后无法放置，回溯至上一个皇后
                    }
                }           
            }

当n=8时，得到的所有的方案如下图（不考虑对称性）：

![20170930182449402][]

当n持续增大时，我试了试n=15，发现时间复杂度已经超出我的心里预期，最终没等它继续执行下去。

感谢您的阅读~

[20170930162223618]: /images/20220607/7c7c39fea029454d86aed926fb3b3345.png
[20170930182449402]: /images/20220607/13615b2299394f558d2f2c7ddfa8cf7e.png