Table of contents

Print all the distinct solutions of placing N-Queens in a NxN chessboard

The N-Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Write a program that returns all distinct solutions to the N-Queens puzzle. Each solution contains a distinct board configuration of the N-Queens' placement, where 'Q' and '.' indicate a queen and an empty space, respectively.

Input-Output Examples

Example 1:

plaintext
Input: n = 4
Output: [
         [".Q..",
          "...Q",
          "Q...",
          "..Q."],
         
         ["..Q.",
          "Q...",
          "...Q",
          ".Q.."]
        ]

Example 2:

plaintext
Input: n = 1
Output: [["Q"]]

Approach:

Technique: Backtracking

  1. Initialization: Create a list to store the solutions and a board to represent the current state.
  2. Backtracking Function:
    • Use a recursive function to try placing a queen in each row.
    • For each row, iterate through the columns and check if the current position is safe.
    • If the position is safe, place the queen and recursively place queens in the next row.
    • If a solution is found, add it to the list of solutions.
    • Backtrack by removing the queen and trying the next position.
  3. Safety Check: Ensure that no two queens threaten each other by checking the column, and both diagonals.

C++ Program to implement N-queens problem

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve(vector<vector<string>>& solutions, vector<string>& board, int row, int n);
bool isSafe(const vector<string>& board, int row, int col, int n);

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    solve(solutions, board, 0, n);
    return solutions;
}

void solve(vector<vector<string>>& solutions, vector<string>& board, int row, int n) {
    if (row == n) {
        solutions.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solve(solutions, board, row + 1, n);
            board[row][col] = '.';
        }
    }
}

bool isSafe(const vector<string>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

int main() {
    int n = 4;
    vector<vector<string>> result = solveNQueens(n);
    for (const auto& solution : result) {
        for (const auto& row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}

Java Program to implement N-queens problem

java
import java.util.*;

public class NQueens {
    public static void main(String[] args) {
        int n = 4;
        List<List<String>> result = solveNQueens(n);
        for (List<String> solution : result) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        solve(solutions, board, 0, n);
        return solutions;
    }

    private static void solve(List<List<String>> solutions, char[][] board, int row, int n) {
        if (row == n) {
            solutions.add(construct(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q';
                solve(solutions, board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }

    private static boolean isSafe(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private static List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (char[] chars : board) {
            path.add(new String(chars));
        }
        return path;
    }
}

Python Program to implement N-Queens problem

python
from typing import List

def solveNQueens(n: int) -> List[List[str]]:
    solutions = []
    board = [["."] * n for _ in range(n)]
    solve(solutions, board, 0, n)
    return solutions

def solve(solutions: List[List[str]], board: List[List[str]], row: int, n: int) -> None:
    if row == n:
        solutions.append(["".join(row) for row in board])
        return
    for col in range(n):
        if isSafe(board, row, col, n):
            board[row][col] = "Q"
            solve(solutions, board, row + 1, n)
            board[row][col] = "."

def isSafe(board: List[List[str]], row: int, col: int, n: int) -> bool:
    for i in range(row):
        if board[i][col] == "Q":
            return False
    for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
        if board[i][j] == "Q":
            return False
    for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
        if board[i][j] == "Q":
            return False
    return True

if __name__ == "__main__":
    n = 4
    result = solveNQueens(n)
    for solution in result:
        for row in solution:
            print(row)
        print()

These codes include the main function and the necessary functions for solving the N-Queens problem. The solveNQueens function initializes the board and starts the backtracking process. The solve function places queens row by row, and the isSafe function checks if a position is safe for placing a queen. The result is printed to the console, showing all the distinct solutions for the N-Queens problem.

DSA

Related Articles