計算機プログラムの構造と解釈 第二版 P72 問題2.42

たしかポイントは、行と列をどうやって表すか？的なような事だったような気がする。
あとは、safeはけっこうごちゃごちゃやらないといけない。ので凄く難しい。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)

(define nil '())


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


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


(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))


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



(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 (adjoin-position row k qs)
  (cons (list k row) qs))

(define empty-board ())

(define (safe? col positions)
  (define (safe-simple? col row pos)
    (let ((r (cadr pos))
          (c (car pos)))
      (let ((lu (- r c))
            (ll (+ r c)))
        (and (not (= lu (- row col)))
             (not (= ll (+ row col)))
             (not (= r row))))))
  (define (all p ls)
    (if (null? ls)
      #t
      (and (p (car ls)) (all p (cdr ls)))))
  (let ((hd (car positions))
        (tl (cdr positions)))
    (all (lambda (pos) (safe-simple? col (cadr hd) pos)) tl)))


;; main
(define (main args)
  (display "(queens 4): ")
  (newline)
  (display (queens 4))
  (newline)

  0)

実行

(((4 3) (3 1) (2 4) (1 2)) ((4 2) (3 4) (2 1) (1 3)))

そもそも4 x 4だと2通りしか無いという話を聞いていたので、
できている。
あと、safe?はどっかヤツのコピペだな。
たしか、自分で作ったヤツはダメだったんだよな。。。
斜め上とか、下とか、のヤツを求めるのが難しいかった。

昔の俺、ちゃんと考えろよ。
でも、何やってるかは、なんかわかるので、まぁまぁまぁ。。。涙