# Leetcode N-Queens problem solution

Apr 1, 2023

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<>();
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;
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(".");
}
}
}

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 results``````

## Solution 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);
return;
}

for(int col = 0;col < n;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(".");
}
}
return  QueenStringlist;
}

}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.