# \$BN}=,LdBj(B 1 (\$B2rEzNc(B)

1. \$B%b!<%S%k\$NLdBj(B(\$B>\:Y(B)
a. left-branch, right-branch, branch-length, branch-structure \$B\$rDj5A\$;\$h(B
\$B\$3\$l\$O!"(Bmobile, branch \$B\$,%j%9%H9=B\$\$r\$b\$A\$\$\$F\$I\$N\$h\$&\$KI=\$5\$l\$F\$\$\$k\$+\$K1~\$8\$F!"(B \$B\$=\$N\$^\$^5-=R\$9\$l\$PNI\$\$!#\$A\$J\$_\$K!"\$3\$N\$h\$&\$J4X?t\$O(B field \$B\$rA*Br\$7\$FCM\$r\$H\$C\$FMh\$k\$?\$a!"(B selector \$B\$H\$b8F\$P\$l\$k!#(B
```(define (left-branch mobile) (car mobile))

(define (branch-length branch) (car branch))
```
b. \$B%b!<%S%k\$KBP\$7\$F!"\$=\$NAm=ENL\$r\$+\$(\$9(B total-weight \$B\$r(B a. \$B\$N4X?t\$r(B \$B\$b\$A\$\$\$FDj5A\$;\$h!#(B
\$BAm=ENL\$rJV\$9\$KEv\$?\$C\$F!"(Bstructure \$B\$,%b!<%S%k\$G\$"\$k\$+!"\$?\$@\$N\$*\$b\$j\$G\$"\$k\$+\$rH=Dj\$9\$k(B \$B4X?t\$rDj5A\$7\$?!#\$3\$l\$O!"\$*\$b\$j\$d%b!<%S%k\$,\$=\$l\$>\$l\$I\$N\$h\$&\$J%G!<%?9=B\$\$GI=8=(B \$B\$5\$l\$?\$+\$K\$h\$kItJ,\$G\$"\$k!#(B
```(define (leaf-weight? structure)  (number? structure))
```
\$B\$3\$N4X?t\$J\$i\$S\$K!">e=R\$N(B selector \$B\$rMQ\$\$\$F!"(Btotal-weight \$B\$O0J2<\$N\$h\$&\$K(B \$B:F5"E*\$KDj5A\$G\$-\$k!#(B
```
(define (weight-value weight-obj) weight-obj)
(define (mobile-total-weight mobile)
(+ (total-weight (branch-structure (left-branch mobile)))
(total-weight (branch-structure (right-branch mobile)))))

(define (total-weight structure)
(if (leaf-weight? structure)
(weight-value structure)
(mobile-total-weight structure)))
```
c. \$B%b!<%S%k\$,%P%i%s%9\$7\$F\$\$\$k\$+\$I\$&\$+\$rJV\$9!"(B mobile-balanced? \$B\$rDj5A\$;\$h!#(B
\$B%b!<%S%k\$,%P%i%s%9\$7\$F\$\$\$k\$+\$I\$&\$+H=Dj\$9\$k\$K\$O!"(B \$B:81&\$N;R6!\$,%P%i%s%9\$7\$F\$*\$j!"<+J,<+?H\$,%P%i%s%9\$7\$F\$\$\$l\$P\$h\$\$!#(B \$B0J2<\$O!"%W%m%0%i%`Nc\$G\$"\$k!#(B
```(define (branch-moment branch)
(* (total-weight (branch-structure branch))
(branch-length branch)))

(define (mobile-balanced? structure)
(if (leaf-weight? structure)
#t
(and (mobile-balanced?
(branch-structure (left-branch structure)))
(mobile-balanced?
(branch-structure (right-branch structure)))
(= (branch-moment (left-branch structure))
(branch-moment (right-branch structure))))))
```
d. \$B%b!<%S%k\$N%G!<%?9=B\$\$r0J2<\$NMM\$KJQ99\$7\$?>l9g\$K%W%m%0%i%`\$NJQ99E@\$r9M\$(\$h!#(B
```
;;; Structure := Mobile | Weight
;;; Mobile := ('Mobile left-structure right-structure)
;;; Weight := ('Weight weight-value)

(define (make-mobile left right) (list 'Mobile left right))
(define (make-weight value)      (list 'Weight value))
```
\$B:#2sJQ99\$5\$l\$?\$N\$O!"(Bmobile \$B\$H=E\$_\$N%G!<%?9=B\$\$N\$_\$G\$"\$k!#(B \$B\$D\$^\$j!"0J>e\$N\$h\$&\$Jl9g!"JQ998D=j\$O(B
• a. \$B\$GDj5A\$7\$?(B selector \$B\$J\$i\$S\$K!"(B
• b. \$B\$GDj5A\$7\$?(B \$B\$*\$b\$j\$+%b!<%S%k\$+\$NH=Dj4X?t\$H(B
• b. \$B\$N(Bweight-value (weight object \$B\$N(B selector)
\$B\$N\$_\$G\$"\$k!#(B \$B\$H\$O\$\$\$(!"(Bconstructor \$B\$,JQ\$o\$C\$?\$N\$G!"(B sample-mobile0,1 \$B\$N\$H\$3\$m\$b(B \$BJQ99\$,@8\$8\$^\$9\$,!#(B
```;;; mobile selector

;;; weight-obj selector

;;; mobile/weight type predicate
(define (leaf-weight? structure) (eq? (car mobile) 'Weight))
```
\$B\$D\$^\$j!"%G!<%?9=B\$\$X\$N%"%/%;%9

\$BLdBj\$K\$b\$I\$k(B

2. N-Queen \$B%Q%:%k\$N2r\$N8D?t\$rJV\$9(B program \$B\$r:n\$l!#(B
\$B\$H\$j\$"\$(\$:!"<+J,\$G:n\$C\$F\$_\$^\$7\$g\$&!#(B \$B2rEzNc\$O\$3\$N8e\$K:\\$;\$^\$9!#(B \$B\$3\$N2rEz\$O;^4"\$r9T\$C\$?Nc\$G\$9!#(B

\$B\$NJ}K!\$H\$7\$F!"9TJ}8~\$J\$i\$S\$Kl9g(B safety check \$B\$r9bB.\$K\$*\$3\$J\$&\$3\$H\$,\$G\$-\$k\$G\$7\$g\$&!#(B \$B1F\$r(B bit mask \$B\$H\$7\$FI=8=\$7\$F\$*\$/\$H!"\$5\$i\$KAa\$\$\$G\$7\$g\$&!#(B \$B\$?\$@!"\$=\$l\$G\$O%j%9%H\$r\$D\$+\$C\$?%W%m%0%i%_%s%0\$NN}=,\$K\$O\$"\$^\$j\$J\$i\$J\$\$(B:-)

\$B\$H\$\$\$&\$3\$H\$G!"0J2<\$N2rEzNc\$KMn\$ACe\$-\$^\$7\$?!#(B \$BF|K\8l\$N%3%a%s%H\$D\$-\$G\$9!#(B

```;;;
;;; N-Queen Problem
;;;

;;;
;;; \$B%\!<%I\$NDj5A\$H(B board-safe? \$B\$NDj5A(B
;;;
;;; \$B%\!<%I\$N9=@.\$O!"(B(row_k ... row_0)\$B\$H\$J\$C\$F\$*\$j!"\$3\$l\$O3F!9(B
;;; Queen \$B\$,(B i \$BNs(B (row_i)-th \$B9T(B \$B\$K\$\$\$k\$3\$H\$r<(\$7\$F\$\$\$k!#(B
;;;

(define (board-init) (list))

(define (board-with-new-queen col row board)
(cons row board))

(define (board-safe?-gen-iter row step board)  ; step \$B\$O\$I\$A\$iJ}8~\$KC5\$9\$+\$N;XDj(B
(if (null? board) ; \$B\$b\$7!"(Bboard \$B\$rC5\$7\$D\$/\$7\$F\$b(Bunsafe \$B\$J\$b\$N\$,\$J\$+\$C\$?\$J\$i!"(B
#t            ; #t \$B\$rJV\$9!#(B
(let ((new-row (+ row step))) ; new-row \$B\$O!"BP1~\$9\$k(B row \$B\$NCM(B
(if (= new-row (car board)) ; \$B\$b\$7!"(Bboard \$B\$K(B unsafe \$B\$J(B Queen \$B\$,\$"\$C\$?\$i(B
#f                      ; #f \$B\$r\$+\$(\$7!"(B
(board-safe?-gen-iter new-row ; \$B\$5\$b\$J\$/\$P!"```