How to Solve the N-Queen Problem

Introduction

The N-Queen Problem is a classic puzzle that asks how to place N queens on a chessboard with dimensions N×N such that none of them can attack each other. No two queens should be placed on the same row, column, or diagonal. The problem is a popular example for demonstrating recursive algorithms, especially the use of backtracking (see also Permutations of a String).

Overview of N-Queen Problem

In chess, the queen is the most powerful piece because it can move in straight lines across rows, columns, and both diagonals. When trying to arrange multiple queens on a board, the goal is to ensure their paths do not intersect. The N-Queen Problem explores how many ways such an arrangement is possible for a given N.

Solution Strategy

A practical way to solve this problem is through backtracking. This method involves placing a queen one step at a time and exploring further only if the current state is valid. If a conflict arises, we reverse the last step (backtrack) and try a different route. By repeating this process, we can identify all the valid solutions.

The idea is to build the solution row by row, ensuring that every new queen is placed in a column that doesn’t lead to an attack from any of the previously placed queens.

Java Code Example for N-Queen Problem

Here is an original Java program that computes and displays all the valid placements for N queens using backtracking.

public class QueenPlacement {

    private int size;

    public QueenPlacement(int n) {
        this.size = n;
    }

    public void solve() {
        int[] positions = new int[size];
        placeQueen(0, positions);
    }

    private void placeQueen(int currentRow, int[] positions) {
        if (currentRow == size) {
            showBoard(positions);
            return;
        }

        for (int column = 0; column < size; column++) {
            if (canPlace(currentRow, column, positions)) {
                positions[currentRow] = column;
                placeQueen(currentRow + 1, positions);
            }
        }
    }

    private boolean canPlace(int row, int col, int[] positions) {
        for (int previousRow = 0; previousRow < row; previousRow++) {
            int previousCol = positions[previousRow];

            boolean sameColumn = previousCol == col;
            boolean sameDiagonal = Math.abs(previousCol - col) == Math.abs(previousRow - row);

            if (sameColumn || sameDiagonal) {
                return false;
            }
        }
        return true;
    }

    private void showBoard(int[] positions) {
        for (int row = 0; row < size; row++) {
            for (int col = 0; col < size; col++) {
                if (positions[row] == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 4; // Change this value for different board sizes
        QueenPlacement queenSolver = new QueenPlacement(n);
        queenSolver.solve();
    }
}

Output Example for a 4×4 Board

When you run the program with n = 4, you will get the following two valid layouts where four queens are placed with no threats:

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

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

Each “Q” marks a queen’s position, and each “.” represents an empty square. These solutions show how queens can be placed without sharing any row, column, or diagonal.

Conclusion

The N-Queen Problem is more than a game. It’s a great example of recursive thinking and the power of backtracking algorithms. By trying possibilities one step at a time and undoing decisions when necessary, we can find all valid configurations even for larger board sizes. Understanding this problem sharpens problem-solving skills and lays a foundation for tackling more complex constraint-based challenges.

You can find the example code on Github.