Printing all solutions in N-Queen Problem

The problem, simply

A chess queen attacks every square in her row, her column, and both of her diagonals, as far as the board goes.

You get a number n. Put n queens on an n by n board so that no two queens attack each other. Give back every such board, drawn as rows of text where Q is a queen and . is empty.

A story to remember it

Picture it

Examples

Way 1: the simple way

Two queens in one row always attack, so each row gets exactly one queen. Fill the rows from top to bottom. Before placing a queen, look up the column and both diagonals above it, square by square.

1. If all rows are filled, copy the board into the answers.
2. For each column in the current row, scan upward: straight up, up left, and up right.
3. If no queen is seen, place one, fill the next row, then remove it.

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        List<List<String>> result = new ArrayList<>();
        solve(0, board, result);
        return result;
    }

    private void solve(int row, char[][] board, List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            List<String> copy = new ArrayList<>();
            for (char[] r : board) copy.add(new String(r));
            result.add(copy);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 'Q';
                solve(row + 1, board, result);
                board[row][col] = '.';                 // take the queen back
            }
        }
    }

    private boolean isSafe(char[][] board, int row, int col) {
        int n = board.length;
        for (int i = row - 1; i >= 0; i--) if (board[i][col] == 'Q') return false;    // up
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;                                      // up left
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
            if (board[i][j] == 'Q') return false;                                      // up right
        return true;
    }
}

How long it takes: the search tree has at most n choices in the first row, fewer than n - 1 safe ones in the next, and so on, roughly n! placements. Each safety scan costs O(n), so O(n! * n). Extra room: the board, O(n^2).

Way 2: the clever way

Scanning is wasted work. Every square on the same column, or on the same slanted line, shares a simple number:

• Same column: the same c.
• Same line going down to the right: the same r - c.
• Same line going up to the right: the same r + c.

So keep three rows of yes or no switches: is this column taken, is this down line taken, is this up line taken. Checking a square becomes three look-ups.

1. For row r, try each column c. It is safe if col[c], down[r - c + n - 1] and up[r + c] are all off.
2. Place the queen: remember its column for row r, and switch the three on.
3. Fill row r + 1. Then switch the three off again.
4. When all rows are filled, draw the board from the remembered columns.

import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        place(0, n, new int[n], new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], result);
        return result;
    }

    private void place(int r, int n, int[] queenCol, boolean[] col, boolean[] down, boolean[] up,
                       List<List<String>> result) {
        if (r == n) {
            result.add(draw(queenCol));
            return;
        }
        for (int c = 0; c < n; c++) {
            int d = r - c + n - 1;                      // same number along a down-right line
            int u = r + c;                              // same number along an up-right line
            if (col[c] || down[d] || up[u]) continue;   // attacked
            queenCol[r] = c;
            col[c] = down[d] = up[u] = true;
            place(r + 1, n, queenCol, col, down, up, result);
            col[c] = down[d] = up[u] = false;           // take the queen back
        }
    }

    private List<String> draw(int[] queenCol) {
        int n = queenCol.length;
        List<String> board = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queenCol[r]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

How long it takes: the same tree, about O(n!) placements, but each check is O(1) now. Drawing each answer costs O(n^2), which is the size of the output. Extra room: the switches and the column per row, O(n).

Watch out for

• Checking the whole row too. One queen per row is built in, so it never needs checking.
• Checking squares below the current row. Nothing has been placed there yet.
• Forgetting to switch everything back off. Later branches then see attacks that are not there.

What interviewers ask next

• Only count the boards (N-Queens II). Keep the three switch rows as bits in three integers. The free columns are ~(cols | down | up) & ((1 << n) - 1), and you take them one by one with free & -free. This is very fast.
• Use the mirror. Every board has a mirror image, so only try the left half of the first row, double the count, and handle the middle column for odd n.
• Find just one board for n = 1000. Backtracking is too slow. There are known formulas that place the queens directly, or a repair method: start anywhere and keep moving the most attacked queen.
• Why one queen per row? Two queens in a row attack each other, and there are n rows for n queens, so each row has exactly one.

Remember this

Grown-up words: the bossy lines are attack lines (column, main diagonal and anti diagonal), the switches are boolean arrays or bitmasks, taking a queen back is backtracking, and skipping attacked squares is pruning.