2010/09/01
諸連絡・近況報告
- 【Scrooge】 休止中
- 【Esprit】 休止中
- 【Japonica】 休止中
- 【SmartPointer】 休止中
- 【SquareRoot】 休止中
- ニート対策には人頭税と強制労働を！
- トラックバックを送信したい方は mt-tb と .cgi の間に 2 を入れてください。
- PPL の活動も参照せよ。
投稿者 kagelow : 00:30
だってそっちの方が楽しいから。
職場の友人が、「世界一難しい数独の問題」というのがネット上でニュースになっていると教えてくれた。また、MA-CY さんも weblog で取り上げていた。そこで、陰郎もいっちょやってみようかと思った。
といっても、自分で解くわけじゃない。機械に解かせてみようと思ったのだ。で、できたのがこれ。ZIP ファイルにソースコードと結果の画像が入っている。自分で解きたい方は画像の方は見ないように。
ソースの拡張子は cxx だが、ほとんど C 言語だ。たいていのコンパイラでコンパイルできると思う。実行は、以下のような感じでパラメータとして問題を与える。９×９のマスを、左上から右方向・下方向に数字を羅列する。空欄は０にする。なんとも適当な作りだ。
./numplc.exe 005300000800000020070010500400005300010070006003200080060500009004000030000009700
なんで今回こんなことをやったかというと、何年も前に同じものをでっちあげたことがあったからだ。当時、母と兄が数独にハマっており、自動的に解くプログラムを Microsoft Excel の VBA マクロで作ったら「お前はなんてイヤな奴だ」と言われたことがあった。まぁ楽しみを奪うつもりはなかったのだが、そう言われるのも仕方がないかもしれない。
話を戻そう。で、「世界一難しい問題」ということで、当時の自分のロジックが通用するかどうか試してみたかったのだ。今回は C で書いたが、覚えている限りで実装してみたところ、簡単に誤った解答をハジき出して平気な顔をされた。こりゃいかんとイジり回して完成させたわけだ。結果わかったことは、初歩的な消去法だけでは解答できないということ。「ここが仮に３だったら‥‥‥」などといった仮定のもとに進め、矛盾に行き当たったら仮定を置いたところまで戻って別の選択肢を‥‥‥というのを再帰的に繰り返していかないとダメだった。300～400 行程度のプログラムだが、なかなか面白かった。
計画的に作ったわけじゃないので、あまりキレイなコードじゃないし、最適化の余地が至るところに残っている。それに、そもそもちゃんと C++ で作れば良かった。そうすれば同じロジックで４×４のを解いたりもできたかもしれない。ま、それはそれで。
投稿者 kagelow : 00:30 | コメント (3)
2010/08/21
異環境データのためのデータ抽象
以前、「コンパイル時点での構成体サイズチェック」という記事を書いた。今回は、その続編とでもいうべきお話。
