The O(n) Club: N-Queens Without The Emotional Damage

The O(n) Club: N-Queens Without The Emotional Damage

⚡ TL;DR

Need to park N queens on an N×N chessboard with zero drama? They can’t cross paths—no row, column, or diagonal showdowns. The brute-force method is just self-inflicted suffering (unless you like waiting for eternity). Here’s what you’ll end up regretting:

// Brute force, also known as "career sabotage":
for (every conceivable board where queen counts == N) {
    if (nobody's fighting) addToResults(board);
}

🧠 How Devs Usually Mess This Up

Classic rookie moves? First, thinking that putting queens row-by-row magically solves everything. Spoiler: diagonals exist. Second, finding just one arrangement and doing a happy dance—nope, most interviews want all possible boards, not your favorite. Finally, checking the entire board for every queen drop—a great way to make your backtracking function file for burnout benefits.

🔍 What’s Actually Going On

It’s a sneakily simple constraint satisfaction problem in disguise. Place one queen per row, but every new queen has to dodge all previous ones vertically and on both diagonals. If your algorithm is re-scanning the board looking for danger, it’s like a chef checking if the oven’s still hot—every ten seconds. Instead, keep tracked arrays for columns and each diagonal. Mark a spot as “unsafe,” slap down a queen, and move on. If you hit a dead end, clean up (backtrack), reset those arrays, and act like nothing ever happened. It’s therapy for algorithms.

🛠️ PseudoCode

• Set up your guard dogs: Arrays for columns and both diagonals, all “false” (nothing threatened yet).
• Backtrack from row 0: For each column in this row, only try spots that aren’t threatened:
  

  if (!cols[col] && !diag1[row-col+n-1] && !diag2[row+col]) {...}

• Put a queen: Flag the column and both diagonals as “taken”.
  

  cols[col] = diag1[row-col+n-1] = diag2[row+col] = true;

• Recurse to next row, keep going until row==n: That’s a legal board, so record the arrangement!
• Backtrack: Remove the queen and all threat flags. Pretend you never made the mistake.

💻 The Code

public class NQueens {
    public List<list>> solveNQueens(int n) {
        List<list>> solutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1];
        boolean[] diag2 = new boolean[2 * n - 1];
        backtrack(0, board, cols, diag1, diag2, solutions);
        return solutions;
    }
    private void backtrack(int row, char[][] board, boolean[] cols, boolean[] diag1, boolean[] diag2, List<list>> res) {
        int n = board.length;
        if (row == n) {
            List
<string> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            res.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n - 1; // for '\' diagonals
            int d2 = row + col;         // for '/' diagonals
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            backtrack(row + 1, board, cols, diag1, diag2, res);
            board[row][col] = '.';
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
}</string></list></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Mixed-up diagonal math leads to array index rage: diag1 is (row - col + n - 1); diag2 is (row + col).
• N = 2 and N = 3 are unsolvable (and so is hoping brute force will scale past N=12).
• Space: O(n²) for storing boards, O(n) for status arrays. Time: O(n!). There are faster ways, but Java recursion can’t do magic.
• If you love code golf or bit-twiddling, sure, use bitmasks—just be ready to explain it to HR when everyone else quits.

🧠 Interviewer Brain-Tattoo

“Backtracking isn’t guessing. It’s failing efficiently—which, in a way, is the essence of every code review.”