Scheme - 超言語的抽象(Schemeの変形 - 非決定性計算(非決定性プログラムの例(論理パズル(エイトクイーンパズル))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

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

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.3(Schemeの変形 - 非決定性計算)、4.3.3(非決定性プログラムの例)、論理パズル、問題 4.44.を解いてみる。

その他参考書籍

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

問題 4.44.

コード(BBEdit, Emacs)

sample44.scm

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

(define require
  (lambda (p)
    (if (not p) (amb))))

(define (an-integer-between low high)
  (require (<= low high))
  (amb low (an-integer-between (+ low 1)
                               high)))

(define (distinct? items)
  (cond ((null? items) #t)
        ((null? (cdr items)) #t)
        ((member (car items) (cdr items)) #f)
        (else (distinct? (cdr items)))))

(define (queens board-size)
  ;; 各クィーンの座標 (rn cn)
  (let ((r0 (an-integer-between 0 (- board-size 1)))
        (r1 (an-integer-between 0 (- board-size 1)))
        (r2 (an-integer-between 0 (- board-size 1)))
        (r3 (an-integer-between 0 (- board-size 1)))
        (r4 (an-integer-between 0 (- board-size 1)))
        (r5 (an-integer-between 0 (- board-size 1)))
        (r6 (an-integer-between 0 (- board-size 1)))
        (r7 (an-integer-between 0 (- board-size 1)))
        (c0 (an-integer-between 0 (- board-size 1)))
        (c1 (an-integer-between 0 (- board-size 1)))
        (c2 (an-integer-between 0 (- board-size 1)))
        (c3 (an-integer-between 0 (- board-size 1)))
        (c4 (an-integer-between 0 (- board-size 1)))
        (c5 (an-integer-between 0 (- board-size 1)))
        (c6 (an-integer-between 0 (- board-size 1)))
        (c7 (an-integer-between 0 (- board-size 1))))
    ;; どのクィーンの行も被らない
    (require (distinct? (list r1 r2 r3 r4 r5 r6 r7)))
    ;; どのクィーンの列も被らない
    (require (distinct? (list c1 c2 c3 c4 c5 c6 c7)))
    ;; ／方向の斜めに被らない
    (require (distinct? (list (+ r0 c0)
                              (+ r1 c1)
                              (+ r2 c2)
                              (+ r3 c3)
                              (+ r4 c4)
                              (+ r5 c5)
                              (+ r6 c6)
                              (+ r7 c7))))
    ;; \方向の斜めに被らない
    (require (distinct? (list (- r0 c0)
                              (- r1 c1)
                              (- r2 c2)
                              (- r3 c3)
                              (- r4 c4)
                              (- r5 c5)
                              (- r6 c6)
                              (- r7 c7))))
    (list (list r0 c0)
          (list r1 c1)
          (list r2 c2)
          (list r3 c3)
          (list r4 c4)
          (list r5 c5)
          (list r6 c6)
          (list r7 c7))))

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

$ ./sample44.sc
$