题解：N皇后问题

Guderian出品

说明

n皇后问题描述为：在一个$n \times n$的棋盘上摆放$n$个皇后，要求任意两个皇后不能冲突，即任意两个皇后不再同一行、同一列、同一斜线上。

分析

算法设计策略：回溯法

将第$i$个皇后摆放在第$i$行，$i$从$1$开始，每个皇后都从第$1$列开始尝试。尝试时判断再该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后；如果有冲突，则考虑下一列。

如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后，以此类推，直到找到所有合理的摆放方案。

实现

解法一 新手回溯：朴素算法

（1）常量和变量说明

• n：皇后数，棋盘规模为$n\times n$
• queen[]：皇后的摆放位置数组，queen[i]表示第$i$个皇后的位置，1<=queen[i]<=n

（2）C语言程序

#include<stdio.h>
#include<math.h>
#define n 4
int queen[n+1];

void Show()                 //输出所有皇后摆放方案
{ 
    printf("(");
    for(int i = 1; i <= n; i++)
        printf(" %d", queen[i]);
    printf(")\n");
}

int Place(int j)            //检查当前列能否放置皇后，不能返回0，能返回1
{ 
    for(int i = 1; i < j; i++)  //检查与已经摆放的皇后是否在通一列或者同一斜线上
        if(queen[i] == queen[j] || fabs(queen[i]-queen[j]) == (j - i))
            return 0;
    return 1;
}

void Nqueen(int j)
{
    for(int i = 1; i <= n; i++)
    {
        queen[j] = i;
        if(Place(j))
            if(j == n)      //如果所有皇后都摆放好，则输出当前摆放方案
                Show();
            else            //否则继续摆放下一个皇后
                Nqueen(j + 1);
    }
}

int main()
{
    Nqueen(1);
    return 0;
}

（3）复杂度分析

• 时间复杂度：$O(n!)$到$O(n^n)$
• 空间复杂度：$O( n )$

解法二 优化回溯：记忆化搜索

（1）常量和变量说明

• column[]：标记数组，对于第$i$列，column[i]为$0$说明没有皇后，为$1$说明有皇后
• diagonal1[]：标记数组，对于第$i$条主对角线，diagonal1[]为$0$说明没有皇后，为$1$说明有皇后
• diagonal2[]：标记数组，对于第$i$条次对角线，diagonal2[]为$0$说明没有皇后，为$1$说明有皇后

（2）C语言程序

#include<stdio.h>
#include<math.h>
#define n 4
int queen[n+1],column[n+1],diagonal1[2*n+1],diagonal2[2*n+1]; //设置标记，回溯时不用枚举queen[]

void Show()
{ 
    printf("(");
    for(int i = 1; i <= n; i++)
        printf(" %d", queen[i]);
    printf(")\n");
}

void Nqueen(int j)
{
    for(int i = 1; i <= n; i++)
        if(column[i] + diagonal1[i - j + n] + diagonal2[i + j] == 0)
        {
            queen[j] = i;
            column[i] = 1, diagonal1[i - j + n] = 1, diagonal2[i + j] = 1;
            if(j < n) 
                Nqueen(j + 1);
            else
                Show();
            column[i] = 0, diagonal1[i - j + n] = 0, diagonal2[i + j] = 0;
        }
}

int main()
{
    Nqueen(1);
    return 0;
}

（3）复杂度分析

• 时间复杂度：不超过$O(n!)$
• 空间复杂度：$O( n )$

对比

当$n$较小时，解法二比解法一快至少$20$倍。