百万皇后问题

4月11日 · 2018年

百万皇后

数据结构定义

300万皇后问题的算法
参考了Rok sosicJun GuPolynomial Time Algorithms for the N-Queen Problem中的QS算法

百万皇后的主要思想

随机地生成一张摆放
取出可以相互攻击的皇后,然后任意取出一个皇后,看看他们交换是不是可以减少冲突
如果可以,交换,否则,不交换

数据存放的形式

i行的皇后放在第queen[i]
i遍历0~n-1,保证了每一行只有1个皇后,所以不会存在行的冲突
queen[i]列是一个[0..n-1]的序列
如果保证这个序列不重不漏,那么每一列也就只有1个皇后,所以不会存在列的冲突
另外,如果保证在每次交换的过程中,第i行的皇后和第j行的皇后交换,指的是他们的列交换,所以行和列都还是不重不漏的[0..n-1]的序列
于是只要每次维护正反对角线是不是有冲突就可以了

变量声明

rand()范围太小,要超大规模随机数,所以要这个,注意这个是unsigned long long int,所以要强制类型转换成int

typedef std::subtract_with_carry_engine<std::uint_fast64_t, 48, 5, 12> ranlux48_base;

n表示皇后数量

int n;

queen[i]表示第i行的皇后在第几列

int queen[MAXN];

表示哪些皇后是可以相互攻击的

attack[MAXN];

正反对角线的冲突数量

int diagonalNegative[2 * MAXN + 7];
int diagonalPositive[2 * MAXN + 7];

总冲突数

int collisions;

记录某一列是不是已经放了东西了,这保证[0..n-1]序列不重不漏,所以列一定不会有冲突

bool columnUsed[MAXN] = {false};

函数声明

/**
 * 想在第row行第col列放皇后,检查这个皇后是不是和以前放的有冲突
 * @param row 行数
 * @param col 列数
 * @return 如果没有冲突,返回true,否则,false
 */
bool check(int row, int col)
/**
 * 随机生成一个棋盘布局
 */
void generateARadomPermutation()
/**
 * 执行交换给定两行的皇后
 * @param i 第i行
 * @param j 第j行
 */
void performSwap(int i, int j)
/**
 * 检查交换给定的两个皇后会不会减少冲突数
 * @param i 第i行
 * @param j 第j行
 * @return 交换后的冲突数的变化量,小于0表示冲突减少
 */
int swapWillReduceCollisions(int i, int j)
/**
 * 计算冲突
 * @return 冲突数量
 */
int computeCollisions()
/**
 * 获得能够相互攻击的皇后的编号
 * @return 能够相互攻击的皇后的个数
 */
int computeAttacks()

算法描述

随机地生成一张摆放
取出可以相互攻击的皇后,然后任意取出一个皇后,看看他们交换是不是可以减少冲突
如果可以,交换,否则,不交换

优化细节

  • 前THRESHOLD行要保证没有冲突
    这是为了减少collision的数量
    尽可能加速程序运行
    这里的THRESHOLD参考了几篇论文,最终定在5/12
    放下去之前要check
  • check不能每次遍历比较
    直接看对角线数组是不是为0
  • 检查交换给定的两个皇后会不会减少冲突数
    计算的结果用delta表示变化量
    一方面可以用delta的正负来表示是不是交换了更好
    另一个是可以在更新collision的时候直接加上delta就好了
    还有一个就是避免修改了对角线数组以后发现不是交换以后更好再重新恢复
  • 容斥原理,如果正好是同一条对角线,要去掉重复计算的那个
  • 冲突数按照C_n^2计算,而不是有x个皇后计算x-1个冲突
    那样的话每次冲突减少的都是没几个,一个两个,三个五个
  • 能够相互攻击的皇后数量不等于冲突数量
  • n要求为正整数,n=2和n=3无解,所以直接判断掉了
  • 计算一个阈值
    当冲突小于阈值的时候重新计算attack数组
    这里的常系数定义参考了Rok sosicJun Gu的QS2算法的定义
    $$C_1取0.53$$
  • 最大化N较小的时候的运行速度
    对较大的N没有影响
    这里的常系数定义参考了Rok sosicJun Gu的QS2算法的定义
    $$C_2取32$$

算法框图

可以得到如下的流程图

代码实现

#include <bits/stdc++.h>

#define MAXN 5000007

using namespace std;

// rand()范围太小,要超大规模随机数,所以要这个,注意这个是unsigned long long int,所以要强制类型转换成int
typedef std::subtract_with_carry_engine<std::uint_fast64_t, 48, 5, 12> ranlux48_base;

// n表示皇后数量
int n;

// queen[i]表示第i行的皇后在第几列
int queen[MAXN];

// 表示哪些皇后是可以相互攻击的
int attack[MAXN];

// 正反对角线的冲突数量
int diagonalNegative[2 * MAXN + 7];
int diagonalPositive[2 * MAXN + 7];

// 总冲突数
int collisions;

// 记录某一列是不是已经放了东西了,这保证[0..n-1]序列不重不漏,所以列一定不会有冲突
bool columnUsed[MAXN] = {false};

/**
 * 想在第row行第col列放皇后,检查这个皇后是不是和以前放的有冲突
 * @param row 行数
 * @param col 列数
 * @return 如果没有冲突,返回true,否则,false
 */
bool check(int row, int col) {
    int negativeIndex = row + col;
    int positiveIndex = row - col;
    return (diagonalNegative[negativeIndex] == 0 && diagonalPositive[n - 1 + positiveIndex] == 0);
}

/**
 * 随机生成一个棋盘布局
 */
void generateARadomPermutation() {
    ranlux48_base rb;
    // 前THRESHOLD行要保证没有冲突,这是为了减少collision的数量,尽可能加速程序运行,这里的THRESHOLD参考了几篇论文,最终定在5/12
    const int THRESHOLD = (int) (5.0 / 12.0 * n);
    int generatedQueenNumber = 0;
    memset(diagonalPositive, 0, 2 * n * sizeof(int));
    memset(diagonalNegative, 0, 2 * n * sizeof(int));

    while (generatedQueenNumber < n) {
        int col;

        do {
            col = (int) (rb() % n);
        } while (columnUsed[col]);

        // 前面5/12行是没有冲突的,所以放下去之前要check
        if (generatedQueenNumber < THRESHOLD)
            if (check(generatedQueenNumber, col) == false) { continue; }

        queen[generatedQueenNumber] = col;
        columnUsed[col] = true;
        int negativeIndex = generatedQueenNumber + col;
        ++diagonalNegative[negativeIndex];
        int positiveIndex = generatedQueenNumber - col;
        ++diagonalPositive[n - 1 + positiveIndex];
        ++generatedQueenNumber;
    }
}

/**
 * 执行交换给定两行的皇后
 * @param i 第i行
 * @param j 第j行
 */
void performSwap(int i, int j) {
    // 首先更新对角线的冲突数组,减去原来的冲突数
    --diagonalNegative[i + queen[i]];
    --diagonalNegative[j + queen[j]];
    --diagonalPositive[n - 1 + i - queen[i]];
    --diagonalPositive[n - 1 + j - queen[j]];
    // 交换皇后
    int tmp = queen[i];
    queen[i] = queen[j];
    queen[j] = tmp;
    // 把交换后增加的冲突加入到对角线冲突数组
    ++diagonalNegative[i + queen[i]];
    ++diagonalNegative[j + queen[j]];
    ++diagonalPositive[n - 1 + i - queen[i]];
    ++diagonalPositive[n - 1 + j - queen[j]];
}

/**
 * 检查交换给定的两个皇后会不会减少冲突数
 * @param i 第i行
 * @param j 第j行
 * @return 交换后的冲突数的变化量,小于0表示冲突减少
 */
int swapWillReduceCollisions(int i, int j) {
    int delta = 0;
    // 计算原来正反对角线的冲突量,交换后会使得这些冲突减少
    delta -= diagonalNegative[i + queen[i]] - 1;
    delta -= diagonalNegative[j + queen[j]] - 1;

    // 容斥原理,如果正好是同一条对角线,要去掉重复计算的那个
    if (i + queen[i] == j + queen[j]) {
        ++delta;
    }

    delta -= diagonalPositive[n - 1 + i - queen[i]] - 1;
    delta -= diagonalPositive[n - 1 + j - queen[j]] - 1;

    if (i - queen[i] == j - queen[j]) {
        ++delta;
    }

    //计算新对角线的冲突量,交换后的新位置将会额外增加这些冲突
    delta += diagonalNegative[i + queen[j]];
    delta += diagonalNegative[j + queen[i]];

    if (i + queen[j] == j + queen[i]) {
        ++delta;
    }

    delta += diagonalPositive[n - 1 + i - queen[j]];
    delta += diagonalPositive[n - 1 + j - queen[i]];

    if (i - queen[j] == j - queen[i]) {
        ++delta;
    }

    return delta;
}

/**
 * 计算冲突
 * @return 冲突数量
 */
int computeCollisions() {
    int collisions = 0;

    // 遍历对角线数组计算冲突数量
    for (int i = 0; i < 2 * n - 1; ++i) {
        collisions += diagonalNegative[i] * (diagonalNegative[i] - 1) / 2;
        collisions += diagonalPositive[i] * (diagonalPositive[i] - 1) / 2;
    }

    return collisions;
}

/**
 * 获得能够相互攻击的皇后的编号
 * @return 能够相互攻击的皇后的个数
 */
int computeAttacks() {
    /*
     * 注:能够相互攻击的皇后数量不等于冲突数量
     */
    memset(attack, 0, n * sizeof(int));
    int numberOfAttacks = 0;

    for (int i = 0; i < n; ++i) {
        int negativeIndex = i + queen[i];
        int positiveIndex = i - queen[i];

        // 如果某皇后所在对角线有其他皇后,那就是可以攻击的,计数器加1,并记录这是第几个皇后
        if (diagonalNegative[negativeIndex] > 1 || diagonalPositive[n - 1 + positiveIndex] > 1) {
            attack[numberOfAttacks] = i;
            ++numberOfAttacks;
        }
    }

    return numberOfAttacks;
}


int main() {
    ranlux48_base rb;
    cin >> n;

    if (n <= 0 || n == 2 || n == 3) {
        // n要求为正整数,n=2和n=3无解,所以直接判断掉了
        cout << "No solution." << endl;

    } else {
        int beginTime = clock();
        // C1是为了计算一个阈值,当冲突小于阈值的时候重新计算attack数组,这里的常系数定义参考了Rok sosic和Jun Gu的QS2算法的定义,C1取0.53
        const double C1 = 0.45;
        // C2是为了最大化N较小的时候的运行速度,对较大的N没有影响,这里的常系数定义参考了Rok sosic和Jun Gu的QS2算法的定义,C2取32
        const double C2 = 32;

        do {
            generateARadomPermutation();
            collisions = computeCollisions();
            int limit = (int) (C1 * collisions);
            int numberOfAttacks = computeAttacks();
            int loopCount = 0;

            do {
                if (collisions == 0) {
                    break;
                }

                // 只遍历能够相互攻击的皇后
                for (int k = 0; k < numberOfAttacks; ++k) {
                    // 找到一个具有攻击性的皇后,再随机地找一个和自己不一样的皇后
                    int i = attack[k];
                    int j;

                    do {
                        j = (int) (rb() % n);
                    } while (i == j);

                    int delta;

                    // 如果交换后的冲突是减小的,执行交换
                    if ((delta = swapWillReduceCollisions(i, j)) < 0) {
                        // 更新冲突数,并执行交换
                        collisions += delta;
                        performSwap(i, j);

                        // 冲突数为0,找到解,输出,冲突数小于阈值,重新计算阈值和attack数组
                        if (collisions == 0) {
                            break;
                        }

                        if (collisions < limit) {
                            limit = (int) (C1 * collisions);
                            numberOfAttacks = computeAttacks();
                        }
                    }
                }

                loopCount += numberOfAttacks;
            } while (loopCount <= C2 * n);
        } while (collisions != 0);

        int endTime = clock();
        // 输出
        // for (int i = 0; i < n; ++i)  printf("(%d, %d)\n", i, queen[i]);
        // 输出耗费的时间
        printf("Time cost: %f second(s).\n", (double) (endTime - beginTime) / CLOCKS_PER_SEC);
    }

    return 0;
}

3 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定
  1. 陆 轩韬2018-4-11 · 21:06

    行数显示有问题

    • jxtxzzw2018-4-11 · 22:12

      并没有看出哪里有问题

      • jxtxzzw2018-4-16 · 14:02

        我知道了,屏幕缩小以后,三位数显示不下,就会被挤到下一行,不影响使用,以后空了再修复吧