In the Leetcode N-Queens problem solution, The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [[“Q”]]
Constraints:
- 1 <= n <= 9
Solution in C Programming
char*** SolveNQueensInner(char*** pppcRet, char acCol[], char cIndex, char cN, int* pnReturnSize)
{
for(char i=0; i<cN; i++)
{
// check previous Queens
bool bIsValid = true;
for(char j=0; j<cIndex; j++)
{
// check vertical: i == acCol[j]
// check right-up to left-down diagonal: cIndex + i == j + acCol[j]
// check left-up to right-down diagonal: cIndex - i == j - acCol[j]
if(i == acCol[j] || cIndex+i == j+acCol[j] || cIndex-i == j-acCol[j])
{
bIsValid = false;
break;
}
}
if(bIsValid == false) continue;
// store
acCol[cIndex] = i;
if(cIndex < cN - 1)
{
// store next queens
pppcRet = SolveNQueensInner(pppcRet, acCol, cIndex+1, cN, pnReturnSize);
}
else
{
if(*pnReturnSize == 0)
{
pppcRet = (char***) malloc(sizeof(char**));
}
else
{
pppcRet = (char***) realloc(pppcRet, (*pnReturnSize+1)*sizeof(char**));
}
pppcRet[*pnReturnSize] = (char**) malloc(cN*sizeof(char*));
for(char j=0; j<cN; j++)
{
pppcRet[*pnReturnSize][j] = (char*) malloc((cN+1)*sizeof(char));
memset(pppcRet[*pnReturnSize][j], '.', cN*sizeof(char));
pppcRet[*pnReturnSize][j][acCol[j]] = 'Q';
pppcRet[*pnReturnSize][j][cN] = '\0';
}
(*pnReturnSize)++;
}
// restore
acCol[cIndex] = -1;
}
return pppcRet;
}Solution in C++ Programming
class Solution {
public:
bool canPlace(vector<string> &board, int r, int c){
for(int i=r-1;i>=0;i--)
if(board[i][c] == 'Q')
return false;
for(int i=r-1,j=c-1;i>=0 && j>=0;i--,j--)
if(board[i][j] == 'Q')
return false;
for(int i=r-1,j=c+1;i>=0 && j<board.size();i--,j++)
if(board[i][j] == 'Q')
return false;
return true;
}
void backtrack(vector<string> &board,vector<vector<string>> &ans, int r){
if(r == board.size()){
ans.push_back(board);
return;
}
for(int c=0;c<board.size();c++){
if(canPlace(board,r,c)){
board[r][c] = 'Q';
backtrack(board,ans,r+1);
board[r][c] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> board(n,string(n,'.'));
backtrack(board,ans,0);
return ans;
}
};Solution in Java Programming
class Solution {
public List<List<String>> solveNQueens(int n) {
boolean[][] board = new boolean[n][n];
List<List<String>> ans = queensList(board,0);
return ans;
}
private List<List<String>> queensList(boolean[][] board, int row){
if(row == board.length){
List<List<String>> list = new ArrayList<>();
list.add(appendInList(board));
return list;
}
List<List<String>> list = new ArrayList<>();
for(int col = 0; col<board.length; col++){
if(isSafe(board,row,col)){
board[row][col] = true;
list.addAll(queensList(board,row+1));
board[row][col] = false;
}
}
return list;
}
private List<String> appendInList(boolean[][] board) {
List<String> list = new ArrayList<>();
for(boolean[] row: board){
StringBuilder str = new StringBuilder();
for(boolean element: row){
if(element){
str.append("Q");
}else{
str.append(".");
}
}
list.add(str.toString());
}
return list;
}
private boolean isSafe(boolean[][] board, int row, int col) {
for(int i = 0; i<row; i++){
if(board[i][col]){
return false;
}
}
int maxLeft = Math.min(row,col);
for(int i = 1; i<=maxLeft; i++){
if(board[row-i][col-i]){
return false;
}
}
int maxRight = Math.min(row,board.length-col-1);
for(int i = 1; i<=maxRight; i++){
if(board[row-i][col+i]){
return false;
}
}
return true;
}
}Solution in Python Programming
class Solution(object):
def solveNQueens(self, n):
column = n*[0]
diag1 = (2 * n - 1) * [0]
diag2 = (2 * n - 1) * [0]
results = []
def boardState():
rows = []
for y in column:
rows.append(((y - 1) * '.') + 'Q' + ((n - y) * '.'))
return rows
def search(y):
if y == n:
results.append(boardState())
return
for x in range(n):
if column[x] or diag1[x + y] or diag2[x - y + n - 1]:
continue
column[x] = diag1[x + y] = diag2[x - y + n - 1] = y + 1
search(y + 1)
column[x] = diag1[x + y] = diag2[x - y + n - 1] = 0
search(0)
return resultsSolution in C# Programming
public class Solution
{
IList<IList<string>> ans;
IList<int> QueenIndexList;
public IList<IList<string>> SolveNQueens(int n)
{
ans = new List<IList<string>>();
QueenIndexList = new List<int>();
BackTrackToSolveNQueens(n);
return ans;
}
void BackTrackToSolveNQueens(int n)
{
if(QueenIndexList.Count == n)
{
IList<string> QueenStringList = GetCurrentQueenStringList(n);
ans.Add(QueenStringList);
return;
}
for(int col = 0;col < n;col++)
{
QueenIndexList.Add(col);
if(IsValidQueenPosition(QueenIndexList))
BackTrackToSolveNQueens(n);
QueenIndexList.RemoveAt(QueenIndexList.Count - 1);
}
}
bool IsValidQueenPosition(IList<int> QueenIndexList)
{
int row = QueenIndexList.Count - 1;
for(int PrevRow = 0;PrevRow <= (row - 1);PrevRow++)
{
//Diagonal
if((row - PrevRow) == Math.Abs(QueenIndexList[row] - QueenIndexList[PrevRow]))
return false;
//On the Same Row
if(QueenIndexList[row] == QueenIndexList[PrevRow])
return false;
}
return true;
}
IList<string> GetCurrentQueenStringList(int n)
{
IList<string> QueenStringlist = new List<string>();
StringBuilder resultSB = new StringBuilder();
for(int row = 0;row<QueenIndexList.Count;row++)
{
resultSB.Clear();
for(int col = 0;col < n;col++)
{
if(QueenIndexList[row] == col)
resultSB.Append("Q");
else
resultSB.Append(".");
}
QueenStringlist.Add(resultSB.ToString());
}
return QueenStringlist;
}
}Also read,