Java Program to Solve N Queens Problem

A Java program to solve the N Queens problem uses backtracking by placing queens row by row and checking safe positions with a method like isSafe(), then recursively placing queens until all are placed or backtracking if stuck.

Examples

Input4

Output[[.Q.., ...Q, Q..., ..Q.]]

Input1

Output[[Q]]

Input2

OutputNo solution exists

How to Think About It

To solve the N Queens problem, think of placing one queen per row. For each row, try all columns and check if placing a queen there is safe (no other queen attacks it). If safe, place the queen and move to the next row. If stuck, backtrack to try other positions.

Algorithm

1

Start with the first row.

2

Try placing a queen in each column of the current row.

3

Check if the position is safe from attacks by other queens.

4

If safe, place the queen and move to the next row.

5

If all queens are placed, record the solution.

6

If no safe position in a row, backtrack to previous row and try next column.

Code

java

public class NQueens {
    private int n;
    private char[][] board;

    public NQueens(int n) {
        this.n = n;
        board = new char[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = '.';
    }

    private boolean isSafe(int row, int col) {
        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 boolean solve(int row) {
        if (row == n) return true;
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                if (solve(row + 1)) return true;
                board[row][col] = '.';
            }
        }
        return false;
    }

    public void solveNQueens() {
        if (solve(0)) printBoard();
        else System.out.println("No solution exists");
    }

    private void printBoard() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 4;
        NQueens nq = new NQueens(n);
        nq.solveNQueens();
    }
}

Output

..Q.
...Q
Q...
.Q..

Dry Run

Let's trace the 4-queens example through the code

1

Start at row 0

Try placing queen at (0,0), safe? Yes, place Q.

2

Move to row 1

Try columns 0 to 3; (1,0) attacked, (1,1) attacked, (1,2) safe, place Q.

3

Move to row 2

Try columns; (2,0) attacked, (2,1) attacked, (2,2) attacked, (2,3) attacked, no safe spot, backtrack.

4

Backtrack to row 1

Remove Q from (1,2), try next column (1,3), safe, place Q.

5

Move to row 2

Try columns; (2,0) safe, place Q.

6

Move to row 3

Try columns; (3,0) attacked, (3,1) safe, place Q.

7

All queens placed

Solution found, print board.

Row	Column Tried	Action
0	0	Place Q
1	0,1	Attacked, skip
1	2	Place Q
2	0,1,2,3	No safe spot, backtrack
1	3	Place Q
2	0	Place Q
3	0	Attacked
3	1	Place Q

Why This Works

Step 1: Backtracking approach

The program tries to place queens one row at a time and backtracks if no safe position is found.

Step 2: Safety check

Before placing a queen, it checks the column and diagonals above to ensure no queen attacks the position.

Step 3: Recursive solution

If a queen is placed safely, the program moves to the next row recursively until all queens are placed.

Alternative Approaches

Using boolean arrays for columns and diagonals

java

public class NQueensFast {
    private int n;
    private char[][] board;
    private boolean[] cols, d1, d2;

    public NQueensFast(int n) {
        this.n = n;
        board = new char[n][n];
        cols = new boolean[n];
        d1 = new boolean[2 * n];
        d2 = new boolean[2 * n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = '.';
    }

    private boolean solve(int row) {
        if (row == n) return true;
        for (int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if (!cols[col] && !d1[id1] && !d2[id2]) {
                board[row][col] = 'Q';
                cols[col] = true; d1[id1] = true; d2[id2] = true;
                if (solve(row + 1)) return true;
                board[row][col] = '.';
                cols[col] = false; d1[id1] = false; d2[id2] = false;
            }
        }
        return false;
    }

    public void solveNQueens() {
        if (solve(0)) printBoard();
        else System.out.println("No solution exists");
    }

    private void printBoard() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int n = 4;
        new NQueensFast(n).solveNQueens();
    }
}

This method uses extra arrays to check safety in O(1) time, making it faster but uses more memory.

Print all solutions instead of one

java

import java.util.*;
public class NQueensAll {
    private int n;
    private char[][] board;
    private List<List<String>> solutions = new ArrayList<>();

    public NQueensAll(int n) {
        this.n = n;
        board = new char[n][n];
        for (int i = 0; i < n; i++)
            Arrays.fill(board[i], '.');
    }

    private boolean isSafe(int row, int col) {
        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 void solve(int row) {
        if (row == n) {
            List<String> sol = new ArrayList<>();
            for (int i = 0; i < n; i++) sol.add(new String(board[i]));
            solutions.add(sol);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q';
                solve(row + 1);
                board[row][col] = '.';
            }
        }
    }

    public void solveNQueens() {
        solve(0);
        if (solutions.isEmpty()) System.out.println("No solution exists");
        else solutions.forEach(sol -> {
            sol.forEach(System.out::println);
            System.out.println();
        });
    }

    public static void main(String[] args) {
        int n = 4;
        new NQueensAll(n).solveNQueens();
    }
}

This approach finds and prints all possible solutions, useful for understanding all configurations but slower.

Complexity: O(n!) time, O(n^2) space

Time Complexity

The algorithm tries to place queens row by row, exploring up to n columns per row, leading to factorial time in worst case due to backtracking.

Space Complexity

The board uses O(n^2) space, and recursion stack uses O(n) space for rows.

Which Approach is Fastest?

Using boolean arrays for columns and diagonals speeds up safety checks to O(1), making it faster than checking the board each time.

Approach	Time	Space	Best For
Basic backtracking with board checks	O(n!)	O(n^2)	Simple implementation, easy to understand
Backtracking with boolean arrays	O(n!)	O(n)	Faster safety checks, better for large n
Find all solutions	O(n!)	O(n^2)	When all solutions are needed