# Solution For N Queens

The N Queens problem is a classic problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share a row, column, or diagonal.

The LeetCode challenge for the N Queens problem asks you to return all possible solutions for a given n (size of the chessboard).

Here is a step-by-step solution for the N Queens problem on LeetCode:

1. Create an empty 2D list of size n×n to represent the chessboard.

2. Define a function `is_valid(row, col, board)` to check whether a queen can be placed in a given cell on the board. This function will check if there is already a queen in the same row, same column, and diagonals (both upper left and upper right) as the cell given by `(row, col)`.

3. Define a function `n_queens_helper(row, board)` that will recursively call itself, placing one queen on the board at a time, starting from the top row. It takes the current row and the current state of the board as input.

4. In the helper function, loop over the columns in the current row to check whether a queen can be placed in each cell.

5. If a cell is valid, place a queen in that cell and call the `n_queens_helper(row+1, board)` function recursively with the updated board and the next row.

6. If none of the columns in the current row allow a queen to be placed, return from the helper function (this is the base case of the recursion).

7. In the main `solve_n_queens(n)` function, call the helper function `n_queens_helper(0, [[]]*n)` to generate all possible solutions.

8. Finally, format the solutions as required by LeetCode, which is a list of lists where each inner list represents a single solution and each element of the list represents a string of the chessboard with ‘Q’ indicating the position of the queen and ‘.’ indicating an empty cell.

Here is the Python code for the N Queens problem on LeetCode:

“`
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def is_valid(row, col, board):
n = len(board)
# check if there is already a queen in the same row or same column
if any(board[row][i] == ‘Q’ for i in range(n)):
return False
if any(board[i][col] == ‘Q’ for i in range(n)):
return False
# check if there is already a queen in the same diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == ‘Q’:
return False
for i, j in zip(range(row, -1, -1), range(col, n)):
if board[i][j] == ‘Q’:
return False
return True

``````    def n_queens_helper(row, board):
n = len(board)
if row == n:
# base case: all queens have been placed
solutions.append([''.join(row) for row in board])
return
for col in range(n):
if is_valid(row, col, board):
# place a queen in the current cell
board[row][col] = 'Q'
# recursively place the rest of the queens
n_queens_helper(row+1, board)
# remove the queen from the current cell
board[row][col] = '.'

# initialization
solutions = []
board = [['.' for _ in range(n)] for _ in range(n)]
n_queens_helper(0, board)
return solutions
``````

“`

This code will generate all possible solutions for the N Queens problem for a given value of n.

## Step by Step Implementation For N Queens

```There are many possible solutions to the n-queens problem, but here is one possible Java solution:

1. Create an empty board of size n x n.

2. Place a queen in the first row, first column.

3. For each subsequent row, place a queen in the first column that does not conflict with any previously placed queens.

4. If a queen cannot be placed in the first column, move to the next column and try again.

5. Repeat steps 3-4 until all queens have been placed.

6. Print the board.```
```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.."]
]
'''

class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def could_place(row, col):
return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])

def place_queen(row, col):
cols[col] = 1
hill_diagonals[row - col] = 1
dale_diagonals[row + col] = 1

def remove_queen(row, col):
queens.remove((row, col))
cols[col] = 0
hill_diagonals[row - col] = 0
dale_diagonals[row + col] = 0

solution = []
for _, col in sorted(queens):
solution.append('.' * col + 'Q' + '.' * (n - col - 1))
output.append(solution)

def backtrack(row = 0):
for col in range(n):
if could_place(row, col):
place_queen(row, col)
if row + 1 == n:
else:
backtrack(row + 1)
remove_queen(row, col)

cols = [0] * n
hill_diagonals = [0] * (2 * n - 1)
dale_diagonals = [0] * (2 * n - 1)
queens = set()
output = []
backtrack()
return output```
```var solveNQueens = function(n) {
let result = [];
let board = [];

for (let i = 0; i < n; i++) {
board[i] = [];
for (let j = 0; j < n; j++) {
board[i][j] = 0;
}
}

const dfs = (board, row) => {
if (row === n) {
result.push(board.map(r => r.join('')));
return;
}

for (let col = 0; col < n; col++) {
if (isValid(board, row, col)) {
board[row][col] = 1;
dfs(board, row + 1);
board[row][col] = 0;
}
}
}

const isValid = (board, row, col) => {
for (let i = 0; i < row; i++) {
if (board[i][col]) return false;
}

for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) return false;
}

for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j]) return false;
}

return true;
}

dfs(board, 0);
return result;
};```
```The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

#include
#include

using namespace std;

class Solution {
public:
vector> solveNQueens(int n) {
vector> res;
vector nQueens(n, string(n, '.'));
solveNQueens(res, nQueens, 0, n);
return res;
}
private:
void solveNQueens(vector> &res, vector &nQueens, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col) {
if (isValid(nQueens, row, col, n)) {
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, row + 1, n);
nQueens[row][col] = '.';
}
}
}
bool isValid(vector &nQueens, int row, int col, int &n) {
//check if the column had a queen before.
for (int i = 0; i != row; ++i) {
if (nQueens[i][col] == 'Q') {
return false;
}
}
//check if the 45° diagonal had a queen before.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
if (nQueens[i][j] == 'Q') {
return false;
}
}
//check if the 135° diagonal had a queen before.
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
if (nQueens[i][j] == 'Q') {
return false;
}
}
return true;
}
};```
```You can find the problem statement here - https://leetcode.com/problems/n-queens/

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int n = 8;

// create an empty array
int[,] board = new int[n,n];

// call the solveNQ method
solveNQ(board, 0);
}

/* A method to solve the N Queen problem */
static bool solveNQ(int[,] board, int col)
{
if (col >= board.GetLength(0))
return true;

for (int i = 0; i < board.GetLength(0); i++)
{
if (isSafe(board, i, col))
{
board[i, col] = 1;

if (solveNQ(board, col + 1))
return true;

board[i, col] = 0;
}
}

return false;
}

/* A utility function to check if a queen can be placed on board[row,col]
Note that this function is called when "col" queens are already placed
in columns from 0 to col -1. So we need to check only left side for
attacking queens */
static bool isSafe(int[,] board, int row, int col)
{
int i, j;

/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row,i] == 1)
return false;

/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i,j] == 1)
return false;

/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]