Cracking The Coding Interview Together – Problem 8.12: Eight Queens

Picture this: you are sitting in a system design and algorithms interview. The interviewer smiles, slides a whiteboard marker across the desk, and asks you to place eight deadly pieces on a standard 64-square grid without letting any of them cross paths. It sounds like a game of tactical chess, but it is actually one of the most fundamental algorithmic challenges you will face in your career.

At first glance, it looks like a brute-force nightmare. How do we evaluate millions of combinations without crashing our call stack or burning CPU cycles? The secret lies in a classic computer science technique that turns an exponential explosion into a graceful, pruned traversal. Today, we are going to break down Problem 8.12 from Cracking the Coding Interview: the Eight Queens puzzle. By the end of this post, we will build a production-ready, clean Java solution together, dissecting every optimization along the way.

Problem Statement

Our objective is straightforward to state but deceptively complex to solve. We need to write an algorithm to print all possible ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column, or diagonal.

More formally:

• No two queens can occupy the same row.
• No two queens can occupy the same column.
• No two queens can occupy the same diagonal (both major and minor diagonals).

Our operational goal is not just to find one valid configuration, but to generate and output all distinct valid arrangements efficiently.

Analyze the Problem Together

Let us break down the constraints and look for the 'Aha!' conflict. A naive approach would be to iterate through all 64 squares on the board and choose 8 squares to place our queens. The total number of ways to choose 8 squares out of 64 is represented by the binomial coefficient:

C(64, 8) = 4,426,165,368

Over four billion combinations! If we validate each board configuration from scratch, checking rows, columns, and diagonals, our algorithm will grind to a halt. That is entirely unacceptable for a production environment or a timed interview.

Can we do better? Absolutely. Since we know that no two queens can share the same row, we can simplify our state space immediately. If we place exactly one queen per row, we reduce our choices drastically. Instead of picking 8 arbitrary squares, we simply need to decide which column to place the queen in for each of the 8 rows.

This insight shrinks our search space from over 4 billion combinations down to 8⁸ (which is 16,777,216). But we can prune the tree even further. By enforcing the rule that no two queens share a column or a diagonal as we place them row by row, we eliminate invalid subtrees before we even explore them. This technique is called backtracking.

Questions for the Interviewer

Before we write a single line of code, a senior engineer always pauses to clarify requirements and boundaries. Here are the questions we should ask our interviewer:

• Scale and Generalizability: Should our solution support an arbitrary N x N chessboard, or is it strictly locked to an 8x8 grid?
• Output Format: How do you want the board configurations represented? Should we return a list of integer arrays (where the index represents the row and the value represents the column), or visual string grids?
• Memory Constraints: Since we are generating all valid permutations, should we stream the results via a callback/iterator to protect heap memory, or is returning a collected list acceptable?

For our implementation today, we will design a flexible solution that handles an arbitrary N x N board and returns a clean collection of results.

Think About the Solution

Our high-level architecture relies on a recursive backtracking function. We will pass a single array, say Integer[] columns, of size N. The index of the array represents the row, and the value stored at that index represents the column where the queen is placed. This single data structure is brilliantly space-efficient and inherently guarantees that no two queens share a row.

As we move down row by row, for a given row, we attempt to place a queen in every possible column (from 0 to N-1). Before committing to a position, we validate the choice against all previously placed queens. If the position is safe, we recurse to the next row. If we reach a point where no valid placement exists, the recursion naturally unwinds—we backtrack—and we try the next available column in the previous row.

Let us quickly map out our helper validation logic:

• Column Check: Two queens share a column if their column values are identical.
• Diagonal Check: Two queens share a diagonal if the absolute difference between their row indices equals the absolute difference between their column indices. (i.e., Math.abs(row1 - row2) == Math.abs(col1 - col2)).

Write Code and Explain

Let us look at the production-ready Java implementation:

import java.util.ArrayList;
import java.util.List;

public class EightQueensSolver {

    private static final int GRID_SIZE = 8;

    /**
     * Public entry point to find all valid configurations.
     *
     * @return A list of valid board configurations.
     */
    public List<Integer[]> solveNQueens() {
        List<Integer[]> results = new ArrayList<>();
        Integer[] columns = new Integer[GRID_SIZE];
        placeQueens(0, columns, results);
        return results;
    }

    /**
     * Core recursive backtracking method.
     *
     * @param row     The current row we are placing a queen on.
     * @param columns Array tracking the column position for each row.
     * @param results Accumulator list for valid configurations.
     */
    private void placeQueens(int row, Integer[] columns, List<Integer[]> results) {
        // Base case: If we have successfully placed queens for all rows, save the result
        if (row == GRID_SIZE) {
            results.add(columns.clone());
            return;
        }

        // Try placing a queen in every column for the current row
        for (int col = 0; col < GRID_SIZE; col++) {
            if (checkValid(columns, row, col)) {
                columns[row] = col; // Place the queen
                placeQueens(row + 1, columns, results); // Recurse to the next row
                // Note: We don't explicitly need to clear columns[row] because
                // it gets overwritten in the next iteration of the loop.
            }
        }
    }

    /**
     * Validates if a proposed queen placement conflicts with any existing queens.
     *
     * @param columns Current board state.
     * @param row     Proposed row.
     * @param col     Proposed column.
     * @return True if safe, false otherwise.
     */
    private boolean checkValid(Integer[] columns, int row, int col) {
        for (int previousRow = 0; previousRow < row; previousRow++) {
            int previousCol = columns[previousRow];

            // Check if columns match (same column conflict)
            if (previousCol == col) {
                return false;
            }

            // Check diagonals: absolute difference in rows equals absolute difference in cols
            int rowDistance = Math.abs(row - previousRow);
            int colDistance = Math.abs(col - previousCol);
            if (rowDistance == colDistance) {
                return false;
            }
        }
        return true;
    }
}

Let us walk through how this code executes step by step:

1. We initialize our public method solveNQueens(), which creates an array of size 8. We kick off our recursion with row = 0.

2. Inside placeQueens(), our base case checks if row == GRID_SIZE. When we hit row 8, it means we have successfully placed 8 queens without violating any rules. We clone the current columns array and add it to our results list.

3. If we are not at the base case, we iterate through every possible column from 0 to 7. For each column, we invoke checkValid().

4. The checkValid() method inspects all previously placed queens (from row 0 up to row - 1). It checks whether any previous queen shares the same column or lies on the same diagonal. If any conflict is found, it returns false.

5. If the placement is safe, we assign columns[row] = col and immediately recurse into row + 1. When the recursive call finishes or backtracks, the loop continues to test the next column option.

Time & Space Complexity

Let us analyze the computational trade-offs of our approach:

• Time Complexity: O(N!). While the upper bound of exploring every row permutation is O(N^N), our strict validation prunes invalid branches immediately. For N=8, the total number of valid board configurations is precisely 92, and the algorithm evaluates a tiny fraction of the total search space, executing in mere milliseconds.
• Space Complexity: O(N). The call stack grows to a maximum depth of N (the number of rows), and our columns array takes O(N) space. This is extremely memory-efficient.

Why This Problem Matters (The Senior Perspective)

At first glance, the Eight Queens problem feels like an academic puzzle designed to torture computer science students. But as senior engineers, we recognize it as the canonical introduction to Constraint Satisfaction Problems (CSPs) and State Space Search.

The backtracking pattern you learned here is the exact same foundational principle powering automated routing engines, scheduling systems, Sudoku solvers, and compiler register allocation. Understanding how to prune search trees effectively separates junior engineers—who write brute-force loops that time out in production—from senior engineers who reason about state spaces and algorithmic boundaries.

Final Thoughts

Mastering backtracking is a rite of passage in your software engineering journey. By breaking down the problem constraints early, we transformed an impossible search space into an elegant, highly performant recursive solution.

I encourage you to take this code, plug it into your local IDE, and try optimizing the checkValid method using bit manipulation for O(1) conflict checks—a classic interview follow-up! Keep building, keep questioning, and happy coding!