Scheme - データによる抽象の構築(階層データ構造と閉包性(公認インターフェースとしての並び(写像の入れ子(エイトクィーンパズル))))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.2(階層データ構造と閉包性)、2.2.3(公認インターフェースとしての並び)、写像の入れ子、問題 2.42.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.42.

コード(BBEdit, Emacs)

sample.scm

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

;; これまでに書いた手続き
(load "./procedures.scm")

(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 new-row k rest-of-queens)
  (append rest-of-queens
          (list (cons new-row k))))

(define empty-board nil)

(define (safe? k positions)
  (define k-row (car (car (last-pair positions))))
  (define (iter n positions)
    (cond ((= n k) #t)
          ((= k-row (car (car positions))) #f)
          (else (iter (+ n 1) (cdr positions)))))
  (iter 1 positions))

(for-each (lambda (n)
            (for-each print
                      (queens n)))
          (enumerate-interval 0 5))

入出力結果(Terminal(gosh), REPL(Read, Eval, Print, Loop))

$ ./sample.scm
()
((1 . 1))
((1 . 1) (2 . 2))
((2 . 1) (1 . 2))
((1 . 1) (2 . 2) (3 . 3))
((1 . 1) (3 . 2) (2 . 3))
((2 . 1) (1 . 2) (3 . 3))
((2 . 1) (3 . 2) (1 . 3))
((3 . 1) (1 . 2) (2 . 3))
((3 . 1) (2 . 2) (1 . 3))
((1 . 1) (2 . 2) (3 . 3) (4 . 4))
((1 . 1) (2 . 2) (4 . 3) (3 . 4))
((1 . 1) (3 . 2) (2 . 3) (4 . 4))
((1 . 1) (3 . 2) (4 . 3) (2 . 4))
((1 . 1) (4 . 2) (2 . 3) (3 . 4))
((1 . 1) (4 . 2) (3 . 3) (2 . 4))
((2 . 1) (1 . 2) (3 . 3) (4 . 4))
((2 . 1) (1 . 2) (4 . 3) (3 . 4))
((2 . 1) (3 . 2) (1 . 3) (4 . 4))
((2 . 1) (3 . 2) (4 . 3) (1 . 4))
((2 . 1) (4 . 2) (1 . 3) (3 . 4))
((2 . 1) (4 . 2) (3 . 3) (1 . 4))
((3 . 1) (1 . 2) (2 . 3) (4 . 4))
((3 . 1) (1 . 2) (4 . 3) (2 . 4))
((3 . 1) (2 . 2) (1 . 3) (4 . 4))
((3 . 1) (2 . 2) (4 . 3) (1 . 4))
((3 . 1) (4 . 2) (1 . 3) (2 . 4))
((3 . 1) (4 . 2) (2 . 3) (1 . 4))
((4 . 1) (1 . 2) (2 . 3) (3 . 4))
((4 . 1) (1 . 2) (3 . 3) (2 . 4))
((4 . 1) (2 . 2) (1 . 3) (3 . 4))
((4 . 1) (2 . 2) (3 . 3) (1 . 4))
((4 . 1) (3 . 2) (1 . 3) (2 . 4))
((4 . 1) (3 . 2) (2 . 3) (1 . 4))
((1 . 1) (2 . 2) (3 . 3) (4 . 4) (5 . 5))
((1 . 1) (2 . 2) (3 . 3) (5 . 4) (4 . 5))
((1 . 1) (2 . 2) (4 . 3) (3 . 4) (5 . 5))
((1 . 1) (2 . 2) (4 . 3) (5 . 4) (3 . 5))
((1 . 1) (2 . 2) (5 . 3) (3 . 4) (4 . 5))
((1 . 1) (2 . 2) (5 . 3) (4 . 4) (3 . 5))
((1 . 1) (3 . 2) (2 . 3) (4 . 4) (5 . 5))
((1 . 1) (3 . 2) (2 . 3) (5 . 4) (4 . 5))
((1 . 1) (3 . 2) (4 . 3) (2 . 4) (5 . 5))
((1 . 1) (3 . 2) (4 . 3) (5 . 4) (2 . 5))
((1 . 1) (3 . 2) (5 . 3) (2 . 4) (4 . 5))
((1 . 1) (3 . 2) (5 . 3) (4 . 4) (2 . 5))
((1 . 1) (4 . 2) (2 . 3) (3 . 4) (5 . 5))
((1 . 1) (4 . 2) (2 . 3) (5 . 4) (3 . 5))
((1 . 1) (4 . 2) (3 . 3) (2 . 4) (5 . 5))
((1 . 1) (4 . 2) (3 . 3) (5 . 4) (2 . 5))
((1 . 1) (4 . 2) (5 . 3) (2 . 4) (3 . 5))
((1 . 1) (4 . 2) (5 . 3) (3 . 4) (2 . 5))
((1 . 1) (5 . 2) (2 . 3) (3 . 4) (4 . 5))
((1 . 1) (5 . 2) (2 . 3) (4 . 4) (3 . 5))
((1 . 1) (5 . 2) (3 . 3) (2 . 4) (4 . 5))
((1 . 1) (5 . 2) (3 . 3) (4 . 4) (2 . 5))
((1 . 1) (5 . 2) (4 . 3) (2 . 4) (3 . 5))
((1 . 1) (5 . 2) (4 . 3) (3 . 4) (2 . 5))
((2 . 1) (1 . 2) (3 . 3) (4 . 4) (5 . 5))
((2 . 1) (1 . 2) (3 . 3) (5 . 4) (4 . 5))
((2 . 1) (1 . 2) (4 . 3) (3 . 4) (5 . 5))
((2 . 1) (1 . 2) (4 . 3) (5 . 4) (3 . 5))
((2 . 1) (1 . 2) (5 . 3) (3 . 4) (4 . 5))
((2 . 1) (1 . 2) (5 . 3) (4 . 4) (3 . 5))
((2 . 1) (3 . 2) (1 . 3) (4 . 4) (5 . 5))
((2 . 1) (3 . 2) (1 . 3) (5 . 4) (4 . 5))
((2 . 1) (3 . 2) (4 . 3) (1 . 4) (5 . 5))
((2 . 1) (3 . 2) (4 . 3) (5 . 4) (1 . 5))
((2 . 1) (3 . 2) (5 . 3) (1 . 4) (4 . 5))
((2 . 1) (3 . 2) (5 . 3) (4 . 4) (1 . 5))
((2 . 1) (4 . 2) (1 . 3) (3 . 4) (5 . 5))
((2 . 1) (4 . 2) (1 . 3) (5 . 4) (3 . 5))
((2 . 1) (4 . 2) (3 . 3) (1 . 4) (5 . 5))
((2 . 1) (4 . 2) (3 . 3) (5 . 4) (1 . 5))
((2 . 1) (4 . 2) (5 . 3) (1 . 4) (3 . 5))
((2 . 1) (4 . 2) (5 . 3) (3 . 4) (1 . 5))
((2 . 1) (5 . 2) (1 . 3) (3 . 4) (4 . 5))
((2 . 1) (5 . 2) (1 . 3) (4 . 4) (3 . 5))
((2 . 1) (5 . 2) (3 . 3) (1 . 4) (4 . 5))
((2 . 1) (5 . 2) (3 . 3) (4 . 4) (1 . 5))
((2 . 1) (5 . 2) (4 . 3) (1 . 4) (3 . 5))
((2 . 1) (5 . 2) (4 . 3) (3 . 4) (1 . 5))
((3 . 1) (1 . 2) (2 . 3) (4 . 4) (5 . 5))
((3 . 1) (1 . 2) (2 . 3) (5 . 4) (4 . 5))
((3 . 1) (1 . 2) (4 . 3) (2 . 4) (5 . 5))
((3 . 1) (1 . 2) (4 . 3) (5 . 4) (2 . 5))
((3 . 1) (1 . 2) (5 . 3) (2 . 4) (4 . 5))
((3 . 1) (1 . 2) (5 . 3) (4 . 4) (2 . 5))
((3 . 1) (2 . 2) (1 . 3) (4 . 4) (5 . 5))
((3 . 1) (2 . 2) (1 . 3) (5 . 4) (4 . 5))
((3 . 1) (2 . 2) (4 . 3) (1 . 4) (5 . 5))
((3 . 1) (2 . 2) (4 . 3) (5 . 4) (1 . 5))
((3 . 1) (2 . 2) (5 . 3) (1 . 4) (4 . 5))
((3 . 1) (2 . 2) (5 . 3) (4 . 4) (1 . 5))
((3 . 1) (4 . 2) (1 . 3) (2 . 4) (5 . 5))
((3 . 1) (4 . 2) (1 . 3) (5 . 4) (2 . 5))
((3 . 1) (4 . 2) (2 . 3) (1 . 4) (5 . 5))
((3 . 1) (4 . 2) (2 . 3) (5 . 4) (1 . 5))
((3 . 1) (4 . 2) (5 . 3) (1 . 4) (2 . 5))
((3 . 1) (4 . 2) (5 . 3) (2 . 4) (1 . 5))
((3 . 1) (5 . 2) (1 . 3) (2 . 4) (4 . 5))
((3 . 1) (5 . 2) (1 . 3) (4 . 4) (2 . 5))
((3 . 1) (5 . 2) (2 . 3) (1 . 4) (4 . 5))
((3 . 1) (5 . 2) (2 . 3) (4 . 4) (1 . 5))
((3 . 1) (5 . 2) (4 . 3) (1 . 4) (2 . 5))
((3 . 1) (5 . 2) (4 . 3) (2 . 4) (1 . 5))
((4 . 1) (1 . 2) (2 . 3) (3 . 4) (5 . 5))
((4 . 1) (1 . 2) (2 . 3) (5 . 4) (3 . 5))
((4 . 1) (1 . 2) (3 . 3) (2 . 4) (5 . 5))
((4 . 1) (1 . 2) (3 . 3) (5 . 4) (2 . 5))
((4 . 1) (1 . 2) (5 . 3) (2 . 4) (3 . 5))
((4 . 1) (1 . 2) (5 . 3) (3 . 4) (2 . 5))
((4 . 1) (2 . 2) (1 . 3) (3 . 4) (5 . 5))
((4 . 1) (2 . 2) (1 . 3) (5 . 4) (3 . 5))
((4 . 1) (2 . 2) (3 . 3) (1 . 4) (5 . 5))
((4 . 1) (2 . 2) (3 . 3) (5 . 4) (1 . 5))
((4 . 1) (2 . 2) (5 . 3) (1 . 4) (3 . 5))
((4 . 1) (2 . 2) (5 . 3) (3 . 4) (1 . 5))
((4 . 1) (3 . 2) (1 . 3) (2 . 4) (5 . 5))
((4 . 1) (3 . 2) (1 . 3) (5 . 4) (2 . 5))
((4 . 1) (3 . 2) (2 . 3) (1 . 4) (5 . 5))
((4 . 1) (3 . 2) (2 . 3) (5 . 4) (1 . 5))
((4 . 1) (3 . 2) (5 . 3) (1 . 4) (2 . 5))
((4 . 1) (3 . 2) (5 . 3) (2 . 4) (1 . 5))
((4 . 1) (5 . 2) (1 . 3) (2 . 4) (3 . 5))
((4 . 1) (5 . 2) (1 . 3) (3 . 4) (2 . 5))
((4 . 1) (5 . 2) (2 . 3) (1 . 4) (3 . 5))
((4 . 1) (5 . 2) (2 . 3) (3 . 4) (1 . 5))
((4 . 1) (5 . 2) (3 . 3) (1 . 4) (2 . 5))
((4 . 1) (5 . 2) (3 . 3) (2 . 4) (1 . 5))
((5 . 1) (1 . 2) (2 . 3) (3 . 4) (4 . 5))
((5 . 1) (1 . 2) (2 . 3) (4 . 4) (3 . 5))
((5 . 1) (1 . 2) (3 . 3) (2 . 4) (4 . 5))
((5 . 1) (1 . 2) (3 . 3) (4 . 4) (2 . 5))
((5 . 1) (1 . 2) (4 . 3) (2 . 4) (3 . 5))
((5 . 1) (1 . 2) (4 . 3) (3 . 4) (2 . 5))
((5 . 1) (2 . 2) (1 . 3) (3 . 4) (4 . 5))
((5 . 1) (2 . 2) (1 . 3) (4 . 4) (3 . 5))
((5 . 1) (2 . 2) (3 . 3) (1 . 4) (4 . 5))
((5 . 1) (2 . 2) (3 . 3) (4 . 4) (1 . 5))
((5 . 1) (2 . 2) (4 . 3) (1 . 4) (3 . 5))
((5 . 1) (2 . 2) (4 . 3) (3 . 4) (1 . 5))
((5 . 1) (3 . 2) (1 . 3) (2 . 4) (4 . 5))
((5 . 1) (3 . 2) (1 . 3) (4 . 4) (2 . 5))
((5 . 1) (3 . 2) (2 . 3) (1 . 4) (4 . 5))
((5 . 1) (3 . 2) (2 . 3) (4 . 4) (1 . 5))
((5 . 1) (3 . 2) (4 . 3) (1 . 4) (2 . 5))
((5 . 1) (3 . 2) (4 . 3) (2 . 4) (1 . 5))
((5 . 1) (4 . 2) (1 . 3) (2 . 4) (3 . 5))
((5 . 1) (4 . 2) (1 . 3) (3 . 4) (2 . 5))
((5 . 1) (4 . 2) (2 . 3) (1 . 4) (3 . 5))
((5 . 1) (4 . 2) (2 . 3) (3 . 4) (1 . 5))
((5 . 1) (4 . 2) (3 . 3) (1 . 4) (2 . 5))
((5 . 1) (4 . 2) (3 . 3) (2 . 4) (1 . 5))
$