さすがに毎日SICPばかりだと飽きるので、ちょっと気分転換に、ずいぶん前に挫折した問題に再挑戦してみる。問題は、8行×9列のマスに、下のようなクエスチョンマーク型の図形を9個描くというもの。

 ## 
  #
 ##
 #

 #

出展は、すぐ遊べるオンラインパズルというサイトで紹介されていた「九個の？」
http://www.geocities.jp/haayaa2000/puzzle/packing/nine_q.html

クエスチョンマークは90度ずつ回転して使ってもいいし、裏返しにして使ってもいい。つまり、以下の8種類の図形を、互いに重ならないように、8×9のフィールドに9個配置するパターンを探索する。

 ##   ##   #     #   ###         ###
  #   #              # ## #   # ## #
 ##   ##   #     #   
 #     #   ##   ##        
            #   #    # ## #   # ## #
 #     #   ##   ##   ###         ###

戦略としては、まず左から右に向かって各行を連結し、フィールドを 0~71 の整数からなる1次元のリストと見なす。そして、0~71 の整数を7つ組み合わせたリストとして、1つのクエスチョンマークを定義する。たとえば、上の8つうち、いちばん左のクエスチョンマークをフィールドの一番左上のマスから描き始めたパターンは、(0 1 10 18 19 27 45) と定義できる。とうぜん、あらゆる 7つの整数の組み合わせがクエスチョンマークを形作れるわけじゃないし、フィールドをはみ出すこともできないから、このフィールド上に描くことが可能なクエスチョンマーク（つまり長さ 7 のリスト）の種類は限られる。そこで、フィールド上でクエスチョンマークとして可能なリストをすべて洗い出し、そこから互いに交わらない 9 つのリストを取り出してくることができれば、問題がとけたことになる。

以前は Python でこの問題に挑戦していて、その時点で前半の「可能なクエスチョンマークをすべて洗い出す」ところまではすんなり解決していた。しかし、そのときは、その集合のなかから互いに交わらない 9 つの組み合わせを得る現実的でスマートな方法がわからなくて、挫してしまっていた。無謀にも、とりあえず9つの組み合わせをすべて求めてからfilterしようとしたりもしたんだけど、せいぜい4つの組み合わせを求めるまでが600Hz/512MのEDENマシンには限界だったようで、それ以上は仮想メモリもすべて枯渇して永遠に計算が進まず……むー（ちなみに、可能なクエスチョンマークは全部で208パターンある）。組み合わせを作り出しつつfilterするようにすれば、時間はかかってもとにかく解くことはできるだろうなあと妄想しつつ、get-combination を定義したりもしてみたんだけど。

いまになって再挑戦する気になったのは、Gaucheに combination-fo-each というプロシージャが用意されていたから。9つのクエスチョンマークの組み合わせを得つつ、それらが互いに交わらないか調べるのには、こんな get-distinct-n プロシージャを用意すればいいはず。

(define (distinct? sets)
  (= (length (apply lset-union = sets))
     (* (length sets) (length (car sets)))))

(define (get-distinct-n set n)
  (combinations-for-each 
   (lambda (s) 
     (if (distinct? s)
         (begin (display s) (newline))))
   set
   n))

可能なクエスチョンマークの集合を valid-list とすれば、

(get-distict-n valid-list 9)

あとは、計算が終わるのを気長にまちつつ、ぶログチェックでもしていればいいはず。ガーベジコレクションばんざい！



ただし、まだ計算終わってないので、結果は未確認。