SICP 問題 2.42 エイトクイーンパズル
ex-2.42 エイトクイーンパズルが終わりました(2.43もエイトクイーンパズルだけど).
全く何も見ないで解くのは無理だなーと思ったので、答えを見て動かしながら手続きどの様に動作するのか？を理解するに留めました。 まぁこういうのは「知っているか、知らないか」「知っているけど、使いこなせない」「知っていてるし、使いこなせる(応用して実務で使える)」だと思うのでまずは「知れた」から良かったかなと。 (もちろん知らないで自力で解ける人はいるし凄い！僕には無理なだけ)
; ex-2.42 ; rest-of-queensは最初のk-1列にk-1個のクイーンを置く方法である ; new-rowはk列目にクイーンの置ける行の案である ; - [x] adjoin-positionは盤上の位置の集合の表現を実装し、位置の集合に新しい場所の座標を連結する手続き ; - [x] empty-boardは場所のから集合を表現する ; - [x] safe?は他のクイーンに対してk番目のクイーンが安全な場所か?(他のクイーンは互いに安全である事が保証されているので新しいクイーンだけ調べれば良い) ; 参考 : https://www.serendip.ws/archives/776 ; > (queens 4) ; (((2 . 1) (4 . 2) (1 . 3) (3 . 4)) ((3 . 1) (1 . 2) (4 . 3) (2 . 4))) (define (queens board-size) (define (queen-cols k) ; 板の最初のk列にクイーンを置く全ての方法の並びを返す (if (= k 0) (list empty-board) (filter ; (fleter predicate sequence) (lambda (positions) (safe? k positions)) ; predicate ; (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row 2 rest-of-queens)) '(1 2 3 4))) '(((1 1)))) ; (((1行目 2列目) (1行目 1列目)) ...) ; (((1 2) (1 1)) ((2 2) (1 1)) ((3 2) (1 1)) ((4 2) (1 1))) (flatmap ; sequence (lambda (rest-of-queens) ; 1,2,3,4 k enumerate-intervalなnew-row(1 2 3 4) ; (map (lambda (new-row) (cons (list new-row 1) ())) (list 1 2 3 4)) ; k = 1 ; 行 列 ; (((1 1)) ((2 1)) ((3 1)) ((4 1))) ; k = 2 ; (((1 2)) ((2 2)) ((3 2)) ((4 2))) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))); new-row (queen-cols (- k 1)))))) ; rest-of-queens, queen-colsの再帰 (queen-cols board-size)) ; k (define empty-board ()) ; rowはクイーンを置く行の案. 1,2,3,4 ; kは引数board-sizeと-1されていく値. 4,3,2,1 ; rest-of-queensは() ; (cons (list 1or2or3or4 1) ()) (define (adjoin-position new-row k rest-of-queens) (cons (list new-row k) rest-of-queens)) (define (safe? k positions) (print "poisitions " positions) ; 行 列 ; ((1 1)) ; ((2 1)) ; ((3 3) (1 2) (3 1)) ; kth : (3 3) ; rest : ((1 2) (3 1)) (let ((kth (car positions))) (define (iter rest) (print "kth " kth ", rest: " rest) ; conflictsするかnullになるまでiterを回す ; nullになった = (3行 3列)と(1 2), (3 3)と(3 1)すべて問題なし (cond ((null? rest) #t) ((conflicts? (car rest) kth) #f) (else (iter (cdr rest))))) (iter (cdr positions)))) ; a (3 3) ; b (1 2) ; なんでこれでconflicts判定できるのかよくわかってない。 ; ここはこういうロジックなんだなーくらいで良いかも。 ; 2週目やる時はここもちゃんと理解したいな(別ロジックでも良い)。 (define (conflicts? a b) (let ( ; (abs (- 3 1)) => 2 (dx (abs (- (car a) (car b)))) ; (abs (- 3 2)) => 1 (dy (abs (- (cadr a) (cadr b))))) (cond ((= dx 0) #t) ((= dy 0) #t) ((= dx dy) #t) (else #f)))) ; いつもflatmapの挙動を忘れるのでメモ (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (cons (list new-row 1) rest-of-queens)) (list 1 2 3 4))) (list 1 2 3)) ; (((1 1) . 1) ((2 1) . 1) ((3 1) . 1) ((4 1) . 1) ; ((1 1) . 2) ((2 1) . 2) ((3 1) . 2) ((4 1) . 2) ; ((1 1) . 3) ((2 1) . 3) ((3 1) . 3) ((4 1) . 3))
結果
gosh$ (queens 4) poisitions ((1 1)) kth (1 1), rest: () poisitions ((2 1)) kth (2 1), rest: () poisitions ((3 1)) kth (3 1), rest: () poisitions ((4 1)) kth (4 1), rest: () poisitions ((1 2) (1 1)) kth (1 2), rest: ((1 1)) poisitions ((2 2) (1 1)) kth (2 2), rest: ((1 1)) poisitions ((3 2) (1 1)) kth (3 2), rest: ((1 1)) kth (3 2), rest: () poisitions ((4 2) (1 1)) kth (4 2), rest: ((1 1)) kth (4 2), rest: () poisitions ((1 2) (2 1)) kth (1 2), rest: ((2 1)) poisitions ((2 2) (2 1)) kth (2 2), rest: ((2 1)) poisitions ((3 2) (2 1)) kth (3 2), rest: ((2 1)) poisitions ((4 2) (2 1)) kth (4 2), rest: ((2 1)) kth (4 2), rest: () poisitions ((1 2) (3 1)) kth (1 2), rest: ((3 1)) kth (1 2), rest: () poisitions ((2 2) (3 1)) kth (2 2), rest: ((3 1)) poisitions ((3 2) (3 1)) kth (3 2), rest: ((3 1)) poisitions ((4 2) (3 1)) kth (4 2), rest: ((3 1)) poisitions ((1 2) (4 1)) kth (1 2), rest: ((4 1)) kth (1 2), rest: () poisitions ((2 2) (4 1)) kth (2 2), rest: ((4 1)) kth (2 2), rest: () poisitions ((3 2) (4 1)) kth (3 2), rest: ((4 1)) poisitions ((4 2) (4 1)) kth (4 2), rest: ((4 1)) poisitions ((1 3) (3 2) (1 1)) kth (1 3), rest: ((3 2) (1 1)) kth (1 3), rest: ((1 1)) poisitions ((2 3) (3 2) (1 1)) kth (2 3), rest: ((3 2) (1 1)) poisitions ((3 3) (3 2) (1 1)) kth (3 3), rest: ((3 2) (1 1)) poisitions ((4 3) (3 2) (1 1)) kth (4 3), rest: ((3 2) (1 1)) poisitions ((1 3) (4 2) (1 1)) kth (1 3), rest: ((4 2) (1 1)) kth (1 3), rest: ((1 1)) poisitions ((2 3) (4 2) (1 1)) kth (2 3), rest: ((4 2) (1 1)) kth (2 3), rest: ((1 1)) kth (2 3), rest: () poisitions ((3 3) (4 2) (1 1)) kth (3 3), rest: ((4 2) (1 1)) poisitions ((4 3) (4 2) (1 1)) kth (4 3), rest: ((4 2) (1 1)) poisitions ((1 3) (4 2) (2 1)) kth (1 3), rest: ((4 2) (2 1)) kth (1 3), rest: ((2 1)) kth (1 3), rest: () poisitions ((2 3) (4 2) (2 1)) kth (2 3), rest: ((4 2) (2 1)) kth (2 3), rest: ((2 1)) poisitions ((3 3) (4 2) (2 1)) kth (3 3), rest: ((4 2) (2 1)) poisitions ((4 3) (4 2) (2 1)) kth (4 3), rest: ((4 2) (2 1)) poisitions ((1 3) (1 2) (3 1)) kth (1 3), rest: ((1 2) (3 1)) poisitions ((2 3) (1 2) (3 1)) kth (2 3), rest: ((1 2) (3 1)) poisitions ((3 3) (1 2) (3 1)) kth (3 3), rest: ((1 2) (3 1)) kth (3 3), rest: ((3 1)) poisitions ((4 3) (1 2) (3 1)) kth (4 3), rest: ((1 2) (3 1)) kth (4 3), rest: ((3 1)) kth (4 3), rest: () poisitions ((1 3) (1 2) (4 1)) kth (1 3), rest: ((1 2) (4 1)) poisitions ((2 3) (1 2) (4 1)) kth (2 3), rest: ((1 2) (4 1)) poisitions ((3 3) (1 2) (4 1)) kth (3 3), rest: ((1 2) (4 1)) kth (3 3), rest: ((4 1)) kth (3 3), rest: () poisitions ((4 3) (1 2) (4 1)) kth (4 3), rest: ((1 2) (4 1)) kth (4 3), rest: ((4 1)) poisitions ((1 3) (2 2) (4 1)) kth (1 3), rest: ((2 2) (4 1)) poisitions ((2 3) (2 2) (4 1)) kth (2 3), rest: ((2 2) (4 1)) poisitions ((3 3) (2 2) (4 1)) kth (3 3), rest: ((2 2) (4 1)) poisitions ((4 3) (2 2) (4 1)) kth (4 3), rest: ((2 2) (4 1)) kth (4 3), rest: ((4 1)) poisitions ((1 4) (2 3) (4 2) (1 1)) kth (1 4), rest: ((2 3) (4 2) (1 1)) poisitions ((2 4) (2 3) (4 2) (1 1)) kth (2 4), rest: ((2 3) (4 2) (1 1)) poisitions ((3 4) (2 3) (4 2) (1 1)) kth (3 4), rest: ((2 3) (4 2) (1 1)) poisitions ((4 4) (2 3) (4 2) (1 1)) kth (4 4), rest: ((2 3) (4 2) (1 1)) kth (4 4), rest: ((4 2) (1 1)) poisitions ((1 4) (1 3) (4 2) (2 1)) kth (1 4), rest: ((1 3) (4 2) (2 1)) poisitions ((2 4) (1 3) (4 2) (2 1)) kth (2 4), rest: ((1 3) (4 2) (2 1)) poisitions ((3 4) (1 3) (4 2) (2 1)) kth (3 4), rest: ((1 3) (4 2) (2 1)) kth (3 4), rest: ((4 2) (2 1)) kth (3 4), rest: ((2 1)) kth (3 4), rest: () poisitions ((4 4) (1 3) (4 2) (2 1)) kth (4 4), rest: ((1 3) (4 2) (2 1)) kth (4 4), rest: ((4 2) (2 1)) poisitions ((1 4) (4 3) (1 2) (3 1)) kth (1 4), rest: ((4 3) (1 2) (3 1)) kth (1 4), rest: ((1 2) (3 1)) poisitions ((2 4) (4 3) (1 2) (3 1)) kth (2 4), rest: ((4 3) (1 2) (3 1)) kth (2 4), rest: ((1 2) (3 1)) kth (2 4), rest: ((3 1)) kth (2 4), rest: () poisitions ((3 4) (4 3) (1 2) (3 1)) kth (3 4), rest: ((4 3) (1 2) (3 1)) poisitions ((4 4) (4 3) (1 2) (3 1)) kth (4 4), rest: ((4 3) (1 2) (3 1)) poisitions ((1 4) (3 3) (1 2) (4 1)) kth (1 4), rest: ((3 3) (1 2) (4 1)) kth (1 4), rest: ((1 2) (4 1)) poisitions ((2 4) (3 3) (1 2) (4 1)) kth (2 4), rest: ((3 3) (1 2) (4 1)) poisitions ((3 4) (3 3) (1 2) (4 1)) kth (3 4), rest: ((3 3) (1 2) (4 1)) poisitions ((4 4) (3 3) (1 2) (4 1)) kth (4 4), rest: ((3 3) (1 2) (4 1)) (((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))
