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