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的阶乘
代码实现

  
#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行以下的元素进行拷贝和赋值
同时，逐行放置已经确定了顺序，就不会产生同解了，不必除以阶乘
代码实现

  
#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更新

由于我们发现皇后是逐行摆放的，可以抛弃掉行，转而用一个一维数组表示
它的下标就是行坐标，储存着的就是列坐标
代码实现

#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代表因新放棋子而不能放置的地方
依靠上述第一种方法的代码实现

    
//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阶就已经很难算出来了
依靠上述第二种方法的代码改进

  
//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，有了很大提升，不过还是有不小的改进空间
这就是后话了😁😁