Exercise 2.42

Read Exercise 2.42 ~ Solution

(define empty-board nil)

(define (adjoin-position row positions)
  (cons row positions))

(define (safe? position)

  (define board-size (length position))

  (define (safe-diagonal? position)

    ; test the position for the newly placed queen
    (define (col-safe? new-row col position)
      (cond ((> col board-size) true)
            ((= (abs (- new-row (car position)))
                ; the new qeeen's position is always on column 1
                (abs (- col 1))) false)
            (else (col-safe? new-row (+ col 1) (cdr position)))))

    ; the new queen's position is always in column 1
    ; so the initial column to check is always 2
    (col-safe? (car position) 2 (cdr position)))

  (define (safe-horizontal? position)
    ; does the new row (car) appear anywhere else?
    (not (member (car position) (cdr position))))

  (or (= (length position) 1)  ; 1x1 board
      (and (safe-horizontal? position)
           (safe-diagonal?   position))))

My basic strategy for writing safe? didn’t change, but I went through several horrendous versions of safe-diagonal? and I’m still not completely happy with it. Is it good-enough? – let me know.

(display (queens 1))
((1))

(display (queens 2))
()

(display (queens 3))
()

(display (queens 4))
((3 1 4 2) (2 4 1 3))

(display (queens 5))
((4 2 5 3 1) (3 5 2 4 1) (5 3 1 4 2) (4 1 3 5 2) (5 2 4 1 3) (1 4 2 5 3) (2 5 3 1 4) (1 3 5 2 4) (3 1 4 2 5) (2 4 1 3 5))

(length (queens 8))
92

Only 92 solutions to the 8 queens problem?
According to wikipedia, yes.

(length(queens 9))
352

(length(queens 9))
352

(length(queens 10))
724

(length(queens 11))
2680

(length(queens 12))
14200

12 queens took about 30 seconds on my desktop machine and caused the virtual machine I usually use for doing these problems to completely grind to a halt, due to paging I think, needing a hard reset :)
I really enjoyed this exercise.