次の “嘘つき” パズル (Phillips 1934より) を解け。 5 人の女子生徒が試験のために座っている。彼女らは、両親が結果 に過度の関心を持っていると考えている。そのため彼女らは、試 験の結果について家に手紙を送る際に、ひとつ本当のことを書き、 ひとつ嘘のことを書くよう申し合わせた。以下に、彼女らの手紙 のそれに関連する部分を示す。
- Betty: “試験は Kitty が 2 位。私は残念ながら 3 位。”
- Ethel: “喜んで、私トップ取ったよ。Joan が 2 位。”
- Joan: “私は 3 位で、かわいそうな Ethel は最下位。”
- Kitty: “私は 2 位。Mary は 4 位しか取れなかったんだ。” • Mary: “私は 4 位。トップは Betty だったよ。” 実際には、5 人の女の子の成績はどういう順番だったのだろうか。
解答 🔗
問題文の条件を require で愚直に表現すれば解ける。同じ点数をとった女子生徒はおらず、順番は重複しないため、4.3.2 の脚注で言及されている distinct 手続きも条件に追加する必要がある。条件をプログラムで表現するだけで問題が解けてしまう非決定性プログラムすごい。
(define (distinct? items)
(cond ((null? items) true)
((null? (cdr items)) true)
((member (car items) (cdr items)) false)
(else (distinct? (cdr items)))))
(define (solve-puzzle)
(let (
(betty (amb 1 2 3 4 5))
(ethel (amb 1 2 3 4 5))
(joan (amb 1 2 3 4 5))
(kitty (amb 1 2 3 4 5))
(mary (amb 1 2 3 4 5)))
(require (or (eq? kitty 2) (eq? betty 3)))
(require (or (eq? ethel 1) (eq? joan 2)))
(require (or (eq? joan 3) (eq? ethel 5)))
(require (or (eq? kitty 2) (eq? mary 4)))
(require (or (eq? mary 4) (eq? betty 1)))
(require (distinct? (list betty ethel joan kitty mary)))
(list
(list 'betty betty)
(list 'ethel ethel)
(list 'joan joan)
(list 'kitty kitty)
(list 'mary mary))))
(solve-puzzle)
; ((betty 3) (ethel 5) (joan 2) (kitty 1) (mary 4))