N皇后问题

所谓N皇后问题，是一个经典的关于回溯法的问题。

问题描述：在n*n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

分析：对于每一个放置点而言，需要考虑四个方向上是否已经存在皇后。分别是行，列，四十五度斜线和一百三十五度斜线。

　　　其中，对于行：每一行只能放一个皇后，直到我们把最后一个皇后放到最后一行的合适位置。对于列：列相同的约束条件，只需判断该放置点与已放置好的皇后的j是否相等即可。

　　　对于四十五度斜线和一百三十五度斜线：当前棋子和已放置好的棋子不能存在行数差的绝对值等于列数差的绝对值的情况，若存在则说明两个棋子在同一条斜线上。

首先由比较简单的四皇后开始分析。

对于解空间比较小的情况，最简单的当然就是使用暴力搜索法。

class nQueen {
public:
    void update(std::vector<std::vector<int>> &is_occupied, int row, int col) {
        int n = is_occupied.size();
        for (int r = row+1; r < n; ++r) {
            if (0 == is_occupied[r][col]) is_occupied[r][col] = 1;
            if (col+r-row < n && 0 == is_occupied[r][col+r-row])
                is_occupied[r][col+r-row] = 1;
            if (col+row >= r && 0 == is_occupied[r][col+row-r])
                is_occupied[r][col+row-r] = 1;
        }
    }

    void visualize(std::vector<std::vector<int>> &solutions) {
        int n = solutions.size();
        for (int r = 0; r < n; ++r) {
            int l = solutions[r].size();
            for (int c = 0; c < l; ++c) std::cout << solutions[r][c] << " ";
            std::cout<< std::endl;

            for (int c = 0; c < l; ++c) {
                int pos = solutions[r][c];
                for (int i = 0; i < l; ++i) {
                    if (i == pos) std::cout << "Q ";
                    else std::cout << "* ";
                }
                std::cout << std::endl;
            }
            std::cout << std::endl;
        }

        std::cout << "Total solutions: " << solutions.size() << std::endl;
    }
　　// 暴力穷举式搜索法
    void fourQueen() {
        int n = 4;
        for (int i = 0; i < n; ++i) {
            std::vector<int> ret;
            ret.push_back(i);
            std::vector<std::vector<int>> is_occupied(n, std::vector<int>(n, 0));

            for (int c = 0; c < n; ++c)
                if (c != i) is_occupied[0][c] = 1;

            update(is_occupied, 0, i);
            for (int j = 0; j < n; ++j) {
                if (0 == is_occupied[1][j]) {
                    ret.push_back(j);
                    update(is_occupied, 1, j);
                    for (int h = 0; h < n; ++h) {
                        if (0 == is_occupied[2][h]) {
                            ret.push_back(h);
                            update(is_occupied, 2, h);
                            for (int k = 0; k < n; ++k) {
                                if (0 == is_occupied[3][k]) {
                                    ret.push_back(k);
                                    solutions.push_back(ret);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }

        visualize(solutions);
    }

public:
    std::vector<std::vector<int>> is_occupied;
    std::vector<std::vector<int>> solutions;
};

BruteForceSearch