八皇后问题

这种二维网格规划问题，一般是递归回溯的套路

#include <iostream>
#include <vector>

using namespace std;

int count = 0;
vector<vector<bool>> chessboard(8, vector<bool>(8, false));

void print() {
    for (int i=0; i<8; ++i) {
        for (int j=0; j<8; ++j) {
            if (chessboard[i][j]) cout << "☆";
            else cout << "★";
        }
        cout << endl;
    }

    cout << endl;
}

bool check(int row, int col) {
    for (int i=0; i<row; ++i) {
        if (chessboard[i][col]) return false;
    }

    for (int i=row-1, j=col-1; i>=0 && j>=0; --i, --j) {
        if (chessboard[i][j]) return false;
    }

    for (int i=row-1, j=col+1; i>=0 && j<8; --i, ++j) {
        if (chessboard[i][j]) return false;
    }

    return true;
}

void find_place(int row) {
    if (row > 7) {
        ++count;
        print();
        return;
    }

    for (int col=0; col<8; ++col) {
        if (check(row, col)) {
            chessboard[row][col] = true;
            find_place(row+1);
            chessboard[row][col] = false;
        }
    }
}

int main() {
    find_place(0);
    cout << count << endl;
}

回溯法的另一个应用——全排列(https://leetcode.cn/problems/permutations/description/?envType=problem-list-v2&envId=ex0k24j&)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> nums_used = vector<bool>(nums.size(), false);
        vector<int> sub_ret;
        find(nums, nums_used, 0, sub_ret);
        return ret;
    }

    vector<vector<int>> ret;

    void find(const vector<int>& nums, vector<bool> &nums_used, 
    int count, vector<int> &sub_ret) {
        if (count >= nums.size()) {
            ret.push_back(sub_ret);
            return;
        }

        for (int i=0; i<nums.size(); ++i) {
            if (!nums_used[i]) {
                nums_used[i] = true;
                sub_ret.push_back(nums[i]);
                find(nums, nums_used, count + 1, sub_ret);
                nums_used[i] = false;
                sub_ret.erase(sub_ret.end());
            }
        }
    }
};