8 Queens Problem in Java - Complete Solution

A complete Java guide to solving the 8 queens problem using recursive backtracking. Includes the full NQueens class, isSafe method walkthrough, compilation instructions, and an iterative alternative.

Play Now Learn More

Table of Contents

Problem Setup

The 8 queens problem is a classic computer science exercise that appears in Java textbooks and coding interview prep. The task: place 8 queens on an 8×8 chessboard such that no two queens threaten each other. Queens attack along rows, columns, and both diagonals.

In Java, the most natural representation is a one-dimensional integer array int[] board of length n, where board[row] stores the column index of the queen in that row. This eliminates row conflicts by design — each row holds exactly one queen.

Java is a popular language for demonstrating this algorithm in university data structures and algorithms courses. The solution here works for the general N queens problem by parameterizing the board size. For a broader comparison of algorithm approaches, see the N Queens Algorithm Overview.

Java Implementation

The following complete Java program finds and prints all 92 solutions to the 8 queens problem. Save it as NQueens.java:

public class NQueens {

    private final int n;
    private final int[] board;
    private int solutionCount;

    public NQueens(int n) {
        this.n = n;
        this.board = new int[n];
        this.solutionCount = 0;
    }

    /**
     * Returns true if placing a queen at (row, col) is safe
     * given queens already placed in rows 0..row-1.
     */
    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col) return false;                        // same column
            if (Math.abs(board[i] - col) == Math.abs(i - row)) return false; // diagonal
        }
        return true;
    }

    /**
     * Recursively places queens row by row using backtracking.
     */
    private void solve(int row) {
        if (row == n) {
            solutionCount++;
            printBoard();
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;
                solve(row + 1);
                board[row] = -1; // backtrack
            }
        }
    }

    /**
     * Prints the current board state to stdout.
     */
    private void printBoard() {
        System.out.println("Solution " + solutionCount + ":");
        for (int row = 0; row < n; row++) {
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < n; col++) {
                sb.append(board[row] == col ? "Q " : ". ");
            }
            System.out.println(sb);
        }
        System.out.println();
    }

    public int getSolutionCount() {
        return solutionCount;
    }

    public static void main(String[] args) {
        int n = 8;
        NQueens solver = new NQueens(n);
        solver.solve(0);
        System.out.println("Total solutions for " + n + "-Queens: " + solver.getSolutionCount());
    }
}

How It Works

The Java implementation follows the standard backtracking algorithm:

  1. Constructor: Initializes the board array and solution counter. Separating state into instance fields keeps the recursive method signature clean.
  2. isSafe(row, col): Iterates through all rows above the current one. For each placed queen, it checks (a) same column and (b) diagonal conflict using the absolute-difference test. If either condition is true, returns false.
  3. solve(row): The recursive backbone. When row == n, a complete solution has been found — increment the counter and print. Otherwise, try each column, recurse if safe, then reset board[row] = -1 to backtrack.
  4. main(): Creates an NQueens instance with n=8 and triggers the search from row 0.

Time complexity: O(n!) in the worst case, O(n) space for the board array and call stack. For n=8, all 92 solutions are printed in well under a second.

Running the Code

To compile and run the Java solution:

javac NQueens.java
java NQueens

Expected output (truncated):

Solution 1:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

...

Total solutions for 8-Queens: 92

Requires Java 8 or later. The code uses no external dependencies — only java.lang standard library features. Change int n = 8 in main() to any positive integer to solve the N queens variant.

Iterative Alternative

While recursion is the natural fit for backtracking, you can implement an iterative version using an explicit stack. This avoids potential stack overflow for very large n and can be easier to debug in some environments:

import java.util.Stack;

public class NQueensIterative {

    public static int solve(int n) {
        int[] board = new int[n];
        java.util.Arrays.fill(board, -1);
        int row = 0;
        int count = 0;

        while (row >= 0) {
            int nextCol = board[row] + 1;
            boolean placed = false;

            while (nextCol < n) {
                if (isSafe(board, row, nextCol)) {
                    board[row] = nextCol;
                    placed = true;
                    break;
                }
                nextCol++;
            }

            if (placed) {
                if (row == n - 1) {
                    count++; // found a solution
                    board[row] = nextCol; // keep looking in same row
                    board[row] = -1;      // will look for nextCol+1 next iteration
                    // Force next iteration to continue from nextCol+1
                    board[row] = nextCol; // reset for the loop increment
                } else {
                    row++; // move to next row
                    board[row] = -1; // start fresh in new row
                }
            } else {
                board[row] = -1; // reset this row
                row--;           // backtrack to previous row
            }
        }
        return count;
    }

    private static boolean isSafe(int[] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col) return false;
            if (Math.abs(board[i] - col) == Math.abs(i - row)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("Solutions: " + solve(8)); // 92
    }
}

Frequently Asked Questions

How do I compile and run the Java 8 queens solution?

Save the code as NQueens.java, then run javac NQueens.java followed by java NQueens in a terminal. Java 8 or higher is required. No external libraries are needed.

Can this Java code solve N queens for any board size?

Yes. Change the value of n in the main() method to any positive integer. For n=10 there are 724 solutions; for n=12 there are 14,200. Large values (n>14) will take noticeably longer due to the factorial growth in search space.

Why is the board array initialized to -1 in Java?

Using -1 as a sentinel value for "no queen placed" makes it easy to detect uninitialized rows and is a common convention in backtracking implementations. Column indices are 0-based (0 to n-1), so -1 is always an invalid column and will never cause false safety conflicts.

Related Pages

8 Queens in Python

Complete Python backtracking solution with generator and set-based optimizations.

Read more

8 Queens in C++

C++ solution with bitwise optimization and compilation guide.

Read more

8 Queens Backtracking Guide

Algorithm theory, complexity analysis, and JS implementation.

Read more

Interactive Puzzle

Try solving the puzzle yourself interactively.

Read more

Learn Algorithms

Full learning guide covering strategies, history, and code.

Read more