The 8 queens puzzle is an almost two centuries problem that was proposed by Max Bezzel in 1848. Although I had encountered it in the past in some combinatorics classes, I was recently reminded of it while studying SICP. In chapter 2.2.3 and in exercise 2.42 it is asked to implement a procedure queens which solves the problem for any n*n chessboard board.

The main idea of the problem is placing 8 (or n) queens, in an 8*8 (or n*n) chessboard so that no queen is in check from any other, meaning in the same row, column or diagonal. Visualizing the problem a bit better, check the board and try to solve the problem here:

There are many algorithmic solutions for this problem, some of which are explained in Wikipedia entry for the puzzle. In SICP it is proposed to find all solutions by means of recursion, so that we check the nth queen placement given we have a n-1 column board where n-1 queens are placed successfully.

The skeleton given in the book and some helper functions follow: 

(define (enumerate-interval low high)
       (if (> low high)
           '()
           (cons low (enumerate-interval (+ low 1) high))))

(define (accumulate op initial sequence)
       (if (null? sequence)
           initial
           (op (car sequence)
               (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

(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))

So to start filling in the gaps we need to decide on the representation of our board and positions. I choose to represent a position of two elements and a board as a list of such positions: 

(define (pos x y)
  (list x y))

(define (pos-row pos)
  (car pos))

(define (pos-col pos)
  (cadr pos))

(define (pos-diagonal? pos1 pos2)
  (= (abs (- (pos-row pos1) (pos-row pos2)))
     (abs (- (pos-col pos1) (pos-col pos2)))))

(define empty-board '())

Then we have to define the adjoin-position procedure that adds a new position to a set of positions (board) and of course a safe? procedure that checks if a set with board-positions is valid. Return to the definition of queens and check that every time we need only check the safety of the newly placed queens at the kth column. The rest are already checked. 

(define (adjoin-position row col set)
  (cons (pos row col) set))

(define (safe? set board-size)
  "The newest queen, the one we need to check for safety, is in the car of set."
  (define (attack? pos1 pos2)
      (or (= (pos-row pos1) (pos-row pos2))
          (pos-diagonal? pos1 pos2)))
  (let* ((new-queen (car set))
         (rest (cdr set)))
    (accumulate (lambda (new-pos results)
                  (and (not (attack? new-queen new-pos))
                       results))
                #t
                rest)))

Or algorithm is checking each row for every column and eagerly rejects the solutions when a column of no safe positions appear. In this way it can be quite performant and gives solutions of boards up to size 12 in acceptable time.

One way we could improve the performance is to change our data representation for the positions from a list to just a number. This way a board can be a single list and by so we will reduce the amount of cons cells created.

To do so we need to think about how to check the diagonal attacks: 

(define (adjoin-position row col set)
  (cons row set))

(define (safe? k positions)
  (let ((new-queen (car positions)))
    (define (iter rest diagonal anti-diagonal)
      (cond ((null? rest) #t)
            ((= new-queen (car rest)) #f)
            ((= diagonal (car rest)) #f)
            ((= anti-diagonal (car rest)) #f)
            (#t (iter (cdr rest)
                      (- diagonal 1)
                      (+ anti-diagonal 1)))))
    (iter (cdr positions) (- new-queen 1) (+ new-queen 1))))

(length (queens 12))

With this representation we can reach up to (queens 13) and our program is faster and less memory hungry. This optimization was possible by working with abstract procedures that allow us to change the underlying data forms. To change the program we needed only to provide two new functions.

SICP is surely a great book, and I think it's really worth spending the time on studying it deeply. If I could propose any book to software engineers it would be this.

🦉