Gaucheで魔方陣に挑戦

scheme

なんかこんな感じで解きたかったのだがzip(list)が期待する動きと違った

>>(use gauche.sequence)
=>#<undef>
>>(use util.combinations)
=>#<undef>
>>(filter (lambda (x) (eq? 9 (length (map car (group-sequence (sort (fold append () x))))))) (combinations (filter (lambda (x) (eq? 15 (apply + x))) (combinations (iota 9 1) 3)) 3))
=>(((1 5 9) (2 6 7) (3 4 8)) ((1 6 8) (2 4 9) (3 5 7)))

ここまではパーフェクト。おそらく魔方陣の縦と横の関係を表している。

だが、zipが・・・そうか、schemeのzip(list)は可変引数を取るのでhaskellと違うんだ。

>>(zip (map permutations (filter (lambda (x) (eq? 9 (length (map car (group-sequence (sort (fold append () x))))))) (combinations (filter (lambda (x) (eq? 15 (apply + x))) (combinations (iota 9 1) 3)) 3))))
=>(((((1 5 9) (2 6 7) (3 4 8)) ((1 5 9) (3 4 8) (2 6 7)) ((2 6 7) (1 5 9) (3 4 8)) ((2 6 7) (3 4 8) (1 5 9)) ((3 4 8) (1 5 9) (2 6 7)) ((3 4 8) (2 6 7) (1 5 9)))) ((((1 6 8) (2 4 9) (3 5 7)) ((1 6 8) (3 5 7) (2 4 9)) ((2 4 9) (1 6 8) (3 5 7)) ((2 4 9) (3 5 7) (1 6 8)) ((3 5 7) (1 6 8) (2 4 9)) ((3 5 7) (2 4 9) (1 6 8)))))

いかん、途中になってしまったが取りあえず着陸すると以下の通り。
結局総当たりかよ。下手に考えるよりこっちの方が楽だった。

>>(define at list-ref)
=>at
>>(filter (lambda (x) (and (eq? 15 (+ (at x 0) (at x 1) (at x 2))) (eq? 15 (+ (at x 3) (at x 4) (at x 5))) (eq? 15 (+ (at x 6) (at x 7) (at x 8))) (eq? 15 (+ (at x 0) (at x 3) (at x 6))) (eq? 15 (+ (at x 1) (at x 4) (at x 7))) (eq? 15 (+ (at x 2) (at x 5) (at x 8))))) (permutations (iota 9 1)))
=>((1 5 9 6 7 2 8 3 4) (1 5 9 8 3 4 6 7 2) (1 6 8 5 7 3 9 2 4) (1 6 8 9 2 4 5 7 3) (1 8 6 5 3 7 9 4 2) (1 8 6 9 4 2 5 3 7) (1 9 5 6 2 7 8 4 3) (1 9 5 8 4 3 6 2 7) (2 4 9 6 8 1 7 3 5) (2 4 9 7 3 5 6 8 1) (2 6 7 4 8 3 9 1 5) (2 6 7 9 1 5 4 8 3) (2 7 6 4 3 8 9 5 1) (2 7 6 9 5 1 4 3 8) (2 9 4 6 1 8 7 5 3) (2 9 4 7 5 3 6 1 8) (3 4 8 5 9 1 7 2 6) (3 4 8 7 2 6 5 9 1) (3 5 7 4 9 2 8 1 6) (3 5 7 8 1 6 4 9 2) (3 7 5 4 2 9 8 6 1) (3 7 5 8 6 1 4 2 9) (3 8 4 5 1 9 7 6 2) (3 8 4 7 6 2 5 1 9) (4 2 9 3 7 5 8 6 1) (4 2 9 8 6 1 3 7 5) (4 3 8 2 7 6 9 5 1) (4 3 8 9 5 1 2 7 6) (4 8 3 2 6 7 9 1 5) (4 8 3 9 1 5 2 6 7) (4 9 2 3 5 7 8 1 6) (4 9 2 8 1 6 3 5 7) (5 1 9 3 8 4 7 6 2) (5 1 9 7 6 2 3 8 4) (5 3 7 1 8 6 9 4 2) (5 3 7 9 4 2 1 8 6) (5 7 3 1 6 8 9 2 4) (5 7 3 9 2 4 1 6 8) (5 9 1 3 4 8 7 2 6) (5 9 1 7 2 6 3 4 8) (6 1 8 2 9 4 7 5 3) (6 1 8 7 5 3 2 9 4) (6 2 7 1 9 5 8 4 3) (6 2 7 8 4 3 1 9 5) (6 7 2 1 5 9 8 3 4) (6 7 2 8 3 4 1 5 9) (6 8 1 2 4 9 7 3 5) (6 8 1 7 3 5 2 4 9) (7 2 6 3 4 8 5 9 1) (7 2 6 5 9 1 3 4 8) (7 3 5 2 4 9 6 8 1) (7 3 5 6 8 1 2 4 9) (7 5 3 2 9 4 6 1 8) (7 5 3 6 1 8 2 9 4) (7 6 2 3 8 4 5 1 9) (7 6 2 5 1 9 3 8 4) (8 1 6 3 5 7 4 9 2) (8 1 6 4 9 2 3 5 7) (8 3 4 1 5 9 6 7 2) (8 3 4 6 7 2 1 5 9) (8 4 3 1 9 5 6 2 7) (8 4 3 6 2 7 1 9 5) (8 6 1 3 7 5 4 2 9) (8 6 1 4 2 9 3 7 5) (9 1 5 2 6 7 4 8 3) (9 1 5 4 8 3 2 6 7) (9 2 4 1 6 8 5 7 3) (9 2 4 5 7 3 1 6 8) (9 4 2 1 8 6 5 3 7) (9 4 2 5 3 7 1 8 6) (9 5 1 2 7 6 4 3 8) (9 5 1 4 3 8 2 7 6))

折角なのでマクロデビュー

(define-syntax f (syntax-rules () ((f x a b c) (eq? 15 (+ (list-ref x a) (list-ref x b) (list-ref x c))))))
(filter (lambda (x) (and (f x 0 1 2) (f x 3 4 5) (f x 6 7 8) (f x 0 3 6) (f x 1 4 7) (f x 2 5 8))) (permutations (iota 9 1)))

かなり富豪にやってしまった。

あ、ちなみに答えのリストは以下のように並ぶので注意。

1 2 3
4 5 6
7 8 9

よし、ついでに大域脱出に挑戦だ。

>>(use util.combinations)
=>#<undef>
>>(define-syntax f (syntax-rules () ((f x a b c) (eq? 15 (+ (list-ref x a) (list-ref x b) (list-ref x c))))))
=>#<undef>
>>(call/cc (lambda (c) (permutations-for-each (lambda (x) (if (and (f x 0 1 2) (f x 3 4 5) (f x 6 7 8) (f x 0 3 6) (f x 1 4 7) (f x 2 5 8)) (c x)))  (iota 9 1))))
=>(1 5 9 6 7 2 8 3 4)

は、はやい。なんて速いんだろう。
permutaions-for-eachと大域脱出はセットでおぼえておこう。着陸に使えそうだ。

でも 実は　permutaions(-for-each)は全ての解を出すときには不向きだなぁ
生成アルゴリズム中にある一定の幅のスキップを入れないと真なる意味で高速化は不可能だ。
例：最初の３桁で足して１５にならなかったら　それ以後計算しない。
って人はそれをprologという。（笑

追記12/13:魔方陣は斜めも必要らしい。