N Queens

The problem

You are given a whole number n. Place n queens on a board of n rows and n columns so that no queen attacks another. A queen attacks every square in its row, in its column and on its two diagonals. Return every way to do this, each as a list of n strings, one per row from top to bottom, with Q for a queen and a dot for an empty square. The boards may come in any order. If there is no way, return an empty list.

What to write

function solve(n: number): string[][]

Input
n = 4

Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Input
n = 1

Output
[["Q"]]

Constraints

1 ≤ n ≤ 9.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The board is at most 9 by 9. Two queens can never share a row, and there are as many queens as rows, so every row holds exactly one queen. The same holds for the columns.

2. Hint 2: Ask a smaller question

   On a 4 by 4 board, put a queen in the top left corner. Which squares of the second row are still free? Put a queen on the first of them and look at the third row. What do you find, and which queen would you move first?

3. Hint 3: Name the pattern

   A board is a series of choices, one column per row, and a bad choice may only show up some rows later. That signals backtracking: put a queen on a square that is not attacked, go on to the next row, and when a row has no free square, take the last queen off and move it. Read the lesson on backtracking.

4. Hint 4: State the invariant

   While the search fills a row, every row above it holds exactly one queen, and no two of those queens attack each other. The columns and diagonals you have noted as taken belong to exactly those queens, no more and no fewer.

5. Hint 5: Sketch the pseudocode

   Keep three sets: columns, row minus column, row plus column. place(row): if row equals n, save a copy of the board and return. For each column: skip the square if its column or one of its diagonal numbers is stored. Otherwise store all three, add this row to the board, call place(row + 1), then undo all four. Start: place(0).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Place one queen per row and track occupied columns and the two diagonal keys, row minus column and row plus column.

The slow way

Put one queen in each row in every possible way and check each finished board for attacks. With n choices in each of n rows, that is 16,777,216 boards for n = 8, and only 92 of them pass. It is correct, but a board whose first two queens already attack each other is still filled to the last row before it is thrown out.

The insight

A queen that is attacked stays attacked, whatever is placed later. So fill the board from the top row down and test a square before a queen goes on it. Along one diagonal, row minus column never changes; along the other, row plus column never changes. Noting those two numbers and the column turns the test into three lookups.

Step by step

1. Keep the boards found and the rows of the board being built. One list collects the finished boards. The other holds the text of each row filled so far, from the top, and it grows and shrinks as queens are placed and taken off.
2. Remember which columns and diagonals already hold a queen. Three sets answer "is this square attacked?" without scanning the board. All squares of one diagonal share the value row minus column, and all squares of a diagonal in the other direction share row plus column.
3. Every row has a queen: save a copy of the board. Each queen was placed on a square that no earlier queen attacks, so a full board is a valid one. A copy is saved because the working rows keep changing afterwards.
4. In this row, try each square that no earlier queen attacks. Rows are filled one at a time, so the row is never shared. A square is attacked when its column or one of its two diagonal numbers is already in a set, and such a square is skipped.
5. Place a queen: record its column, both diagonals and its row. From now on these three numbers block every square the new queen attacks in the rows below. The row's text has Q in this column and dots everywhere else, as the answer asks.
6. Fill the rows below, then take the queen off the board again. With this queen fixed, the rows below are a smaller version of the same task. Afterwards all four records are undone, so the next column of this row starts from the board as it was.
7. Start at the top row with an empty board. No queen is placed yet, so every square of the top row is free. When this first call returns, every placement has been tried or ruled out, and the boards found are returned.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Keep the boards found and the rows of the board being built
  const out = [],
    path = [];
  // 2. Remember which columns and diagonals already hold a queen
  const cols = new Set(),
    down = new Set(),
    up = new Set();
  function visit(r) {
    // 3. Every row has a queen: save a copy of the board
    if (r === n) {
      out.push([...path]);
      return;
    }
    // 4. In this row, try each square that no earlier queen attacks
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || down.has(r - c) || up.has(r + c)) continue;
      // 5. Place a queen: record its column, both diagonals and its row
      cols.add(c);
      down.add(r - c);
      up.add(r + c);
      path.push(".".repeat(c) + "Q" + ".".repeat(n - c - 1));
      // 6. Fill the rows below, then take the queen off the board again
      visit(r + 1);
      path.pop();
      cols.delete(c);
      down.delete(r - c);
      up.delete(r + c);
    }
  }
  // 7. Start at the top row with an empty board
  visit(0);
  return out;
}

function solve(n: number): string[][] {
  // 1. Keep the boards found and the rows of the board being built
  const out: string[][] = [],
    path: string[] = [];
  // 2. Remember which columns and diagonals already hold a queen
  const cols = new Set<number>(),
    down = new Set<number>(),
    up = new Set<number>();
  function visit(r: number): void {
    // 3. Every row has a queen: save a copy of the board
    if (r === n) {
      out.push([...path]);
      return;
    }
    // 4. In this row, try each square that no earlier queen attacks
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || down.has(r - c) || up.has(r + c)) continue;
      // 5. Place a queen: record its column, both diagonals and its row
      cols.add(c);
      down.add(r - c);
      up.add(r + c);
      path.push(".".repeat(c) + "Q" + ".".repeat(n - c - 1));
      // 6. Fill the rows below, then take the queen off the board again
      visit(r + 1);
      path.pop();
      cols.delete(c);
      down.delete(r - c);
      up.delete(r + c);
    }
  }
  // 7. Start at the top row with an empty board
  visit(0);
  return out;
}

def solve(n):
    # 1. Keep the boards found and the rows of the board being built
    result = []
    path = []
    # 2. Remember which columns and diagonals already hold a queen
    cols = set()
    diagonals = set()
    anti_diagonals = set()

    def backtrack(r):
        # 3. Every row has a queen: save a copy of the board
        if r == n:
            result.append(path.copy())
            return
        # 4. In this row, try each square that no earlier queen attacks
        for c in range(n):
            if c in cols or r - c in diagonals or r + c in anti_diagonals:
                continue
            # 5. Place a queen: record its column, both diagonals and its row
            cols.add(c)
            diagonals.add(r - c)
            anti_diagonals.add(r + c)
            path.append("." * c + "Q" + "." * (n - c - 1))
            # 6. Fill the rows below, then take the queen off the board again
            backtrack(r + 1)
            path.pop()
            cols.remove(c)
            diagonals.remove(r - c)
            anti_diagonals.remove(r + c)

    # 7. Start at the top row with an empty board
    backtrack(0)
    return result

Example 1, traced

Input
n = 4

Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Why it works

A valid board has one queen in each row. The search tries every column in the top row and, below every queen placed, every square that is still free, so each valid board is reached exactly once. An invalid board is never completed: a queen only goes on a square that no earlier queen attacks, and attacks go both ways.

Time and space

Time O(n! · n) upper bound, extra space O(n + output). The first row has n columns to choose from, the next n - 1, down to 1: multiplied, that is n! boards at most. A call scans n columns: O(n! · n), an upper bound, since diagonals stop most attempts early. Sets and calls take O(n) besides the output.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Take the queen off completely: free its column and both diagonals and remove its row. If one of the three sets keeps its entry, free squares look attacked later, and n = 4 returns no board at all.
• Test both diagonals, each with its own number. With the row minus column test alone, queens can still line up along the other diagonal, and n = 4 returns 7 boards instead of 2.
• A diagonal attack can come from any row above, not only the nearest. A test against the queen one row up is right up to n = 4, but returns 14 boards instead of 10 for n = 5.

Pattern

Backtracking. Builds on Valid Sudoku and Permutations.

Keep going