2010-09-01-01-だってそっちの方が楽しいから。 - project-enigma

2010-09-01-01-だってそっちの方が楽しいから。

>> Site top >> weblog >> 月別アーカイブ >> 2010年09月のlog >> 2010-09-01-01-だってそっちの方が楽しいから。

最終更新日付:2014/01/03 07:47:40


だってそっちの方が楽しいから。

2010 年 09 月 01 日

職場の友人が、「世界一難しい数独の問題」というのがネット上でニュースになっていると教えてくれた。また、MA-CY さんも weblog で取り上げていた。そこで、陰郎もいっちょやってみようかと思った。

といっても、自分で解くわけじゃない。機械に解かせてみようと思ったのだ。で、できたのがこれ。ZIP ファイルにソースコードと結果の画像が入っている。自分で解きたい方は画像の方は見ないように。

ソースの拡張子は cxx だが、ほとんど C 言語だ。たいていのコンパイラでコンパイルできると思う。実行は、以下のような感じでパラメータとして問題を与える。9×9のマスを、左上から右方向・下方向に数字を羅列する。空欄は0にする。なんとも適当な作りだ。

./numplc.exe  005300000800000020070010500400005300010070006003200080060500009004000030000009700

なんで今回こんなことをやったかというと、何年も前に同じものをでっちあげたことがあったからだ。当時、母と兄が数独にハマっており、自動的に解くプログラムを Microsoft Excel の VBA マクロで作ったら「お前はなんてイヤな奴だ」と言われたことがあった。まぁ楽しみを奪うつもりはなかったのだが、そう言われるのも仕方がないかもしれない。

話を戻そう。で、「世界一難しい問題」ということで、当時の自分のロジックが通用するかどうか試してみたかったのだ。今回は C で書いたが、覚えている限りで実装してみたところ、簡単に誤った解答をハジき出して平気な顔をされた。こりゃいかんとイジり回して完成させたわけだ。結果わかったことは、初歩的な消去法だけでは解答できないということ。「ここが仮に3だったら‥‥‥」などといった仮定のもとに進め、矛盾に行き当たったら仮定を置いたところまで戻って別の選択肢を‥‥‥というのを再帰的に繰り返していかないとダメだった。300〜400 行程度のプログラムだが、なかなか面白かった。

計画的に作ったわけじゃないので、あまりキレイなコードじゃないし、最適化の余地が至るところに残っている。それに、そもそもちゃんと C++ で作れば良かった。そうすれば同じロジックで4×4のを解いたりもできたかもしれない。ま、それはそれで。

 

コメント

goya - 09/01/2010 11:03:43 AM

「世界一難しい問題」というのは、人力のみで解くという意味だけでなく、プログラミング言語で解かせるにしても『エレガントな』解法を示す、というハードルを如何にクリアするか? につきるのではないかと愚考します。私は人力でしか解けません…

1画面BASICプログラムとか 某FM-7用ツール(ダンプすると単なるメッセージだが、機械語でもきちんと動作する)とか …憧れる

MA-CY - 09/02/2010 08:09:43 AM

さすが陰郎さん、アプローチが違いますね^^

ちなみに私は何とか人力で解きましたが、「「ここが仮に3だったら‥‥‥」などといった仮定のもとに進め、矛盾に行き当たったら仮定を置いたところまで戻って別の選択肢を‥‥‥というのを再帰的に繰り返していかないとダメ」というあたりは、全くやり方が同じです^^;

kagelow - 09/02/2010 10:57:45 PM

えぇと、私は人力では解けません。(笑

やればできるのかもしれませんが、根気が続かないんですよね。多分、手順やロジックといったものをプログラムにすることの方を楽しいと思ってしまうからでしょう。

同様に、将棋やチェスの類いも苦手だったりします。コンピュータゲームの将棋やチェスのエンジンを考える方が楽しそう。

このページにコメントする

 

このページのタグ

Page tag : 開発

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.