N皇后问题

起因

OJ上放了去年的期中考试题，其中有一题2n皇后困扰了我很久
由于还没学过数据结构，很多方法都看不懂
好不容易写了一个正确的程序，但是效率太低了，交上去果真是time limit exceeded
昨天晚上做n皇后时想到了一个方法，减少了很多不必要的操作
虽然效率仍不是很高，好歹把OJ过了，简单记录一下

题目与题解

N皇后

  • N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后
  • 要求:任何两个皇后不同行，不同列也不再同一条斜线上
  • 求给一个整数 n ，返回 n 皇后的摆法数。
  • 例如:8皇后摆法92
    我的思路:构造一个nXn的数组，里面包含0和1，1的位置代表可以放皇后，2的位置代表不可以
    当放上一个新的皇后时，就将她的横向，纵向，斜向置零，再将这个数组传到下一层
    如果一直放到了最后一个棋子，就得到了一个解
    要注意的是，应该记录下各个状态下的棋盘状态，因为对数组进行操作时会改变原值
    因此，新定义了一个b数组，用来拷贝a
    在遍历整个棋盘时，会产生同解(皇后的排列)，所以要除以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
      
    #include<iostream>
    using namespace std;
    int sum = 0;
    void find(int a[][10], int n, int now)
    {
        int b[10][10];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (a[i][j])//查找所有可以放queen的地方
                {
                    if (now == n)//这是最后一个queen
                        ++sum;//方法+1
                    else
                    {
                        for (int p = 0; p < n; ++p)
                            for (int q = 0; q < n; ++q)
                                b[p][q] = a[p][q];
                        for (int p = 0; p < n; ++p)
                                b[p][j] = 0;
                        for (int q = 0; q < n; ++q)
                                b[i][q] = 0;
                        for (int p = i, q = j; p >= 0 && q >= 0; --p, --q)
                                b[p][q] = 0;
                        for (int p = i, q = j; p < n && q < n; ++p, ++q)
                                b[p][q] = 0;
                        for (int p = i, q = j; p >= 0 && q < n; --p, ++q)
                                b[p][q] = 0;
                        for (int p = i, q = j; p < n && q >= 0; ++p, --q)
                                b[p][q] = 0;
                        find(b, n, now+1);
                    }
                }
    }
    int main()
    {
        int n, a[10][10], solve;
        while (cin >> n)//循环输入n，输出结果
        {
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    a[i][j] = 1;
            find(a, n, 1);
            solve = sum;
            for (int i = 1; i <= n; i++)
                solve /= i;//除以i!
            cout << solve << endl;
            sum = 0;
        }
        return 0;
    }
    经过测试数据的检验，这种方法最多只能算到8皇后(此时已要10s左右)
    所以我尝试对它进行改进
  • 改进思路:由于是在n*n上放n个皇后，可知必定每行各有一个，每列各有一个
  • 因此，不需要每次都遍历整个数组，而是只遍历一行即可
  • 第now个棋子就放在第now行(下标now-1)
  • 也只需要对now行以下的元素进行拷贝和赋值
  • 同时，逐行放置已经确定了顺序，就不会产生同解了，不必除以阶乘
    代码实现
    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
      
    #include<iostream>
    using namespace std;
    int sum = 0;
    void find(int a[][20], int n, int now)
    {
        int b[20][20],i=now-1;
        for (int p = 0; p < n; ++p)
            for (int q = 0; q < n; ++q)
                b[p][q] = a[p][q];
        for (int j = 0; j < n; ++j)
            if (a[i][j])//查找所有可以放queen的地方
            {
                if (now == n)//这是最后一个queen
                    ++sum;//方法+1
                else//只对该行下面的进行拷贝和赋值
                {
                    for (int p = i; p < n; ++p)
                        for (int q = 0; q < n; ++q)
                            b[p][q] = a[p][q];
                    for (int p = i; p < n; ++p)
                        b[p][j] = 0;
                    for (int q = 0; q < n; ++q)
                        b[i][q] = 0;
                    for (int p = i, q = j; p < n && q < n; ++p, ++q)
                        b[p][q] = 0;
                    for (int p = i, q = j; p < n && q >= 0; ++p, --q)
                        b[p][q] = 0;
                    find(b, n, now + 1);
                }
            }
    }
    int main()
    {
        int n, a[20][20], solve;
        while (cin >> n)//循环输入n，输出结果
        {
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    a[i][j] = 1;
            find(a, n, 1);
            cout << sum << endl;
            sum = 0;
        }
        return 0;
    }
    经过改进，这种算法可以算到14皇后
    学习数据结构之后，应该可以实现更优的解法
    此算法在力扣上的结果
    n皇后时间
    4.8更新
  • 由于我们发现皇后是逐行摆放的，可以抛弃掉行，转而用一个一维数组表示
  • 它的下标就是行坐标，储存着的就是列坐标
    代码实现 
    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
    #include<iostream>
    using namespace std;
    int sum = 0;
    void find(int a[], int n, int now)
    {
        for (int j = 0; j < n; j++)
        {
            bool flag=true;
            for (int i = 0; i < now - 1; i++)
                if (j == a[i] || (j - a[i] == now - 1 - i) || (j - a[i] == i - now + 1))
                {
                    flag = false;
                    break;
                }
            if (flag)
            {
                if (now == n)
                    ++sum;
                else
                {
                    a[now - 1] = j;
                    find(a, n, now + 1);
                }
            }
        }
    }
    int main()
    {
        int n, a[20];
        while (cin >> n)
        {
            find(a, n, 1);
            cout << sum << endl;
            sum = 0;
        }
        return 0;
    }
    上面两种算法用时对比
    用时对比
    力扣提交结果
    可以看到，下面的方法用时仅为上面的1/3

    2N皇后问题

    题目描述
    2n皇后问题，实际上可以看成是两次n皇后问题的叠加
    只要先放一类皇后，再将已经放置的棋子位置置零，作为另一类皇后的输入即可
    不过有一点要注意:要把一色皇后置零的位置恢复到初始状态，又要与输入的初始0位置区分
    我的方法是: 1代表可以放置，0代表初始限制，2代表红/白棋子，3代表因新放棋子而不能放置的地方
    依靠上述第一种方法的代码实现
    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
        
    //time limited exceed
    #include<iostream>
    using namespace std;
    int sum = 0;
    void find( int a[][10], int n,int now)
    //1代表可以放置，0代表初始限制，2代表红/白棋子，3代表因新放棋子而不能放置的地方
    {
        int b[10][10];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (a[i][j]==1)//查找所有可以放queen的地方
                {
                    if (now == 2*n)//这是最后一个queen
                        ++sum;//方法+1
                    else
                    {
                        for (int p = 0; p < n; ++p)
                            for (int q = 0; q < n; ++q)
                                b[p][q] = a[p][q];
                        b[i][j] = 2;
                        for (int p = 0; p < n; ++p)
                            if(b[p][j]==1)
                                b[p][j] = 3;
                        for (int q = 0; q < n; ++q)
                            if(b[i][q]==1)
                                b[i][q] = 3;
                        for (int p = i, q = j; p >= 0 && q >= 0; --p, --q)
                            if(b[p][q]==1)
                                b[p][q] = 3;
                        for (int p = i, q = j; p < n && q < n; ++p, ++q)
                            if (b[p][q] ==1)
                                b[p][q] = 3;
                        for (int p = i, q = j; p >= 0 && q < n; --p, ++q)
                            if (b[p][q] == 1)
                                b[p][q] = 3;
                        for (int p = i, q = j; p < n && q >= 0; ++p, --q)
                            if (b[p][q] == 1)
                                b[p][q] = 3;
                        if (now == n)//这是最后一个红皇后
                        {
                            for (int p = 0; p < n; ++p)
                                for (int q = 0; q < n; ++q)
                                    if (b[p][q] == 3)
                                        b[p][q] = 1;
                                    else if (b[p][q] == 2)
                                        b[p][q] = 3;
                        }
                        find(b, n,now+1);
                    }
                }
    }
    int main()
    {
        int n, a[10][10], solve;
        cin >> n;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
        find(a, n, 1);
        solve = sum;
        for (int i = 1; i <= n; i++)
            solve /= (i*i);//除以i!^2，这是两类棋子的排列
        cout << solve << endl;
    }
    OJ的运行时间达到了1996ms，超时了😵😵😵
    不过也可以理解，毕竟在本地运行时，到达7阶就已经很难算出来了
    依靠上述第二种方法的代码改进
    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
      
    //time limited exceed
    #include<iostream>
    using namespace std;
    int sum = 0;
    void find(int a[][10], int n, int now)
    //1代表可以放置，0代表初始限制，2代表红/白棋子，3代表因新放棋子而不能放置的地方
    {
        int b[10][10],i;
        for (int p = 0; p < n; ++p)
            for (int q = 0; q < n; ++q)
                b[p][q] = a[p][q];
        if (now <= n)
            i = now - 1;
        else
            i = now - n - 1;
        for (int j = 0; j < n; ++j)
            if (a[i][j] == 1)//查找所有可以放queen的地方
            {
                if (now == 2 * n)//这是最后一个queen
                    ++sum;//方法+1
                else
                {
                    for (int p = i; p < n; ++p)
                        for (int q = 0; q < n; ++q)
                            b[p][q] = a[p][q];
                    b[i][j] = 2;
                    for (int p = i; p < n; ++p)
                        if (b[p][j] == 1)
                            b[p][j] = 3;
                    for (int q = 0; q < n; ++q)
                        if (b[i][q] == 1)
                            b[i][q] = 3;
                    for (int p = i, q = j; p < n && q < n; ++p, ++q)
                        if (b[p][q] == 1)
                            b[p][q] = 3;
                    for (int p = i, q = j; p < n && q >= 0; ++p, --q)
                        if (b[p][q] == 1)
                            b[p][q] = 3;
                    if (now == n)//这是最后一个红皇后
                    {
                        for (int p = 0; p < n; ++p)
                            for (int q = 0; q < n; ++q)
                                if (b[p][q] == 3)
                                    b[p][q] = 1;
                                else if (b[p][q] == 2)
                                    b[p][q] = 3;
                    }
                    find(b, n, now + 1);
                }
            }
    }
    int main()
    {
        int n, a[10][10];
        cin >> n;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
        find(a, n, 1);
        cout << sum << endl;
    }
    OJ用时21ms，有了很大提升，不过还是有不小的改进空间
    这就是后话了😁😁