問題2-42 (2.2.3 Sequences as Conventional Interfaces)

かの有名なn-queen問題をschemeで解くよ!!

• mNC[âè(N Queens Problem)

昔prologで8-queen問題解くプログラム書くのにクソ時間かかった気がするんですけど、今回も結構かかった。

SICPは優しいので、こんなスケルトンを用意してくれています。

(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))

後はこれにあうようにempty-boardだとかadjoin-positionだとかを埋めていけばいいんですけど、まずはどうやってqueenの配置を表現するかという問題がある。
今回は、こんな風にしたよ！oがqueenのある場所です。

o	x	x
x	x	o
x	o	x

この配置は

((1 1) (2 3) (3 2))

と表す！これで決まり！

あとはそれぞれの関数を埋めていくだけだー。

(define (adjoin-position new-row k one-result)
  (append one-result (list (list k new-row))))

adjoin-positionはこんな風に、あらたに置くqueenの位置を追加してくれる。

gosh> (adjoin-position 2 3 (list (list 1 1) (list 2 3)))
((1 1) (2 3) (3 2))

ボードに何もおいてない状態はこうやって表すことになります。

(define empty-board ())

作り上げた回答が正しいかどうかは、safe?っていう述語で判定するよ。
引数kは、今queen置いた列番号です。
同じ行にあるかどうかを判定するためのアイディアは単純で、同じ行番号を持つqueenをfilterでリストとして抜き出してみて、そのリストがnullかどうかで判定している。
同じ列にないことは既に担保されているので無視。
斜めの位置にあるかどうかは、2つのqueenの行番号同士を引いたものの絶対値と、列番号同士を引いたものの絶対値が同じかどうかで判定できるような気がした。

(define (safe? k positions)
  (let ((new-column (cadr 
		     (car (last-pair positions)))))
    (and (null? (filter (lambda (x) (and (= new-column (cadr x))
					 (not (= k (car x)))))
			positions))
	 (null? (filter (lambda (x) (and (= (abs (- k (car x)))
					    (abs (- new-column (cadr x))))
					 (not (= k (car x)))))
			positions)))))

というわけで、4-queen問題を解いてみますね！

gosh> (queens 4)
(((1 2) (2 4) (3 1) (4 3)) ((1 3) (2 1) (3 4) (4 2)))

これはどういう回答かというと、解には2種類あるということになる。
それぞれ、こんな配置です。

x	x	o	x
o	x	x	x
x	x	x	o
x	o	x	x

x	o	x	x
x	x	x	o
o	x	x	x
x	x	o	x