Implementation

This chapter implements subsets, permutations, and N-Queens in Python and walks through them line by line. Then it ports the same core routine, counting N-Queens solutions, to C++, Java, and TypeScript. Whatever the language, the structure is the same three lines: choose, explore, unchoose.

Subsets and permutations (Python)

def subsets(nums):
    result, path = [], []

    def dfs(start):
        result.append(path[:])            # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            dfs(i + 1)                    # explore: only pick after i
            path.pop()                    # unchoose

    dfs(0)
    return result


def permutations(nums):
    result, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):        # leaf: one full permutation
            result.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:                   # skip elements already taken
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

• subsets records a result at every node, not just at leaves. Because it only picks from start onward, [1, 2] and [2, 1] are never both produced.
• permutations cares about order, so it scans from the beginning every time and uses the used array to block elements already chosen. used[i] = False is the matching undo.
• Both functions store a copy with path[:].

N-Queens (Python)

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    queens, boards = [], []

    def place(row):
        if row == n:                                   # every row filled
            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                               # prune
            cols.add(c); diag.add(row - c); anti.add(row + c)
            queens.append(c)
            place(row + 1)
            queens.pop()
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return boards

for line in solve_n_queens(4)[0]:
    print(line)
# .Q..
# ...Q
# Q...
# ..Q.

• One queen goes in each row, so row is the depth of the tree.
• Three sets, cols, diag (row - c), and anti (row + c), make each conflict check O(1). Scanning every queen, as is_safe did in the previous chapter, costs O(n) per check.
• Values added to the sets when choosing must be removed when returning, so the next branch starts from a clean state.

Counting N-Queens solutions (C++)

The other languages show the same routine, counting solutions only. Column and diagonal numbers are small integers, so boolean arrays replace the sets.

#include <iostream>
#include <vector>

int n;
std::vector<bool> col, diag, anti;

int place(int row) {
    if (row == n) return 1;
    int count = 0;
    for (int c = 0; c < n; ++c) {
        if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
        col[c] = diag[row - c + n - 1] = anti[row + c] = true;
        count += place(row + 1);
        col[c] = diag[row - c + n - 1] = anti[row + c] = false;
    }
    return count;
}

int main() {
    n = 8;
    col.assign(n, false);
    diag.assign(2 * n - 1, false);
    anti.assign(2 * n - 1, false);
    std::cout << place(0) << "\n";  // 92
}

Since row - c can be negative, adding n - 1 maps it onto array indices from 0 to 2n - 2.

Counting N-Queens solutions (Java)

public class NQueens {
    static int n;
    static boolean[] col, diag, anti;

    static int place(int row) {
        if (row == n) return 1;
        int count = 0;
        for (int c = 0; c < n; c++) {
            if (col[c] || diag[row - c + n - 1] || anti[row + c]) continue;
            col[c] = diag[row - c + n - 1] = anti[row + c] = true;
            count += place(row + 1);
            col[c] = diag[row - c + n - 1] = anti[row + c] = false;
        }
        return count;
    }

    public static void main(String[] args) {
        n = 8;
        col = new boolean[n];
        diag = new boolean[2 * n - 1];
        anti = new boolean[2 * n - 1];
        System.out.println(place(0)); // 92
    }
}

Counting N-Queens solutions (TypeScript)

function countNQueens(n: number): number {
  const col = new Array<boolean>(n).fill(false);
  const diag = new Array<boolean>(2 * n - 1).fill(false);
  const anti = new Array<boolean>(2 * n - 1).fill(false);

  const place = (row: number): number => {
    if (row === n) return 1;
    let count = 0;
    for (let c = 0; c < n; c++) {
      const d = row - c + n - 1;
      if (col[c] || diag[d] || anti[row + c]) continue;
      col[c] = diag[d] = anti[row + c] = true;
      count += place(row + 1);
      col[c] = diag[d] = anti[row + c] = false;
    }
    return count;
  };

  return place(0);
}

console.log(countNQueens(8)); // 92

Summary

• Subsets are recorded at every node; permutations and N-Queens are recorded at leaves.
• Turning conflict checks into set or array lookups makes each check O(1).
• Whatever state you change when choosing must be restored, in the same way, when you return.