N Queen Problem

Last Updated : 4 Apr, 2026

Place n queens on an n×n chessboard so that no two attack each other (same row, column, or diagonal). Return all valid arrangements, where each solution shows the column position of the queen in each row.

Examples:

Input: n = 4
Output: [[2, 4, 1, 3], [3, 1, 4, 2]]
Explanation: We mainly print column numbers (from first to last row) of every possible configuration.

Input: n = 3
Output: []
Explanation: There are no possible solutions for n = 3

Try it on GfG Practice

Table of Content

[Naive Approach] - Using Backtracking
[Expected Approach 1] Backtracking with Hashing
[Expected Approach 2] Backtracking with Bit-masking - O(n!) Time and O(n) Space

[Naive Approach] - Using Backtracking

Use backtracking to place queens row by row, checking if each position is safe. If safe, place the queen and move to the next row; otherwise, backtrack and try another position. Store the solution when all queens are placed.

nqueens

C++

#include <iostream>
#include <vector>
using namespace std;

// Function to check if it is safe to place
int isSafe(vector<vector<int>>& mat, 
                    int row, int col) {
    int n = mat.size();
    int i, j;

    // Check this col on upper side
    for (i = 0; i < row; i++)
        if (mat[i][col])
            return 0;

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

    // Check upper diagonal on right side
    for (i = row-1, j = col+1; j < n && i >= 0; i--, j++)
        if (mat[i][j])
            return 0;

    return 1;
}

// Recursive function to place queens
void placeQueens(int row, vector<vector<int>>& mat, vector<vector<int>>&result) {
    int n = mat.size();

    // base case: If all queens are placed
    if(row == n) {
        
        // store current solution
        vector<int> ans;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j]){
                    ans.push_back(j + 1);
                }
            }
        }
        result.push_back(ans);
        return;
    }

    // Consider the row and try placing
    // queen in all columns one by one
    for(int i = 0; i < n; i++){
        
        // Check if the queen can be placed
        if(isSafe(mat, row, i)){
            mat[row][i] = 1;
            placeQueens(row + 1, mat, result);
            
            // backtrack
            mat[row][i] = 0; 
        }
    }
}

// Function to find all solutions
vector<vector<int>> nQueen(int n) {

    // Initialize the board
    vector<vector<int>> mat(n, vector<int>(n, 0));
    vector<vector<int>> result;

    // Place queens
    placeQueens(0, mat, result);

    return result;
}

int main() {
    int n = 4;
    vector<vector<int>> result = nQueen(n);
    for(auto &ans : result){
        for(auto i: ans){
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

Java

import java.util.ArrayList;

class GFG {

    // Function to check if it is safe to place
    static int isSafe(int[][] mat, int row, int col) {
        int n = mat.length;
        int i, j;

        // Check this col on upper side
        for (i = 0; i < row; i++)
            if (mat[i][col] == 1)
                return 0;

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

        // Check upper diagonal on right side
        for (i = row - 1, j = col + 1; j < n && i >= 0; i--, j++)
            if (mat[i][j] == 1)
                return 0;

        return 1;
    }

    // Recursive function to place queens
    static void placeQueens(int row, int[][] mat, 
                ArrayList<ArrayList<Integer>> result) {
        int n = mat.length;

        // base case: If all queens are placed
        if (row == n) {

            // store current solution
            ArrayList<Integer> ans = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (mat[i][j] == 1) {
                        ans.add(j + 1);
                    }
                }
            }
            result.add(ans);
            return;
        }

        // Consider the row and try placing
        // queen in all columns one by one
        for (int i = 0; i < n; i++) {

            // Check if the queen can be placed
            if (isSafe(mat, row, i) == 1) {
                mat[row][i] = 1;
                placeQueens(row + 1, mat, result);

                // backtrack
                mat[row][i] = 0;
            }
        }
    }

    // Function to find all solutions
    static ArrayList<ArrayList<Integer>> nQueen(int n) {

        // Initialize the board
        int[][] mat = new int[n][n];
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        // Place queens
        placeQueens(0, mat, result);

        return result;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<ArrayList<Integer>> result = nQueen(n);
        for (ArrayList<Integer> ans : result) {
            for (int i : ans) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

Python

def isSafe(mat, row, col):
    n = len(mat)

    # Check this col on upper side
    for i in range(row):
        if mat[i][col]:
            return 0

    # Check upper diagonal on left side
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if mat[i][j]:
            return 0
        i -= 1
        j -= 1

    # Check upper diagonal on right side
    i, j = row - 1, col + 1
    while i >= 0 and j < n:
        if mat[i][j]:
            return 0
        i -= 1
        j += 1

    return 1

# Recursive function to place queens
def placeQueens(row, mat, result):
    n = len(mat)

    # base case: If all queens are placed
    if row == n:
        
        # store current solution
        ans = []
        for i in range(n):
            for j in range(n):
                if mat[i][j]:
                    ans.append(j + 1)
        result.append(ans)
        return

    # Consider the row and try placing
    # queen in all columns one by one
    for i in range(n):
        
        # Check if the queen can be placed
        if isSafe(mat, row, i):
            mat[row][i] = 1
            placeQueens(row + 1, mat, result)

            # backtrack
            mat[row][i] = 0

# Function to find all solutions
def nQueen(n):
    
    # Initialize the board
    mat = [[0] * n for _ in range(n)]
    result = []

    # Place queens
    placeQueens(0, mat, result)

    return result

if __name__ == "__main__":
    n = 4
    result = nQueen(n)
    for ans in result:
        print(" ".join(map(str, ans)))

C#

using System;
using System.Collections.Generic;

class GFG {
    
    // Function to check if it is safe to place
    static int isSafe(int[,] mat, int row, int col) {
        int n = mat.GetLength(0);
        int i, j;

        // Check this col on upper side
        for (i = 0; i < row; i++)
            if (mat[i, col] == 1)
                return 0;

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

        // Check upper diagonal on right side
        for (i = row - 1, j = col + 1; j < n && i >= 0; i--, j++)
            if (mat[i, j] == 1)
                return 0;

        return 1;
    }

    // Recursive function to place queens
    static void placeQueens(int row, int[,] mat, List<List<int>> result) {
        int n = mat.GetLength(0);

        // base case: If all queens are placed
        if (row == n)
        {
            // store current solution
            List<int> ans = new List<int>();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (mat[i, j] == 1)
                    {
                        ans.Add(j + 1);
                    }
                }
            }
            result.Add(ans);
            return;
        }

        // Consider the row and try placing
        // queen in all columns one by one
        for (int i = 0; i < n; i++)
        {
            // Check if the queen can be placed
            if (isSafe(mat, row, i) == 1)
            {
                mat[row, i] = 1;
                placeQueens(row + 1, mat, result);

                // backtrack
                mat[row, i] = 0;
            }
        }
    }

    // Function to find all solutions
    static List<List<int>> nQueen(int n) {
      
        // Initialize the board
        int[,] mat = new int[n, n];
        List<List<int>> result = new List<List<int>>();

        // Place queens
        placeQueens(0, mat, result);

        return result;
    }

    public static void Main()
    {
        int n = 4;
        List<List<int>> result = nQueen(n);
        foreach (var ans in result)
        {
            foreach (var i in ans)
            {
                Console.Write(i + " ");
            }
            Console.WriteLine();
        }
    }
}

JavaScript

// Function to check if it is safe to place
function isSafe(mat, row, col) {
    let n = mat.length;
    let i, j;

    // Check this col on upper side
    for (i = 0; i < row; i++)
        if (mat[i][col])
            return 0;

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

    // Check upper diagonal on right side
    for (i = row - 1, j = col + 1; j < n && i >= 0; i--, j++)
        if (mat[i][j])
            return 0;

    return 1;
}

// Recursive function to place queens
function placeQueens(row, mat, result) {
    let n = mat.length;

    // base case: If all queens are placed
    if (row === n) {

        // store current solution
        let ans = [];
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (mat[i][j]) {
                    ans.push(j + 1);
                }
            }
        }
        result.push(ans);
        return;
    }

    // Consider the row and try placing
    // queen in all columns one by one
    for (let i = 0; i < n; i++) {

        // Check if the queen can be placed
        if (isSafe(mat, row, i)) {
            mat[row][i] = 1;
            placeQueens(row + 1, mat, result);

            // backtrack
            mat[row][i] = 0;
        }
    }
}

// Function to find all solutions
function nQueen(n) {

    // Initialize the board
    let mat = Array.from({ length: n }, () => Array(n).fill(0));
    let result = [];

    // Place queens
    placeQueens(0, mat, result);

    return result;
}

// Driver code
let n = 4;
let result = nQueen(n);
for (let ans of result) {
    console.log(ans.join(' '));
}

Output

2 4 1 3 
3 1 4 2

Time Complexity: O(n!)
We try placing queens in different positions, and choices reduce at each step due to conflicts.
Auxiliary Space: O(n^2)
We use an n × n board and recursion stack for backtracking.

[Expected Approach 1] Backtracking with Hashing

This is mainly an optimization over the above approach, we optimize the isSafe() by using three arrays to track occupied columns and diagonals. A position is considered valid only if its column and both diagonals are free. When placing a queen, mark these arrays, and while backtracking, unmark them. This allows checking safe positions in constant time O(1).

C++

#include <iostream>
#include<vector>
using namespace std;

// Recursive function to place queens
void placeQueens(int i, vector<int> &cols, vector<int> &leftDiagonal,
                     vector<int> &rightDiagonal, vector<int> &cur, 
                     vector<vector<int>> &result) {
    int n = cols.size();

    // base case: If all queens are placed
    if(i == n) {
        result.push_back(cur);
        return;
    }

    // Consider the row and try placing
    // queen in all columns one by one
    for(int j = 0; j < n; j++){

        // Check if the queen can be placed
        if(cols[j] || rightDiagonal[i + j] || 
                        leftDiagonal[i - j + n - 1]) 
            continue;
        
        // mark the cell occupied
        cols[j] = 1;
        rightDiagonal[i+j] = 1; 
        leftDiagonal[i - j + n - 1] = 1;
        cur.push_back(j+1);

        placeQueens(i + 1, cols, leftDiagonal, rightDiagonal, cur, result);

        // remove the queen from current cell
        cur.pop_back();
        cols[j] = 0;
        rightDiagonal[i+j] = 0; 
        leftDiagonal[i - j + n - 1] = 0;        
    }
}

// Function to find the solution
// to the N-Queens problem
vector<vector<int>> nQueen(int n) {

    // array to mark the occupied cells
    vector<int> cols(n, 0);
    vector<int> leftDiagonal(n*2, 0);
    vector<int> rightDiagonal(n*2, 0);
    vector<int> cur;
    vector<vector<int>> result;

    // Place queens
    placeQueens(0, cols, leftDiagonal, rightDiagonal, cur, result);

    return result;
}

int main() {
    int n = 4;
    vector<vector<int>> ans = nQueen(n);
    for(auto &a: ans){
        for(auto i: a){
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

Java

import java.util.ArrayList;

class GFG {

    // Recursive function to place queens
    static void placeQueens(int i, int[] cols, int[] leftDiagonal,
                                   int[] rightDiagonal, ArrayList<Integer> cur,
                                   ArrayList<ArrayList<Integer>> result) {
        int n = cols.length;

        // base case: If all queens are placed
        if (i == n) {
            result.add(new ArrayList<>(cur));
            return;
        }

        // Consider the row and try placing
        // queen in all columns one by one
        for (int j = 0; j < n; j++) {

            // Check if the queen can be placed
            if (cols[j] == 1 || rightDiagonal[i + j] == 1 ||
                leftDiagonal[i - j + n - 1] == 1)
                continue;

            // mark the cell occupied
            cols[j] = 1;
            rightDiagonal[i + j] = 1;
            leftDiagonal[i - j + n - 1] = 1;
            cur.add(j + 1);

            placeQueens(i + 1, cols, leftDiagonal, rightDiagonal, cur, result);

            // remove the queen from current cell
            cur.remove(cur.size() - 1);
            cols[j] = 0;
            rightDiagonal[i + j] = 0;
            leftDiagonal[i - j + n - 1] = 0;
        }
    }

    // Function to find the solution
    // to the N-Queens problem
    static ArrayList<ArrayList<Integer>> nQueen(int n) {

        // array to mark the occupied cells
        int[] cols = new int[n];
        int[] leftDiagonal = new int[n * 2];
        int[] rightDiagonal = new int[n * 2];
        ArrayList<Integer> cur = new ArrayList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        // Place queens
        placeQueens(0, cols, leftDiagonal, rightDiagonal, cur, result);

        return result;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<ArrayList<Integer>> ans = nQueen(n);
        for (ArrayList<Integer> a : ans) {
            for (int i : a) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

Python

# Recursive function to place queens
def placeQueens(i, cols, leftDiagonal, rightDiagonal, cur, result):
    n = len(cols)

    # base case: If all queens are placed
    if i == n:
        result.append(cur[:])
        return

    # Consider the row and try placing
    # queen in all columns one by one
    for j in range(n):

        # Check if the queen can be placed
        if cols[j] or rightDiagonal[i + j] or leftDiagonal[i - j + n - 1]:
            continue

        # mark the cell occupied
        cols[j] = 1
        rightDiagonal[i + j] = 1
        leftDiagonal[i - j + n - 1] = 1
        cur.append(j + 1)

        placeQueens(i + 1, cols, leftDiagonal, rightDiagonal, cur, result)

        # remove the queen from current cell
        cur.pop()
        cols[j] = 0
        rightDiagonal[i + j] = 0
        leftDiagonal[i - j + n - 1] = 0


# Function to find the solution
# to the N-Queens problem
def nQueen(n):
    
    # array to mark the occupied cells
    cols = [0] * n
    leftDiagonal = [0] * (2 * n)
    rightDiagonal = [0] * (2 * n)
    cur = []
    result = []

    # Place queens
    placeQueens(0, cols, leftDiagonal, rightDiagonal, cur, result)

    return result


if __name__ == "__main__":
    n = 4
    ans = nQueen(n)
    for a in ans:
        print(" ".join(map(str, a)))

C#

using System;
using System.Collections.Generic;

class GFG {

    // Recursive function to place queens
    static void placeQueens(int i, int[] cols, int[] leftDiagonal, int[] rightDiagonal, 
                            List<int> cur, List<List<int>> result) {
        int n = cols.Length;

        // base case: If all queens are placed
        if (i == n) {
            result.Add(new List<int>(cur));
            return;
        }

        // Consider the row and try placing
        // queen in all columns one by one
        for (int j = 0; j < n; j++) {

            // Check if the queen can be placed
            if (cols[j] == 1 || rightDiagonal[i + j] == 1 || 
                leftDiagonal[i - j + n - 1] == 1)
                continue;

            // mark the cell occupied
            cols[j] = 1;
            rightDiagonal[i + j] = 1;
            leftDiagonal[i - j + n - 1] = 1;
            cur.Add(j + 1);

            placeQueens(i + 1, cols, leftDiagonal, rightDiagonal, cur, result);

            // remove the queen from current cell
            cur.RemoveAt(cur.Count - 1);
            cols[j] = 0;
            rightDiagonal[i + j] = 0;
            leftDiagonal[i - j + n - 1] = 0;
        }
    }

    // Function to find the solution
    // to the N-Queens problem
    static List<List<int>> nQueen(int n) {

        // array to mark the occupied cells
        int[] cols = new int[n];
        int[] leftDiagonal = new int[2 * n];
        int[] rightDiagonal = new int[2 * n];
        List<int> cur = new List<int>();
        List<List<int>> result = new List<List<int>>();

        // Place queens
        placeQueens(0, cols, leftDiagonal, rightDiagonal, cur, result);

        return result;
    }

    static void Main() {
        int n = 4;
        List<List<int>> ans = nQueen(n);
        foreach (var a in ans) {
            Console.WriteLine(string.Join(" ", a));
        }
    }
}

JavaScript

// Recursive function to place queens
function placeQueens(i, cols, leftDiagonal, rightDiagonal, cur, result) {
    const n = cols.length;

    // base case: If all queens are placed
    if (i === n) {
        result.push([...cur]);
        return;
    }

    // Consider the row and try placing
    // queen in all columns one by one
    for (let j = 0; j < n; j++) {

        // Check if the queen can be placed
        if (cols[j] || rightDiagonal[i + j] || leftDiagonal[i - j + n - 1]) {
            continue;
        }

        // mark the cell occupied
        cols[j] = 1;
        rightDiagonal[i + j] = 1;
        leftDiagonal[i - j + n - 1] = 1;
        cur.push(j + 1);

        placeQueens(i + 1, cols, leftDiagonal, rightDiagonal, cur, result);

        // remove the queen from current cell
        cur.pop();
        cols[j] = 0;
        rightDiagonal[i + j] = 0;
        leftDiagonal[i - j + n - 1] = 0;
    }
}

// Function to find the solution
// to the N-Queens problem
function nQueen(n) {
    
    // array to mark the occupied cells
    const cols = new Array(n).fill(0);
    const leftDiagonal = new Array(2 * n).fill(0);
    const rightDiagonal = new Array(2 * n).fill(0);
    const cur = [];
    const result = [];

    // Place queens
    placeQueens(0, cols, leftDiagonal, rightDiagonal, cur, result);

    return result;
}

// Driven Code
const n = 4;
const ans = nQueen(n);
ans.forEach(a => {
    console.log(a.join(" "));
});

Output

2 4 1 3 
3 1 4 2

Time Complexity: O(n!) – we try placing a queen in every row recursively, pruning invalid positions using the arrays.
Auxiliary Space: O(n)

[Expected Approach 2] Backtracking with Bit-masking - O(n!) Time and O(n) Space

This is a further optimization for small board sizes. The idea is to use three variables to track occupied rows and diagonals. At each step, use bit operations to quickly find safe positions. Place a queen, update the variables, and move forward; if no position works, backtrack and try other options until all solutions are found.

C++

#include <iostream>
#include <vector>
using namespace std;

// Function to check if the current placement is safe
bool isSafe(int row, int col, int rows, int ld, int rd, int n) {
    return !((rows >> row) & 1) && !((ld >> (row + col)) & 1) && !((rd >> (row - col + n)) & 1);
}

// Recursive function to generate all possible permutations
void nQueenUtil(int col, int n, vector<int>& board, 
  	vector<vector<int>>& res, int rows, int ld, int rd) {

    // If all queens are placed, add into res
    if(col > n) {
        res.push_back(board);
        return;
    }

    // Try placing a queen in each row
    // of the current column
    for(int row = 1; row <= n; ++row) {

        // Check if it's safe to place the queen
        if(isSafe(row, col, rows, ld, rd, n)) {
            
            // Place the queen
            board.push_back(row); 

            // Recur to place the next queen
            nQueenUtil(col + 1, n, board,
                         res, rows | (1 << row), 
                         (ld | (1 << (row + col))), 
                         (rd | (1 << (row - col + n))));

            // Backtrack: remove the queen
            board.pop_back(); 
        }
    }
        
} 

// Main function to find all distinct 
// res to the n-queens puzzle
vector<vector<int>> nQueen(int n) {
    vector<vector<int>> res; 

    // Current board configuration
    vector<int> board; 
    
    // Start solving from the first column
    nQueenUtil(1, n, board, res, 0, 0, 0);
    return res; 
}

int main() {
    int n = 4; 
    vector<vector<int>> res = nQueen(n); 

    for(int i = 0;i < res.size(); i++) {
        cout << "[";
        for(int j = 0; j < n; ++j) {
            cout << res[i][j]; 
            if(j != n - 1)   cout << " "; 
        }
        cout << "]\n";
    }
    return 0;
}

Java

import java.util.*;

class GfG {

    // Function to check if the current placement is safe
    static boolean isSafe(int row, int col, int rows, int ld, int rd, int n) {
        return !(((rows >> row) & 1) == 1) && !(((ld >> (row + col)) & 1) == 1) 
                && !(((rd >> (row - col + n)) & 1) == 1);
    }

    // Recursive function to generate all possible permutations
    static void nQueenUtil(int col, int n, ArrayList<Integer> board, 
        ArrayList<ArrayList<Integer>> res, int rows, int ld, int rd) {

        // If all queens are placed, add into res
        if (col > n) {
            res.add(new ArrayList<>(board));
            return;
        }

        // Try placing a queen in each row
        // of the current column
        for (int row = 1; row <= n; ++row) {

            // Check if it's safe to place the queen
            if (isSafe(row, col, rows, ld, rd, n)) {

                // Place the queen
                board.add(row);

                // Recur to place the next queen
                nQueenUtil(col + 1, n, board, res, 
                    rows | (1 << row), (ld | (1 << (row + col))), 
                    (rd | (1 << (row - col + n))));

                // Backtrack: remove the queen
                board.remove(board.size() - 1);
            }
        }
    }

    // Main function to find all distinct 
    // res to the n-queens puzzle
    static ArrayList<ArrayList<Integer>> nQueen(int n) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        // Current board configuration
        ArrayList<Integer> board = new ArrayList<>();

        // Start solving from the first column
        nQueenUtil(1, n, board, res, 0, 0, 0);
        return res;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<ArrayList<Integer>> res = nQueen(n);

        for (ArrayList<Integer> solution : res) {
            System.out.print("[");
            for (int j = 0; j < n; ++j) {
                System.out.print(solution.get(j));
                if (j != n - 1) System.out.print(" ");
            }
            System.out.println("]");
        }
    }
}

Python

# Function to check if the current placement is safe
def isSafe(row, col, rows, ld, rd, n):
    return not ((rows >> row) & 1) and \
  		   not ((ld >> (row + col)) & 1) and \
           not ((rd >> (row - col + n)) & 1)

# Recursive function to generate all possible permutations
def nQueenUtil(col, n, board, res, rows, ld, rd):

    # If all queens are placed, add into res
    if col > n:
        res.append(board[:])
        return

    # Try placing a queen in each row
    # of the current column
    for row in range(1, n + 1):

        # Check if it's safe to place the queen
        if isSafe(row, col, rows, ld, rd, n):

            # Place the queen
            board.append(row)

            # Recur to place the next queen
            nQueenUtil(col + 1, n, board, res, 
                rows | (1 << row), (ld | (1 << (row + col))), 
                (rd | (1 << (row - col + n))))

            # Backtrack: remove the queen
            board.pop()

# Main function to find all distinct 
# res to the n-queens puzzle
def nQueen(n):
    res = []

    # Current board configuration
    board = []

    # Start solving from the first column
    nQueenUtil(1, n, board, res, 0, 0, 0)
    return res

if __name__ == "__main__":
    n = 4
    res = nQueen(n)
    
    for solution in res:
        print("[", end="")
        for j in range(n):
            print(solution[j], end="")
            if j != n - 1:
                print(" ", end="")
        print("]")

C#

using System;
using System.Collections.Generic;

class GfG {
    
    // Function to check if the current placement is safe
    static bool isSafe(int row, int col, int rows, int ld, int rd, int n) {
        return !(((rows >> row) & 1) == 1) && !(((ld >> (row + col)) & 1) == 1) 
                && !(((rd >> (row - col + n)) & 1) == 1);
    }

    // Recursive function to generate all possible permutations
    static void nQueenUtil(int col, int n, List<int> board, 
        List<List<int>> res, int rows, int ld, int rd) {

        // If all queens are placed, add into res
        if (col > n) {
            res.Add(new List<int>(board));
            return;
        }

        // Try placing a queen in each row
        // of the current column
        for (int row = 1; row <= n; ++row) {

            // Check if it's safe to place the queen
            if (isSafe(row, col, rows, ld, rd, n)) {

                // Place the queen
                board.Add(row);

                // Recur to place the next queen
                nQueenUtil(col + 1, n, board, res, 
                    rows | (1 << row), (ld | (1 << (row + col))), 
                    (rd | (1 << (row - col + n))));

                // Backtrack: remove the queen
                board.RemoveAt(board.Count - 1);
            }
        }
    }

    // Main function to find all distinct 
    // res to the n-queens puzzle
    static List<List<int>> nQueen(int n) {
        List<List<int>> res = new List<List<int>>();

        // Current board configuration
        List<int> board = new List<int>();

        // Start solving from the first column
        nQueenUtil(1, n, board, res, 0, 0, 0);
        return res;
    }

    static void Main() {
        int n = 4;
        List<List<int>> res = nQueen(n);

        foreach (var solution in res) {
            Console.Write("[");
            for (int j = 0; j < n; ++j) {
                Console.Write(solution[j]);
                if (j != n - 1) Console.Write(" ");
            }
            Console.WriteLine("]");
        }
    }
}

JavaScript

// Function to check if the current placement is safe
function isSafe(row, col, rows, ld, rd, n) {
    return !((rows >> row) & 1) && 
    		!((ld >> (row + col)) & 1) && 
            !((rd >> (row - col + n)) & 1);
}

// Recursive function to generate all possible permutations
function nQueenUtil(col, n, board, res, rows, ld, rd) {

    // If all queens are placed, add into res
    if (col > n) {
        res.push([...board]);
        return;
    }

    // Try placing a queen in each row
    // of the current column
    for (let row = 1; row <= n; ++row) {

        // Check if it's safe to place the queen
        if (isSafe(row, col, rows, ld, rd, n)) {

            // Place the queen
            board.push(row);

            // Recur to place the next queen
            nQueenUtil(col + 1, n, board, res, 
                rows | (1 << row), (ld | (1 << (row + col))), 
                (rd | (1 << (row - col + n))));

            // Backtrack: remove the queen
            board.pop();
        }
    }
}

// Main function to find all distinct 
// res to the n-queens puzzle
function nQueen(n) {
    let res = [];

    // Current board configuration
    let board = [];

    // Start solving from the first column
    nQueenUtil(1, n, board, res, 0, 0, 0);
    return res;
}

// Driver Code
let n = 4;
let res = nQueen(n);

for (let i = 0; i < res.length; i++) {
    process.stdout.write("[");
    for (let j = 0; j < n; ++j) {
        process.stdout.write(res[i][j].toString());
        if (j !== n - 1) process.stdout.write(" ");
    }
    console.log("]");
}

Output

[2 4 1 3]
[3 1 4 2]

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem