Algorithms.12

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

题目解释：国际象棋的棋子皇后，可以横向纵向和斜向吃掉对方棋子，题目的目标是一个NxN的棋盘上放置n个皇后并且不会相互攻击到彼此

典型backtrack场景，多选择问题

backtrack三要素：

目的
约束
选择

回归到这道题上来看：

目的：放置n个皇后
约束：皇后之间两两不能攻击
选择：按行逐个逐个尝试

本期使用c++

目的：

if (row == n)
    count++;

约束：显然每一行只能有一个皇后，然后就剩下比较纵向和斜向是否可行等于0是纵向，等于rowid - i是斜向

bool isvalid(std::vector<int> place)
{
    int rowid = place.size() - 1;
    for (int i = 0; i < rowid; i++)
    {
        int diff = abs(place[i] - place[rowid]);
        // 等于0是纵向，等于rowid - i是斜向
        if (diff == 0 || diff == rowid - i)
            return false;
    }
    return true;
}

选择：每一行逐一尝试

for (int i = 0; i < row; i++)
{
    place.push_back(i);
    if (isvalid(place))
    {
        backtrack(row, n, count, place);
    }
    place.pop_back();
}

完整代码

#include <vector>

class Solution
{
  public:
    int totalNQueens(int n)
    {
        int count = 0;
        std::vector<int> place;
        backtrack(n, 0, count, place);
        return count;
    }

  private:
    bool isvalid(std::vector<int> place)
    {
        int rowid = place.size() - 1;
        for (int i = 0; i < rowid; i++)
        {
            int diff = abs(place[i] - place[rowid]);
            if (diff == 0 || diff == rowid - i)
                return false;
        }
        return true;
    }

    void backtrack(int row, int n, int &count, std::vector<int> &place)
    {
        if (row == n)
            count++;
        else
        {
            n++;
            for (int i = 0; i < row; i++)
            {
                place.push_back(i);
                if (isvalid(place))
                {
                    backtrack(row, n, count, place);
                }
                place.pop_back();
            }
        }
    }
};