■

こないだのSICPの例題は、非決定性とか言わんでも内包表記でええやんとか思った

allUniq :: Eq a => [a] -> Bool
allUniq [] = True
allUniq (x:xs) = all (x/=) xs && allUniq xs

solve =
 [[baker,cooper,fletcher,miller,smith]|
   baker<-[1,2,3,4,5],
   cooper<-[1,2,3,4,5],
   fletcher<-[1,2,3,4,5],
   miller<-[1,2,3,4,5],
   smith<-[1,2,3,4,5],
   allUniq[baker,cooper,fletcher,miller,smith],
   baker/=5,
   cooper/=1,
   fletcher/=1 && fletcher/=5,
   miller>cooper,
   abs(smith-fletcher)/=1,
   abs(fletcher-cooper)/=1 ]

この問題は、探索するパターンが5^5=3125通りしかないので、すぐ答がでるけど、"SEND MORE MONEY"問題だと、10^8程度あって、GHCでコンパイルしても3分程度かかった(一個解が見つかった時点で処理を打ち切ればもっと速いけど)。SUDOKUとかは、探索するパターンが更に増えるので、力づくでやっても、まともな時間ではおわらなそう。とはいえ、Mooreの法則がこのまま推移すれば、私が死ぬ頃には、SUDOKUを総当りでやっても一瞬で答がでるような時代になるかもしれないんだな〜。ゆとりってやーね(違

SUDOKUといえば、Wired NewsのDeutschへのインタビューで、量子コンピュータでSUDOKUを解くのを見たということが書いてあったけど、どういうアルゴリズムでどんくらいの時間で解いたんだろうな〜。総当り方式は、誰でも並列化できるので、量子コンピュータ向きなんじゃないかと、全然知らんのに思ったり。
http://www.wired.com/news/technology/0,72734-0.html?tw=wn_technology_10