算法分析与设计►未分类

n-Queens

  • 问题来源
  • 问题简介

    在一个n * n的格子里放置n个皇后，要求每任意两个皇后都不能处于同一行、同一列或者对角线上（45度或者135度）。返回总共有多少种排法。

解题思路


从第一行到最后一行，每次从第一个到最后一个，都尝试放置一个皇后，若符合要求，则计数加一。那么有如下问题：如何判断某个位置是否可以放置一个皇后?

  • 每放置一个皇后就对以前放置过的皇后进行逐一检查

  • 设置状态位，定义每一行，每一列，每一斜线上的格子是否可放置

    • 如何设置以皇后为基点的斜线为不可放置状态
      若两点(i1, j1)、(i2, j2)满足 i1 + j1 == i2 + j2，或 j1 - i1 == j2 - i2，则两点处于同一条斜线上（45度或135度）




时间复杂度 空间复杂度
… …

Code

#include <iostream>
#include <stack>
#include <vector>
#include <functional>
using namespace std;
class Solution {
private:
    bool *flag;
    int count;
    void solve(int row, int col, int n) {
        if (row == n - 1) {
            count++;
            return;
        }
        flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = false;
        row++;
        for (int i = 0; i < n; i++) {
            if (flag[i] && flag[n + row + i] && flag[4 * n - 2 + i - row]) {
                solve(row, i, n);
            }
        }
        row--;
        flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = true;
    }
public:
    Solution() { flag = nullptr; }
    ~Solution() { delete[] flag; }
    void init(int n) {
        count = 0;
        if (flag) {
            delete[] flag;
        }
        flag = new bool[5 * n - 2];
        for (int i = 5 * n - 2 - 1; i--;) {
            /*
            flag[0] to flag[n - 1] to indicate if the column had a queen before.
            flag[n] to flag[3 * n - 2] to indicate if the 45° diagonal had a queen before.
            flag[3 * n - 1] to flag[5 * n - 3] to indicate if the 135° diagonal had a queen before.
            */
            flag[i] = true;
        }
    }
    int totalNQueens(int n) {
        if (n < 2) {
            return n;
        }
        init(n);
        for (int i = 0; i < n; i++) {
            solve(0, i, n);
        }
        return count;
    }
};

int main() {
    Solution nq;
    for (int i = 0; i < 10; i++) {
        cout << i << ": " << nq.totalNQueens(i) << endl;
    }
    return 0;
}

运行结果

n-Queens