Exercise 2.42 エイトクイーンパズル完全攻略

（追記20081013:全然完全攻略じゃないので注意！＞Googleから来た人）

と仰々しいタイトルをつけてしもいました
アホ向け（＝俺向け）のベタな解説が余り見当たらなかったので解説してみる。
内容はボード上に置いたクイーンが互いに縦横斜めの位置に重ならないような配置を探して
その組み合わせを列挙せよ、というもの。ゆーめーな問題（らしい）。

まずはテキストのサンプル。

(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
safe?
adjoin-position
の三つ。
配置の組み合わせを作ってってクイーンが安全でない配置をフィルタリングしていく方法、
ちうことはなんとなくわかるんだが無名関数が多くてわかりずらい。
まずqueen-cols呼び出し、でkが0じゃないからすぐfilter……filterの処理内容はsafe?で処理するデータはflatmapの戻り値。
flatmapの処理内容は列の追加で、処理するデータはqueen-colsの戻り値。
でqueen-cols再帰になるのでkが0になるまで降りていくとempty-boardが返ってくると。
empty-boardがflatmapの引数となり、こいつを……(enumereta-interval 1 board-size) = (1 2 3 4 5 6 7 8)のそれぞれの要素にadjoin-position……
と、この辺りで脳内スタックオーバーフロー。テラ低スペックｗ
ちうかempty-boardとadjoin-positionがなにかわからんのでベタには進みようがない。

こゆときは
１．関数一個は「要するになにやってるの？」ちうのを一言に置き換える（脳内リファクタリング）
２．ベタにプログラムを追わずに一旦、一から自分でアルゴリズムを考えて
それにあわせてプログラムを追っていく（脳内モデルを先に作る）。
３．得意な言語でまず実装（２の進化）
などなどあります。

まず１を試みる……といっても主要な関数はだいたいわかりやすい名前ついてるのでラムダの部分をなんとかしたい。
filterのラムダは、safe?なものだけをfilterする。あんま意味ないなｗ
flatmapは……………………脳内スタック（ｒｙ
俺アホかｗｗｗ

ダメ。２を試みる。
まずは最終形のボード上の配置をどう表現するか。
８×８の碁盤目状なのでパッと思いついたのは二次元配列。
00000100
00100000
10000000
00000010
00001000
00000001
01000000
00010000

各マスの状態はクイーンが置いてある／置いてないの二つの状態だけなので0と1。
ってビットしか使えないわけじゃないから二次元の必要ないな。
(3 7 2 8 5 1 4 6)
とすれば一次元でおｋ。
縦一列目の横三列目に一個目のクイーン、縦二列目の横七列目にクイーン、て感じね。
で、問題文とサンプルプログラム（のadjoin-position)から察するに８×８を最初に作るのではなく、
まず一列つくり、列追加の度に新規列のクイーンが安全か調べる模様。
こんで自分アルゴリズムは完成。
あとはこれをサンプルプログラムに対応させつつ読んでみて、仮定が違えばモデル変更、
ちう感じでおｋだと思うのだが、どうも(queen-cols (- k 1))))))のとこでつまずく……っていうか
まー既に理解している状態で書いているのでアレだがqueen-colsの再帰呼び出し、
自分アルゴリズムでは１×８、２×８、３×８、という手順で考えてたのだがサンプルプログラムではなぜか最初
１×１、２×２、３×３……みたいになっているのかと思いこんでうまく追えなかったという。
（が結局自分アルゴリズムで正解だった！）

ちうわけでここでチートしつつ実際の動きを見てみることに。
ネットのソースなど参考にしつつデバッグプリントを入れてみる。
各関数の引数をプリントアウト。
ログが巨大になるのでまずは４×４で（４でもでかいけど）。

(define (queens board-size)
  (define (queen-cols k)  
    (print "queen-cols k:" k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (print " filter positions:" positions)(safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
       (print "  flat-map rests-of-queens:" rest-of-queens)
            (map (lambda (new-row)
           (print "   map new-row:" new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

gosh> k:4
k:3
k:2
k:1
k:0
  rests-of-queens:()
   new-row:1
   new-row:2
   new-row:3
   new-row:4
 positions:(1)
 positions:(2)
 positions:(3)
 positions:(4)
  rests-of-queens:(1)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(2)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(3)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(4)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
 positions:(1 1)
 positions:(2 1)
 positions:(3 1)
 positions:(4 1)
 positions:(1 2)
 positions:(2 2)
 positions:(3 2)
 positions:(4 2)
 positions:(1 3)
 positions:(2 3)
 positions:(3 3)
 positions:(4 3)
 positions:(1 4)
 positions:(2 4)
 positions:(3 4)
 positions:(4 4)
  rests-of-queens:(3 1)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(4 1)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(4 2)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(1 3)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(1 4)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(2 4)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
 positions:(1 3 1)
 positions:(2 3 1)
 positions:(3 3 1)
 positions:(4 3 1)
 positions:(1 4 1)
 positions:(2 4 1)
 positions:(3 4 1)
 positions:(4 4 1)
 positions:(1 4 2)
 positions:(2 4 2)
 positions:(3 4 2)
 positions:(4 4 2)
 positions:(1 1 3)
 positions:(2 1 3)
 positions:(3 1 3)
 positions:(4 1 3)
 positions:(1 1 4)
 positions:(2 1 4)
 positions:(3 1 4)
 positions:(4 1 4)
 positions:(1 2 4)
 positions:(2 2 4)
 positions:(3 2 4)
 positions:(4 2 4)
  rests-of-queens:(2 4 1)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(1 4 2)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(4 1 3)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
  rests-of-queens:(3 1 4)
   new-row:1
   new-row:2
   new-row:3
   new-row:4
 positions:(1 2 4 1)
 positions:(2 2 4 1)
 positions:(3 2 4 1)
 positions:(4 2 4 1)
 positions:(1 1 4 2)
 positions:(2 1 4 2)
 positions:(3 1 4 2)
 positions:(4 1 4 2)
 positions:(1 4 1 3)
 positions:(2 4 1 3)
 positions:(3 4 1 3)
 positions:(4 4 1 3)
 positions:(1 3 1 4)
 positions:(2 3 1 4)
 positions:(3 3 1 4)
 positions:(4 3 1 4)
((3 1 4 2) (2 4 1 3))
gosh>

流石にデバッグプリント見れば嫌でもわかります
まずはqueen-colsの再帰で最下層まで。empty-boardで空リストが返ってくるのでそれを引数にflatmap。
flatmapが一番複雑だと思うのでここを解説。
この時点でまずは
(flatmap λ '())
という形で呼び出される。λは無名関数見やすくするために一文字に置き換えただけね。
で、このλの中の処理が
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))

このラムダ内ラムダを説明するのが難しい……一度わかってしまえば「何も説明することなくね？」
ちう感じなのだがわかってない人に説明できなければ意味がない！
要はここでさっき受け取った空リストは置いておいて、また新しい関数が始まってますよと。
mapなんでリストの各引数に同じ処理をするのだが、まず引数が
(enumerate-interval 1 board-size)
つまり
(1 2 3 4)
ここは再帰の何階層目だろうが毎回同じリスト（ボードサイズが4なら要素4、8なら要素8）が返ってくる。
で、このそれぞれの要素にさっき一旦おいておいた空リスト（flatmapの引数）をadjoin-position……て中身はconsなのでconsすると
((1) (2) (3) (4))
というリストになる。
(cons 1 '())
は
(1)
ですお

これはボードの一列を表してて
a1に置いた場合、a2に置いた場合、a3に置いた場合、a4に置いた場合、てのを表してます。
で、このリストがfilterに渡されます。filterの処理はsafe?。
一列に一個だけクイーンが配置されている状態は「安全」てわけで渡した四つのパターンは全部そのまま返ってきます。
ここまでが(queen-cols 1)の処理。この戻り値を元に(queen-cols 2)が始まるよ！
今度は二列目を追加した16パターンを検証、その結果をもとに(queen-cols 3)、それを元に(queen-cols 4)と検証していって
最後に残ったリストが正解パターン、です。
せっかくなので誰にでもわかるようにまとめようと思ったのだが最後駆け足というかもー力尽きた。