SICP問題2.42

SICP

エイトクイーンパズル
教科書で定義済な部分

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

empty-boardの定義

(define empty-board
  (list))

adjoin-positionの定義

(define (adjoin-position new-row k rest-of-queens)
  (cons (list new-row k) rest-of-queens)
  )

フィルタsafe?の定義。最初はこんな感じで他の手続きの動きを確認。

(define (safe? k positions)
  (= 1 1))

で、ちゃんと考えてみる。
8クイーンの解法では以下のケースがNGになるらしい

  • 同じ行, 列が既に存在する場合はNGで、
  • 行+列-1(右上がり斜めのライン 1 <= (行+列-1) <= board-size)
  • 行-列+board-size(左下がり斜めのライン 1 <= (行-列+board-size) <= board-size)

ということでsafe?の定義

(define (safe? k positions)
  (define (line position) (car position))
  (define (row position) (car (cdr position)))
  (define (right-up position) (- (+ (row position) (line position)) 1))
  (define (left-down position) (+ (- (line position) (row position)) k)) ; kでもOKだと思う…
  (let ((k-line (line (car positions)))
    (k-row (row (car positions)))
    (k-ru (right-up (car positions)))
    (k-ld (left-down (car positions))))
    (define (safe-iter rest)
      (if (null? rest) 
      #t
      (if (or (= k-line (line (car rest)))
          (= k-row (row (car rest)))
          (= k-ru (right-up (car rest)))
          (= k-ld (left-down (car rest))))
          #f
          (safe-iter (cdr rest)))))
    (safe-iter (cdr positions))))

でテスト。

(display (queens 1))
; (((1 1)))#<undef>
(display (queens 2))
; ()#<undef>
; (display (queens 3))
()#<undef>
(display (queens 4))
; (((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))#<undef>
(display (queens 5))
; (((4 5) (2 4) (5 3) (3 2) (1 1)) ((3 5) (5 4) (2 3) (4 2) (1 1)) ((5 5) (3 4) (1 3) (4 2) (2 1)) ((4 5) (1 4) (3 3) (5 2) (2 1)) ((5 5) (2 4) (4 3) (1 2) (3 1)) ((1 5) (4 4) (2 3) (5 2) (3 1)) ((2 5) (5 4) (3 3) (1 2) (4 1)) ((1 5) (3 4) (5 3) (2 2) (4 1)) ((3 5) (1 4) (4 3) (2 2) (5 1)) ((2 5) (4 4) (1 3) (3 2) (5 1)))#<undef>
(display (queens 6))
; (((5 6) (3 5) (1 4) (6 3) (4 2) (2 1)) ((4 6) (1 5) (5 4) (2 3) (6 2) (3 1)) ((3 6) (6 5) (2 4) (5 3) (1 2) (4 1)) ((2 6) (4 5) (6 4) (1 3) (3 2) (5 1)))#<undef>
(display (queens 7))
; (((6 7) (4 6) (2 5) (7 4) (5 3) (3 2) (1 1))
;  ((5 7) (2 6) (6 5) (3 4) (7 3) (4 2) (1 1))
;  ((4 7) (7 6) (3 5) (6 4) (2 3) (5 2) (1 1))
;  ((3 7) (5 6) (7 5) (2 4) (4 3) (6 2) (1 1))
;  ((6 7) (3 6) (5 5) (7 4) (1 3) (4 2) (2 1))
;  ((7 7) (5 6) (3 5) (1 4) (6 3) (4 2) (2 1))
;  ((6 7) (3 6) (7 5) (4 4) (1 3) (5 2) (2 1))
;  ((6 7) (4 6) (7 5) (1 4) (3 3) (5 2) (2 1))
;  ((6 7) (3 6) (1 5) (4 4) (7 3) (5 2) (2 1))
;  ((5 7) (1 6) (4 5) (7 4) (3 3) (6 2) (2 1))
;  ((4 7) (6 6) (1 5) (3 4) (5 3) (7 2) (2 1))
;  ((4 7) (7 6) (5 5) (2 4) (6 3) (1 2) (3 1))
;  ((5 7) (7 6) (2 5) (4 4) (6 3) (1 2) (3 1))
;  ((1 7) (6 6) (4 5) (2 4) (7 3) (5 2) (3 1))
;  ((7 7) (4 6) (1 5) (5 4) (2 3) (6 2) (3 1))
;  ((5 7) (1 6) (6 5) (4 4) (2 3) (7 2) (3 1))
;  ((6 7) (2 6) (5 5) (1 4) (4 3) (7 2) (3 1))
;  ((5 7) (7 6) (2 5) (6 4) (3 3) (1 2) (4 1))
;  ((7 7) (3 6) (6 5) (2 4) (5 3) (1 2) (4 1))
;  ((6 7) (1 6) (3 5) (5 4) (7 3) (2 2) (4 1))
;  ((2 7) (7 6) (5 5) (3 4) (1 3) (6 2) (4 1))
;  ((1 7) (5 6) (2 5) (6 4) (3 3) (7 2) (4 1))
;  ((3 7) (1 6) (6 5) (2 4) (5 3) (7 2) (4 1))
;  ((2 7) (6 6) (3 5) (7 4) (4 3) (1 2) (5 1))
;  ((3 7) (7 6) (2 5) (4 4) (6 3) (1 2) (5 1))
;  ((1 7) (4 6) (7 5) (3 4) (6 3) (2 2) (5 1))
;  ((7 7) (2 6) (4 5) (6 4) (1 3) (3 2) (5 1))
;  ((3 7) (1 6) (6 5) (4 4) (2 3) (7 2) (5 1))
;  ((4 7) (1 6) (3 5) (6 4) (2 3) (7 2) (5 1))
;  ((4 7) (2 6) (7 5) (5 4) (3 3) (1 2) (6 1))
;  ((3 7) (7 6) (4 5) (1 4) (5 3) (2 2) (6 1))
;  ((2 7) (5 6) (7 5) (4 4) (1 3) (3 2) (6 1))
;  ((2 7) (4 6) (1 5) (7 4) (5 3) (3 2) (6 1))
;  ((2 7) (5 6) (1 5) (4 4) (7 3) (3 2) (6 1))
;  ((1 7) (3 6) (5 5) (7 4) (2 3) (4 2) (6 1))
;  ((2 7) (5 6) (3 5) (1 4) (7 3) (4 2) (6 1))
;  ((5 7) (3 6) (1 5) (6 4) (4 3) (2 2) (7 1))
;  ((4 7) (1 6) (5 5) (2 4) (6 3) (3 2) (7 1))
;  ((3 7) (6 6) (2 5) (5 4) (1 3) (4 2) (7 1))
;  ((2 7) (4 6) (6 5) (1 4) (3 3) (5 2) (7 1))
; )#<undef>
(display (queens 8))
; (((4 8) (2 7) (7 6) (3 5) (6 4) (8 3) (5 2) (1 1))
;  ((5 8) (2 7) (4 6) (7 5) (3 4) (8 3) (6 2) (1 1))
;  ((3 8) (5 7) (2 6) (8 5) (6 4) (4 3) (7 2) (1 1))
;  ((3 8) (6 7) (4 6) (2 5) (8 4) (5 3) (7 2) (1 1))
;  ((5 8) (7 7) (1 6) (3 5) (8 4) (6 3) (4 2) (2 1))
;  ((4 8) (6 7) (8 6) (3 5) (1 4) (7 3) (5 2) (2 1))
;  ((3 8) (6 7) (8 6) (1 5) (4 4) (7 3) (5 2) (2 1))
;  ((5 8) (3 7) (8 6) (4 5) (7 4) (1 3) (6 2) (2 1))
;  ((5 8) (7 7) (4 6) (1 5) (3 4) (8 3) (6 2) (2 1))
;  ((4 8) (1 7) (5 6) (8 5) (6 4) (3 3) (7 2) (2 1))
;  ((3 8) (6 7) (4 6) (1 5) (8 4) (5 3) (7 2) (2 1))
;  ((4 8) (7 7) (5 6) (3 5) (1 4) (6 3) (8 2) (2 1))
;  ((6 8) (4 7) (2 6) (8 5) (5 4) (7 3) (1 2) (3 1))
;  ((6 8) (4 7) (7 6) (1 5) (8 4) (2 3) (5 2) (3 1))
;  ((1 8) (7 7) (4 6) (6 5) (8 4) (2 3) (5 2) (3 1))
;  ((6 8) (8 7) (2 6) (4 5) (1 4) (7 3) (5 2) (3 1))
;  ((6 8) (2 7) (7 6) (1 5) (4 4) (8 3) (5 2) (3 1))
;  ((4 8) (7 7) (1 6) (8 5) (5 4) (2 3) (6 2) (3 1))
;  ((5 8) (8 7) (4 6) (1 5) (7 4) (2 3) (6 2) (3 1))
;  ((4 8) (8 7) (1 6) (5 5) (7 4) (2 3) (6 2) (3 1))
;  ((2 8) (7 7) (5 6) (8 5) (1 4) (4 3) (6 2) (3 1))
;  ((1 8) (7 7) (5 6) (8 5) (2 4) (4 3) (6 2) (3 1))
;  ((2 8) (5 7) (7 6) (4 5) (1 4) (8 3) (6 2) (3 1))
;  ((4 8) (2 7) (7 6) (5 5) (1 4) (8 3) (6 2) (3 1))
;  ((5 8) (7 7) (1 6) (4 5) (2 4) (8 3) (6 2) (3 1))
;  ((6 8) (4 7) (1 6) (5 5) (8 4) (2 3) (7 2) (3 1))
;  ((5 8) (1 7) (4 6) (6 5) (8 4) (2 3) (7 2) (3 1))
;  ((5 8) (2 7) (6 6) (1 5) (7 4) (4 3) (8 2) (3 1))
;  ((6 8) (3 7) (7 6) (2 5) (8 4) (5 3) (1 2) (4 1))
;  ((2 8) (7 7) (3 6) (6 5) (8 4) (5 3) (1 2) (4 1))
;  ((7 8) (3 7) (1 6) (6 5) (8 4) (5 3) (2 2) (4 1))
;  ((5 8) (1 7) (8 6) (6 5) (3 4) (7 3) (2 2) (4 1))
;  ((1 8) (5 7) (8 6) (6 5) (3 4) (7 3) (2 2) (4 1))
;  ((3 8) (6 7) (8 6) (1 5) (5 4) (7 3) (2 2) (4 1))
;  ((6 8) (3 7) (1 6) (7 5) (5 4) (8 3) (2 2) (4 1))
;  ((7 8) (5 7) (3 6) (1 5) (6 4) (8 3) (2 2) (4 1))
;  ((7 8) (3 7) (8 6) (2 5) (5 4) (1 3) (6 2) (4 1))
;  ((5 8) (3 7) (1 6) (7 5) (2 4) (8 3) (6 2) (4 1))
;  ((2 8) (5 7) (7 6) (1 5) (3 4) (8 3) (6 2) (4 1))
;  ((3 8) (6 7) (2 6) (5 5) (8 4) (1 3) (7 2) (4 1))
;  ((6 8) (1 7) (5 6) (2 5) (8 4) (3 3) (7 2) (4 1))
;  ((8 8) (3 7) (1 6) (6 5) (2 4) (5 3) (7 2) (4 1))
;  ((2 8) (8 7) (6 6) (1 5) (3 4) (5 3) (7 2) (4 1))
;  ((5 8) (7 7) (2 6) (6 5) (3 4) (1 3) (8 2) (4 1))
;  ((3 8) (6 7) (2 6) (7 5) (5 4) (1 3) (8 2) (4 1))
;  ((6 8) (2 7) (7 6) (1 5) (3 4) (5 3) (8 2) (4 1))
;  ((3 8) (7 7) (2 6) (8 5) (6 4) (4 3) (1 2) (5 1))
;  ((6 8) (3 7) (7 6) (2 5) (4 4) (8 3) (1 2) (5 1))
;  ((4 8) (2 7) (7 6) (3 5) (6 4) (8 3) (1 2) (5 1))
;  ((7 8) (1 7) (3 6) (8 5) (6 4) (4 3) (2 2) (5 1))
;  ((1 8) (6 7) (8 6) (3 5) (7 4) (4 3) (2 2) (5 1))
;  ((3 8) (8 7) (4 6) (7 5) (1 4) (6 3) (2 2) (5 1))
;  ((6 8) (3 7) (7 6) (4 5) (1 4) (8 3) (2 2) (5 1))
;  ((7 8) (4 7) (2 6) (8 5) (6 4) (1 3) (3 2) (5 1))
;  ((4 8) (6 7) (8 6) (2 5) (7 4) (1 3) (3 2) (5 1))
;  ((2 8) (6 7) (1 6) (7 5) (4 4) (8 3) (3 2) (5 1))
;  ((2 8) (4 7) (6 6) (8 5) (3 4) (1 3) (7 2) (5 1))
;  ((3 8) (6 7) (8 6) (2 5) (4 4) (1 3) (7 2) (5 1))
;  ((6 8) (3 7) (1 6) (8 5) (4 4) (2 3) (7 2) (5 1))
;  ((8 8) (4 7) (1 6) (3 5) (6 4) (2 3) (7 2) (5 1))
;  ((4 8) (8 7) (1 6) (3 5) (6 4) (2 3) (7 2) (5 1))
;  ((2 8) (6 7) (8 6) (3 5) (1 4) (4 3) (7 2) (5 1))
;  ((7 8) (2 7) (6 6) (3 5) (1 4) (4 3) (8 2) (5 1))
;  ((3 8) (6 7) (2 6) (7 5) (1 4) (4 3) (8 2) (5 1))
;  ((4 8) (7 7) (3 6) (8 5) (2 4) (5 3) (1 2) (6 1))
;  ((4 8) (8 7) (5 6) (3 5) (1 4) (7 3) (2 2) (6 1))
;  ((3 8) (5 7) (8 6) (4 5) (1 4) (7 3) (2 2) (6 1))
;  ((4 8) (2 7) (8 6) (5 5) (7 4) (1 3) (3 2) (6 1))
;  ((5 8) (7 7) (2 6) (4 5) (8 4) (1 3) (3 2) (6 1))
;  ((7 8) (4 7) (2 6) (5 5) (8 4) (1 3) (3 2) (6 1))
;  ((8 8) (2 7) (4 6) (1 5) (7 4) (5 3) (3 2) (6 1))
;  ((7 8) (2 7) (4 6) (1 5) (8 4) (5 3) (3 2) (6 1))
;  ((5 8) (1 7) (8 6) (4 5) (2 4) (7 3) (3 2) (6 1))
;  ((4 8) (1 7) (5 6) (8 5) (2 4) (7 3) (3 2) (6 1))
;  ((5 8) (2 7) (8 6) (1 5) (4 4) (7 3) (3 2) (6 1))
;  ((3 8) (7 7) (2 6) (8 5) (5 4) (1 3) (4 2) (6 1))
;  ((3 8) (1 7) (7 6) (5 5) (8 4) (2 3) (4 2) (6 1))
;  ((8 8) (2 7) (5 6) (3 5) (1 4) (7 3) (4 2) (6 1))
;  ((3 8) (5 7) (2 6) (8 5) (1 4) (7 3) (4 2) (6 1))
;  ((3 8) (5 7) (7 6) (1 5) (4 4) (2 3) (8 2) (6 1))
;  ((5 8) (2 7) (4 6) (6 5) (8 4) (3 3) (1 2) (7 1))
;  ((6 8) (3 7) (5 6) (8 5) (1 4) (4 3) (2 2) (7 1))
;  ((5 8) (8 7) (4 6) (1 5) (3 4) (6 3) (2 2) (7 1))
;  ((4 8) (2 7) (5 6) (8 5) (6 4) (1 3) (3 2) (7 1))
;  ((4 8) (6 7) (1 6) (5 5) (2 4) (8 3) (3 2) (7 1))
;  ((6 8) (3 7) (1 6) (8 5) (5 4) (2 3) (4 2) (7 1))
;  ((5 8) (3 7) (1 6) (6 5) (8 4) (2 3) (4 2) (7 1))
;  ((4 8) (2 7) (8 6) (6 5) (1 4) (3 3) (5 2) (7 1))
;  ((6 8) (3 7) (5 6) (7 5) (1 4) (4 3) (2 2) (8 1))
;  ((6 8) (4 7) (7 6) (1 5) (3 4) (5 3) (2 2) (8 1))
;  ((4 8) (7 7) (5 6) (2 5) (6 4) (1 3) (3 2) (8 1))
;  ((5 8) (7 7) (2 6) (6 5) (3 4) (1 3) (4 2) (8 1))
; )#<undef>