HOWTO · Java
How to Solve Eight Queens Problem in Java
This tutorial demonstrates the eight queens problem in Java.
On this page
This tutorial shows how to solve the eight queens problem in Java with backtracking. The goal is to place eight queens on an 8 × 8 chessboard so that no two queens share a row, column, or diagonal. The solver below finds one arrangement and stops; it does not enumerate every solution or implement a board of arbitrary size.
How Backtracking Solves the Eight Queens Problem
Place one queen in each column, moving from the leftmost column to the right. Since each recursive call handles a new column, the solver never needs to test whether two queens share a column. For each column, it tries rows in order and checks the candidate against queens already placed in earlier columns.
A candidate is safe when every earlier queen is in a different row and its row distance differs from its column distance. Equal row distance means the same row; equal absolute row and column distances mean the same diagonal. If a candidate passes both checks, record its row and recursively solve the next column.
The recursive call either completes the board or reaches a column where every row conflicts. In that case, it returns false. The caller then clears its recorded row and tries the next candidate. This undo step is essential: without it, a failed branch would leave a queen on the board and incorrectly affect later checks. Reaching column eight means that all eight columns received a safe queen, so the search can stop successfully.
Implement the Solver in Java
The queenRow array stores one row index per column. A value of -1 means that the column has not been assigned. The solve method checks rows in order, records a safe choice before recursing, and restores the unassigned marker when that choice leads nowhere. Its Boolean return value carries success back through the recursive calls.
Run this example:
public class EightQueens {
private static final int SIZE = 8;
private static final int[] queenRow = new int[SIZE];
private static boolean isSafe(int row, int column) {
for (int previousColumn = 0; previousColumn < column; previousColumn++) {
int previousRow = queenRow[previousColumn];
if (previousRow == row
|| Math.abs(previousRow - row)
== Math.abs(previousColumn - column)) {
return false;
}
}
return true;
}
private static boolean solve(int column) {
if (column == SIZE) {
return true;
}
for (int row = 0; row < SIZE; row++) {
if (isSafe(row, column)) {
queenRow[column] = row;
if (solve(column + 1)) {
return true;
}
queenRow[column] = -1;
}
}
return false;
}
public static void main(String[] args) {
for (int column = 0; column < SIZE; column++) {
queenRow[column] = -1;
}
if (!solve(0)) {
System.out.println("No arrangement found.");
return;
}
for (int row = 0; row < SIZE; row++) {
for (int column = 0; column < SIZE; column++) {
System.out.print(queenRow[column] == row ? "Q " : ". ");
}
System.out.println();
}
}
}
The code uses only Java’s standard library. isSafe scans the columns that already contain queens, so each check considers the current partial arrangement. When a recursive call succeeds, each caller immediately returns true without undoing its choice; those recorded rows are the solution that main prints.
Run the Program and Read the Output
Save the code in a file named EightQueens.java. With a Java Development Kit installed, compile it from that directory with javac EightQueens.java, then run it with java EightQueens. The program prints an 8 × 8 text board. Each Q marks a queen and each period marks an unoccupied square. Read across rows and down columns: every row and column has one queen, and the diagonal safety checks ensure no pair shares a diagonal.
The chosen arrangement depends on the row order in the loop. The program returns as soon as it finds its first complete arrangement, so a different search order can produce a different valid board. The printed board is selectable text, and the example does not rely on a screenshot or a separate image.
Complexity and Limitations
There are at most eight choices for the first column, then at most seven unused rows for the next, and so on. This bounds the search by O(N!) candidate placements for an N × N board when one queen is placed per column. For each candidate, isSafe scans up to N earlier columns, adding an O(N) check; a useful upper bound for this implementation is therefore O(N · N!) time. Pruning unsafe partial boards usually avoids exploring many of those candidates, but does not change that broad bound.
The row array uses O(N) storage for the generalized form, and the recursive calls use up to O(N) stack space. This implementation stores an 8 × 8 board only as eight row indexes rather than a Boolean matrix, so its search state is O(N) rather than O(N²). It is a small fixed-size demonstration: the constant is eight, and the solver reports the first arrangement instead of counting or listing every solution.