[Leet Code] N-Queens N황후 문제.

5075 단어 LeetCode

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.."]

]

 
고전적인 N황후 문제는 기본적인 모든 알고리즘서에 포함될 수 있는 문제이다. 고전 해법은 거슬러 올라가고 한 겹 한 겹 아래로 스캔하는 것이다. 그 중에서pos[i]는 i행 황후의 위치를 나타내고 -1로 초기화한 다음에 0부터 돌아가기 시작한다. 각 줄은 한 번씩 각 열을 훑어보고 이 위치에 황후를 놓으면 충돌이 있는지 판단한다. 이런 식으로 미루어 마지막 줄의 황후를 놓으면하나의 해법이 생성되어 결과res에 저장된 다음에 모든 상황을 검색할 수 있습니다. 코드는 다음과 같습니다.
 
class Solution {

public:

    vector<vector<string> > solveNQueens(int n) {

        vector<vector<string> > res;

        vector<int> pos(n, -1);

        solveNQueensDFS(pos, 0, res);

        return res;

    }

    void solveNQueensDFS(vector<int> &pos, int row, vector<vector<string> > &res) {

        int n = pos.size();

        if (row == n) {

            vector<string> out(n, string(n, '.'));

            for (int i = 0; i < n; ++i) {

                out[i][pos[i]] = 'Q';

            }

            res.push_back(out);

        } else {

            for (int col = 0; col < n; ++col) {

                if (isValid(pos, row ,col)) {

                    pos[row] = col;

                    solveNQueensDFS(pos, row + 1, res);

                    pos[row] = -1;

                }

            }

        }

    }

    bool isValid(vector<int> &pos, int row, int col) {

        for (int i = 0; i < row; ++i) {

            if (col == pos[i] || abs(row - i) == abs(col - pos[i])) {

                return false;

            }

        }

        return true;

    }

};

 
이 문제는 아직 귀속되지 않는 해법이 있으니 네티즌을 참고하십시오Just Do It 블로그. .

좋은 웹페이지 즐겨찾기