昨日の夜、Sudokuをやらされてヘロヘロに疲れてしまったよ、という話。Sudokuは、日本で広がり、その後イギリス経由アメリカでも人気者の数字穴埋めパズル。詳細はSudokuってナンジャ？を見て欲しい。
来週はRSA Conferenceというコンピュータセキュリティ関係の展示会がある。ダンナの元に、その出展企業からのDMがきた。DMにはSudokuが付いていて、「解けたら、それを展示ブースに持っていくと景品をくれる」ということになっていた。で、ダンナは、Sudoku初体験にトライしたのだが、やってみたら解けなかった、しかも油性サインペンで書いちゃったので修正不能であった、ということで、ムキになってインターネットから新しい問題をダウンロード、解き始めたのだが、またもや解けず、「ぎゃー」とか「くぉー」とか奇声を発している。
私はSudokuをやったことがなかったのだが、ルールを聞くだに、「解けない」なんてことはなさそう。
「バカじゃん？」
とダンナの努力をせせら笑ったら、自分がやっているのと同じ問題を再度プリントアウトして
「そんなに言うなら解いてみろ。勝負だ。」
と渡された。
既に1時間以上自分がやっている問題を途中からやらせて、それで勝負かよ、と思ったのだが、まぁやり始めた。
「もしかしたら、簡単に解ける抜け道があるのでは」
と、書いてある数字の登場頻度やら、並びやらをタメツスガメツしたのだが、（少なくとも私には）何も法則性が見つからなかったので、ビューティフルな解法を探すのは2分ほどで諦め、ガリガリと解き始めた。個別のマスに入りうる数字をぜーんぶ書き出してみると、「この数字しか入りようがない」というマスが登場する。で、それを埋めると、連鎖的に「この数字しか入りようがない」というマスが登場していく、、、、というもの。
うううう、超面倒くさい。こういう緻密な努力がモノをいう作業が苦手だから、会計とか法律の道に進まなかったのに・・・と泣きながらカリカリと作業を進めたところ、まぁしばらくしたらできた。
ところが、1時間前からやってるダンナはまだ苦戦中であった。
「論理的にチマチマと解き進んで完成させる」
という正攻法ではなく、
「一か八かで適当な数字を埋めていって、何とか最後につじつまを合わせる」
といういい加減なやり方を取っていたため、途中で破綻してはやり直していたらしい。（時折発せられる奇声は、この破綻の際のものだったようだ）
一応ダンナは元宇宙航空エンジニア、アメリカで言うところのRocket Scientist。普段は、地味で緻密な頭脳労働が得意なのに、らしくもなく超いい加減なやり方を取っていた模様。彼が苦闘したSudokuの紙を見ると、敗因は
「字が汚い」
ということだったようだ。ミミズがのたくったような数字を書き散らかしていたため、何がなんだかわからなくなっていたのである。とはいえ、負けは負け。
勝者である私が
「けけけ、今日の皿洗いはお前だ」
とせせら笑ったら、皿を洗った後、「rematch！」と言って、「Evil level」なる超難問級のSudoku新問題をプリントアウトしてきてやらされた。しかし、私の頭脳はウルトラマンと似ているのである。3分たつと力尽きてしまうのだ。なので、もうヘロヘロ。集中力が続かず、死にそうになり、ついにはExcelを使ってやりました。しんどかった・・・。
しかし、Sudoku、クロスワードパズルみたいに、「いろいろな言葉が入りうる」みたいな揺れは全然なく、論理的に力技で解けちゃう。必要なのは注意力と根気だけ。クリエイティビティは全然いらない。つまらん。なぜこれが人気なのか？
それとも、何かクリエイティブでエレガントな解き方があるのでせうか？誰か教えて～。
On Off and Beyond 
ちょうど、最新号のIEEE Spectrumに”Sudoku Science”という数独の記事がでていましたね。(日本で読んでるのでちょっと遅れてるかもしれませんが)
曰く、SudokuはNP完全問題の一つとの事。chikaさんご所望の「クリエイティブでエレガントな解き方」は残念ながら簡単ではないようですね。
とはいえ、その記事には”if a player computes all possible digits for each cell in a subgrid and notices that two cells have exactly the same two choices, those two digits can be eliminated from all other cells in the subgrid.”なんていう実用的なテクニックが記載されています。お持ちでしたらご一読を。
いいねいいね
コツコツとやるようなパズルがこんなに世界に広まるっていうのは意外ですね。これは本当に偉大な暇つぶしかも知れない。
いいねいいね
コツコツとやるようなパズルがこんなに世界に広まるっていうのは意外ですね。これは本当に偉大な暇つぶしですね。
いいねいいね
okagawa-san,
http://www.spectrum.ieee.org/feb06/2809
これですね。そうか、NP-completeか。世界の頭脳が悩み続けている問題を、私ごときが2分で解決できるはずがなかったですね。へへ。
Now many state-of-the-art hardware verification programs incorporate Gomes’s findings. “The idea is, basically, you run your program, and if it’s taking too long you restart it” with a new ordering, Gomes says, “because your computer may end up getting into an unlucky run, and hopefully the next run will be a lucky one.”
というところを読んで、笑ってしまいました。この、unlucky programは、まさにうちのダンナじゃー。私がリセットしてあげなかったら、いつまでも、unlucky pathsをトライし続けていたに違いない。時々
「この人、ロボットじゃないの?」
と思うんですが、やっぱりヤツの頭の中は（AIじゃない）普通のプログラムでrunしているようです。ははっはー。
Ted Weapon-san,
上記のIEEEの記事によると、Sudokuの流行でNP問題の解決が近づくのでは！ということで、だとしたら、本当に偉大な暇つぶしです。Sudokuが、ルービックキューブなみの流行として扱われております、はい。
いいねいいね
例え機械的に解けるものでも、「上達」という要素があると人ははまりますね。数独の場合、だんだんメモしないでも頭の中で試せる組み合わせが増えてきて、速く解けるようになってくるのが気持ちいいんじゃないでしょうか。
(もっとも、ジグゾーパズルが長く親しまれているように、単調な作業だがとにかく続けていれば何かを達成できる、というのに惹かれる人も多いですな。)
いいねいいね
こんにちわ、chika-san さん
Sudoku 良いですねー。確かにエレガントな解き方はないですね。完全に消去法で埋めていくしかないと思います。埋まり出すと早いんですけどねｗ。普段手帳に、HARDかEVILを書き写しておいて、時間が空いた時に少しずつ解いてます。時間が掛かりますが(苦笑)
そーいえば、先日インテルの方に逢った際に、解いてる所を見られて「Oh! Sandoku!」とほほえまれました。勘違いかもしれませんが、もしかしたら別の呼び方が在るのかもしれません。まっそれだけですｗ
いいねいいね
はじめまして。お会いしたこと無いですがたぶん近くにオフィスあります。
NP-complete かどうか考えたことはありませんでしたが完全に消去法でしか解けない問題はたぶん悪い問題（解き味が悪いと表現される）です。ニコリなんかの老舗パズル雑誌では解ける道筋はあらかじめ考えて問題が作られてます。それでも難問クラスだと２分じゃ絶対無理ですし、解法としては「この数字しか入らない」マスを探す、としか言いようがないですが。
いいねいいね
皆さん盛り上がってるんですね。 私も挑戦してみました。
超Coolではないですが、消去法を少しばかり解かりやすくした方法で解を得ました。
プログラムに出来るかどうか、うちのプログラマに聞いてみます。 プログラムにしたら頭を使わなくなって、本末転倒？
いいねいいね
http://www.nikoli.co.jp/puzzles/1/
参考になるか不明ですが、解き方のヒント指南が
上記ＵＲＬに紹介されています。
いいねいいね
先生と侍と将軍と力士の SUDOKU
去年、「アメリカで数独が大ブレイク」
と書きましたが、「SUDOKU」のブームはとどまるところを知らないようです。シリコンバレー
でも同様のようですが、ワシントンでも凄いですよ。先週入ったこちらの有名書店には、「SUDOKU」の関連本ばかりを集めた「SUDOKU コーナー」…
いいねいいね
はじめまして
確かに数独はハマる人とそうでない人の差が激しい感じがしますね。
ただ、難しい問題は単純に消去法だけでは解けないものもあります。
私のサイトでも解き方についてちょっと解説しています。参考になればどうぞ。
いいねいいね
a1-san,
ひえー、すごいですねー。こんなにたくさんのヒントがあるんですね。凝り性ですねー！
いいねいいね