Sicp exercise 2.42

Got bitten by a bug tonight... the bug to work a little bit more on sicp, so I went back to the 8 queens problem that had been giving me some hassle before and solved it. It's a fun problem and it seems like the solution I came up for the safety test was a bit different from the usual, so here we go.

For starters, the problem involves figuring out all the possible ways to set down n queens on an n*n chess board in such a manner that no queen is in check from another.

The solution to it involves breaking down the problem by working out the way to set down n-1 queens and trying to place a new queen in all possible positions in the next row, then filtering any out that are poorly placed. This recurses down to 0 queens placed from where it then builds up the queens.

The main routine is provided as part of the problem leaving the solver to work out how to represent boards, and how to check that a set of positions is good.

The code

;; Heres a solution with a recursive test based on the number of columns away the 
;; queen being tested against is
;; if the distance horizontally is the same as the vertical difference it's not 
;; valid
(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))
 
 
(define empty-board '())
 
 
(define (adjoin-position new-row k rest-of-queens)
  (append (list new-row) rest-of-queens))
 
 
(define (safe? k positions)
  (check-safe
   (car positions)
   1
   (cdr positions)))
 
 
;; Check the queens column position against that of all other columns
;; One if vertical distance = horizontal distance it's a diagonal hit
(define (check-safe position distance cols)
  (cond ((null? cols) #t)
 ((= (car cols) position) #f)
 ((= (- (car cols) distance) position) #f)
 ((= (+ (car cols) distance) position) #f)
 (else (check-safe position (+ distance 1) (cdr cols)))))

Auxiliary functions



Here are the auxiliary routines(pretty much as they are in sicp):

(define (flatmap proc seq)
  (accumulate append (list) (map proc seq)))
 
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
   (accumulate op initial (cdr sequence)))))
 
(define (enumerate-interval initial end)
  (if (> initial end)
      '()
      (cons initial (enumerate-interval (+ initial 1) end))))
  
 
(define (filter predicate sequence)
  (cond ((null? sequence) '())
 ((predicate (car sequence))
  (cons (car sequence)
        (filter predicate (cdr sequence))))
 (else (filter predicate (cdr sequence)))))

Everything else should be in GNU/MIT scheme.

Alternate solutions

Some other solutions can be found here, though I found many of them long-winded and no more clear. I posted my own solution there for good measure.