It is not difficult to solve the eight-queens puzzle using amb evaluator,
but have to specify either row number or column number explicitly because it will
takes a couple of hours for the program to find an answer if we let the
program to try each number against both row and column.
E.g. we can specify a position of the first row as
(list 0 (amb 0 1 2 3 4 5 6 7))
amb evaluatorを使ってeight-queensパズルは簡単に解けますが、queenの場所を
指定するときに、行、列のどれかを固定する必要があります。
たとえば、一行目のqueenは(list 0 (amb 0 1 2 3 4 5 6 7))の形ですれば、秒単位で
答えが出ますが、単にそれぞれのqueenを(list (amb 0 1 2 3 4 5 6 7) (amb 0 1 2 3 4 5 6 7))
のように指定すると、選択肢が多くなり、1時間がたっても答えが出ません。
用amb evaluator解决eight queens问题没有什么难度。但是在指定王后时要注意
固定某一行或者是某一列。比如,指定第一行王后的位置为
(list 0 (amb 0 1 2 3 4 5 6 7)),而不是指定第一个王后为
(list (amb 0 1 2 3 4 5 6 7) (amb 0 1 2 3 4 5 6 7)).
否则由于分支太多而导致运算会持续很长时间。
(define (eight-queens)
(define (checked a b)
(or
(or (= (car a) (car b))
(= (cadr a) (cadr b)))
(= (abs (- (car a) (car b)))
(abs (- (cadr a) (cadr b))))))
(let ((q1 (list 0 (amb 0 1 2 3 4 5 6 7))))
(let ((q2 (list 1 (amb 0 1 2 3 4 5 6 7))))
(require (not (checked q2 q1)))
(let ((q3 (list 2 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q3 q1))
(not (checked q3 q2))))
(let ((q4 (list 3 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q4 q1))
(not (checked q4 q2))
(not (checked q4 q3))))
(let ((q5 (list 4 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q5 q1))
(not (checked q5 q2))
(not (checked q5 q3))
(not (checked q5 q4))))
(let ((q6 (list 5 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q6 q1))
(not (checked q6 q2))
(not (checked q6 q3))
(not (checked q6 q4))
(not (checked q6 q5))))
(let ((q7 (list 6 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q7 q1))
(not (checked q7 q2))
(not (checked q7 q3))
(not (checked q7 q4))
(not (checked q7 q5))
(not (checked q7 q6))))
(let ((q8 (list 7 (amb 0 1 2 3 4 5 6 7))))
(require (and
(not (checked q8 q1))
(not (checked q8 q2))
(not (checked q8 q3))
(not (checked q8 q4))
(not (checked q8 q5))
(not (checked q8 q6))
(not (checked q8 q7))))
(list q1 q2 q3 q4 q5 q6 q7 q8))))))))))
Friday, November 26, 2010
Thursday, November 25, 2010
amb evaluator of SICP
It is necessary to implement the amb evaluator in order to keep up with
the text and the evaluator does not make sense if it can not handle logical
AND/OR.
Here is the analayze-and in my evaluator which took me some time to work out
continuation part.
为了更好地理解内容,有必要实现amb evaluator。而不能处理逻辑与或的evaluator是没有
什么实际意义的。因为至今对continuation也不是很理解,费了好大劲儿才实现了。
下面是逻辑或的主要部分。
テキストを良く理解するために、amb evaluatorを実装しなければなりません。テキストに
は主な部分がありますが、論理AND、ORの部分がありませんでした。しかし、これがない限り、
amb evaluatorとしてあまり意味がないので、試しに実装してみました。何とか動き出しましたが、
いまだに継続についてあまり理解できていません。
以下は論理ANDのメイン部分になります。
(define (analyze-and exp)
(define (iter first rest env succ fl)
(if (null? rest)
((analyze first) env
(lambda (v fl1)
(succ v fl1))
fl)
((analyze first) env
(lambda (v fl2)
(if (true? v)
(iter (car rest) (cdr rest) env succ fl2)
(succ false fl2)))
fl)))
(let ((f (cadr exp))
(r (cddr exp)))
(lambda (env succeed fail)
(iter f r env succeed fail))))
the text and the evaluator does not make sense if it can not handle logical
AND/OR.
Here is the analayze-and in my evaluator which took me some time to work out
continuation part.
为了更好地理解内容,有必要实现amb evaluator。而不能处理逻辑与或的evaluator是没有
什么实际意义的。因为至今对continuation也不是很理解,费了好大劲儿才实现了。
下面是逻辑或的主要部分。
テキストを良く理解するために、amb evaluatorを実装しなければなりません。テキストに
は主な部分がありますが、論理AND、ORの部分がありませんでした。しかし、これがない限り、
amb evaluatorとしてあまり意味がないので、試しに実装してみました。何とか動き出しましたが、
いまだに継続についてあまり理解できていません。
以下は論理ANDのメイン部分になります。
(define (analyze-and exp)
(define (iter first rest env succ fl)
(if (null? rest)
((analyze first) env
(lambda (v fl1)
(succ v fl1))
fl)
((analyze first) env
(lambda (v fl2)
(if (true? v)
(iter (car rest) (cdr rest) env succ fl2)
(succ false fl2)))
fl)))
(let ((f (cadr exp))
(r (cddr exp)))
(lambda (env succeed fail)
(iter f r env succeed fail))))
Subscribe to:
Posts (Atom)