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):
            queens.add((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

        def add_solution():
            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:
                        add_solution()
                    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