N Queens

In my free time between jobs I’ve been reading through Structure and Interpretation of Computer Programs (SICP) again. Working through some of the problems is good interview prep and there’s always some interesting ideas that stick out no matter how many times I’ve read through the book. This time I had a lot of fun with the N queens problem. It’s been a while since I wrote up a solution for the N queens problem and the way SICP solves it is pretty elegant. I also thought it would be fun to use it to write up a small React app to visualize solutions.

When I first learned about the N queens problem, I was taught to think of it as a recursive backtracking problem similar to the sudoku solver that I wrote up years ago. The first time I wrote a solution for the N queens problem it followed a very similar structure as the sudoku solver. The algorithm would place a queen on the board one at a time and if it ran into an invalid board it would backtrack to the last valid position and continue from there trying a queen in a new spot. The SICP solution is slightly different in that it goes through the board column by column and generates all valid solutions up to that column then continues to the next column.

The lisp code that SICP provides in exercise 2.42 is below. The exercise from the book is to implement the safe? function which determines whether a new queen in column k is safe (ie. not being attacked by any other queens) and thus the position is valid. Part of the challenge of the exercise is determining how the board and positions are represented and also writing the definition for adjoin-position which adds a new queen to the board. enumerate-interval is a function similar to python’s range function.

(define (queens board-size)
    (define (queen-cols k)
        (if (= k 0)
            (list empty-board)
            (filter
                (lambda (positions) (safe? k positions))
                (flatmap
                    (lambda (rest-of-queens)
                    (map (lambda (new-row)
                        (adjoin-position
                            new-row k rest-of-queens))
                        (enumerate-interval 1 board-size)))
                    (queen-cols (- k 1))))))
    (queen-cols board-size))

Since I wanted to visualize the problem with React, I implemented the same algorithm in TypeScript. This has the added benefit of making it clear how the board and positions are represented. So here’s the TypeScript implementation. We will represent each queen as a tuple of its row and column on the board. Note that the SICP algorithm uses one-indexed rows and columns so one corner of the board is (1,1) and ther other is (board-size, board-size). Using this representation the postion of queens is a list of coordinates.

type Coordinate = [number, number];
type Position = Coordinate[];

Slight naming differences aside, this is the algorithm implemented in TypeScript. The function queenColumn generates valid positions for the nth column. To do this it generates valid positions for the n-1th column starting with an empty position when n = 0. To generate the valid positions it simply adds a queen to every row in the new column then filters out any positions where the queen added to the new column is under attack from any of the previously placed queens.

function nQueens(n: number): Position[] {
    function queenColumn(column: number): Position[] {
        if (column === 0) {
            return [[]];
        }
        return queenColumn(column - 1)
          .flatMap(rest =>
                   range(1, n + 1)
                    .map(newRow =>
                          [...rest, [newRow, column]]))
          .filter(safe(column));
    }
    return queenColumn(n);
}

As noted in SICP, there’s a slight optimization where we only have to check whether the queen in the new column is under attack since the way positions are generated means that none of the other queens are attacking each other. So the safe function takes an argument with the current column and only checks the queen in that column against the other queens.

function safe(col: number){
    function isAttacking(a: Coordinate, b: Coordinate) {
        const [ax, ay] = a;
        const [bx, by] = b;
        // Same row, same column or same diagonal
        return ax === bx || ay === by || Math.abs(ax - bx) === Math.abs(ay - by);
    }
    return (positions: Coordinate[]) => {
        const current = positions[col - 1];
        const others = positions.slice(0, col - 1);
        for (const other of others) {
            if (isAttacking(current, other)) {
                return false;
            }
        }
        return true;
   }
}

Here’s the visualization of the solutions up to a board size of 11.

See the Pen N-Queens by Jake Burkhead (@jlburkhead) on CodePen.