## N-Queens

The n-queens puzzle is the problem of placing n queens on an nn 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.."]
]```
`class Solution {public:    vector<vector<string> > result;    bool Check(vector<int> & board, int n, int i, int j)    {        for (int k = i-1; k >= 0; k--)            if (board[k] == j) return false;        for (int k = i-1; k >= 0; k--)        {            if (board[k] - k == j - i) return false;            if (board[k] + k == j + i) return false;        }        return true;    }        void NQueenHelper(vector<int> & board, int n, int i)    {        if (i == n)        {            string row(n, '.');            vector<string> strboard(n, row);            for (int i = 0; i < n; i++)                strboard[i][board[i]] = 'Q';            result.push_back(strboard);            return;        }                for (int j = 0; j < n; j++)        {            if (Check(board, n, i, j))            {                board[i] = j;                NQueenHelper(board, n, i+1);            }        }    }    vector<vector<string> > solveNQueens(int n)    {        result.resize(0);        vector<int> board(n, -1);        NQueenHelper(board, n, 0);        return result;    }};`

Advertisements