LeetCode_N-Queens

一.題目

N-Queens

My Submissions Total Accepted: 42296 Total Submissions: 160923 Difficulty: Hard

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 all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [.Q..,  // Solution 1
  ...Q,
  Q...,
  ..Q.],

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

Show Tags Show Similar Problems Have you met this question in a real interview? Yes No

Discuss

二.解題技巧

這道題是一道典型的圖的深度優先搜索算法，只不過要考慮到N皇後的限制條件，即不能有一個皇後與另外一個皇後在同一橫線、豎線和對角線上，因此，在放置每一個皇後時，都要考慮是否與已經放置的皇後沖突，這個可以通過使用一個輔助矩陣來記錄當前可以放置的位置，在放置每一個皇後的時候，更新這個輔助矩陣，即將與該皇後同行、同列和同一對角線的位置都設置為不可放置的狀態，然後再進行下一步，在進行回溯時，要清空這些標志。

三.實現代碼

#include 
#include 
#include 

using std::string;
using std::vector;

class Solution
{
private:
    void DFS(int n_Index, vector> &State, vector&Path,
             vector> &Result)
    {
        if (n_Index == State.size() - 1)
        {
            for (int Index = 0; Index < State.size(); ++Index)
            {
                if (State[n_Index][Index] == 1)
                {
                    Path[n_Index][Index] = 'Q';
                    Result.push_back(Path);
                    Path[n_Index][Index] = '.';
                    break;
                }
            }
            return;
        }

        for (int Index = 0; Index < State.size(); ++Index)
        {
            if (State[n_Index][Index] == 1)
            {
                Path[n_Index][Index] = 'Q';
                SetStatue(n_Index, Index, 1, State);
                DFS(n_Index + 1, State, Path, Result);
                SetStatue(n_Index, Index, -1, State);
                Path[n_Index][Index] = '.';
            }
        }

    }

    void SetStatue(int n_Index, int Index, int Value, vector> &State)
    {
        // col
        for (int ColIndex = Index; ColIndex < State.size(); ++ColIndex)
        {
            State[n_Index][ColIndex] += Value;
        }

        // row
        for (int RowIndex = n_Index; RowIndex < State.size(); ++RowIndex)
        {
            State[RowIndex][Index] += Value;
        }

        int RowIndex = n_Index + 1;
        int ColIndex = Index - 1;
        while(RowIndex < State.size() && ColIndex >= 0)
        {
            State[RowIndex][ColIndex] += Value;
            RowIndex++;
            ColIndex--;
        }

        RowIndex = n_Index + 1;
        ColIndex = Index + 1;
        while (RowIndex < State.size() && ColIndex < State.size())
        {
            State[RowIndex][ColIndex] += Value;
            RowIndex++;
            ColIndex++;
        }

    }

public:
    vector> solveNQueens(int n)
    {
        string TmpString(n, '.');
        vector Path(n, TmpString);

        vector> Result;

        vector TmpStatues(n, 1);
        vector> State(n, TmpStatues);

        if (n == 0)
        {
            return Result;
        }

        DFS(0, State, Path, Result);
        return Result;
    }
};

四.體會

這道題的難度在於更新和恢復輔助矩陣上面，這個地方很有值得深入研究的地方。