数独

Feb 19, 2008

数独 1年2か月

 ずっと持ち歩いていた数独の本の全111問がようやく終了した。いつから始めたのかなとこのブログを検索したら,2006年12月だったらしい(→参照)。1年2か月かかったことになる。この間,本につけていたカバーは2回取り替えた。
 一応上級編なので,集中してやったとしても1問に30分以上かかる。しかも実際には通勤電車の一部など断片的な時間に取り組むので,そのたびに状況を思い出すだけで時間がかかり,通算ではかなりの時間を使った。
 さて,次の本を買いにいかなくては。

| | Comments (0) | TrackBack (0)

Jan 12, 2008

毎日数独

 『毎日新聞』夕刊の1面題字下に数独の問題が毎日掲載されている。どうやら去年の12月10日かららしい。連日でしかも1面にというのがすごい。

 ドイツの新聞 Sueddeutsche のオンライン版には前から数独のページがある。難易度を3段階から選び,解答を書き込んで正答と照合できるようになっている。ランダムに出題されているらしく,アクセスのたびに違う問題が出てくる。
 最初に誰かからこのサイトのことを聞いてアクセスしてみたとき,Sueddeutsche という題字が,一瞬 Sudoku に見えてしまった。

| | Comments (0) | TrackBack (0)

Dec 26, 2007

数独解析プログラム

 前回数独のことを書いたのはちょうど1年前のことである。そのとき新しく始めたと書いた新書版の本に,その後も断続的に取り組んでいるが,まだ終わっていない。全部で111問あるうちの94問目まできたところである。

 ネット上には,数独を解くPC用プログラムもいろいろあるようだ。しかし,数独はマス目を埋めるプロセスがすべてだから,プログラムに解答を教えてもらってもまったくありがたくない。
 ひとつだけたまにお世話になっているのは suudo9.xls というプログラムである(→所在地)。これは,単純に基本ルールを適用していくだけでどこまで解けるかを,Excelのシート上で解析するものである。(したがって,あるレベルまでの問題は完全に解けてしまう。)
 上記の本の問題で,通常の方法で埋めていき,空白があと27マスになったところでそれ以上どうしても進まないということがあった。そこで,この問題の解析を suudo9.xls に命じたところ,私がたどりついたのと同じ状態で止まった。これで,ここから先は「仮定法」(→参照)を用いないと解けないとわかる。すなわち,suudo9.xls と「見解」が一致すれば,安心して(?)仮定法の適用を始めることができる。
 プログラム作者の言葉では「解析レベルは90%ぐらい」ということだが,実感としてはもっと精度は高い。しかし確かに100%ではなく,私の方が(仮定法を使わずに)一歩先まで行ったこともあった。

| | Comments (0) | TrackBack (0)

Dec 25, 2006

「どちらかに必ず」入る数字――数独のはなし (4)

 中断していた数独のはなしだが,文庫サイズの数独の本を1冊終えた(→参照)あと,1か月ほど休んで,こんどは新書版の本を買い,前ほどの密度ではないが,主に帰りの電車の中で取り組んでいる。
 書店で見比べて,マス目の大きめの本を選んだ。それは,私の場合,答えの数字を入れる前に,いろいろ書き込むからである。

 答えのわかる手前のもっとも有力な情報は,3×3のブロックの中で,2つのマスのどちらかに,ある数字が必ず入るという情報である。例えばブロック内のA・Bという2つのマスのどちらかに3が必ず入るとわかったら,AとBの左上隅に小さく3と書いておく。A・Bがある列に並んでいるときは,その列には3はもう入らないから,他の場所の検討をする上で重要な手がかりとなる。
 進行していって,Aのマスに3以外の数字が入ったら,3の行き場所はあとはBのマスしかないから,直ちにBが3と確定する。ここでさらに,BまたはCに4,CまたはDに5が必ず入るとわかっている場合は,Bが3と確定すれば4の入る場所はCしかないし,Cが決まれば5の行き先はDしかないので,BCDが連鎖反応で確定する。
 また,A・Bのどちらかに必ず3と4が入るとわかったら,A・Bは3と4で「予約済み」となり,そこはもう埋まったとみなして進んでいくことができる。

 「どちらかに必ず」以外の「入る可能性がある」数字は,必要に応じて,右下隅になるべく小さく書いておくことにしている。

| | Comments (0) | TrackBack (0)

Oct 04, 2006

直説法と仮定法――数独のはなし (3)

 以下,数独のベテランの方には無用なことだが,解法の諸相を心覚えとして記しておく。

 数独の解法は,要するにルールを適用していくことである。
 したがって,解き方の第1は,ルールの適用によって「必然的にここにこれが入る」というマスを埋めていくことである。先述の文庫本のレベル分けでいうと「上級編」までは大部分がこれだけで解ける。

 ところが,その上のレベルになると,必然性のみではあるところから進まないというものが多くなる。この場合は,第2の方法として,「数字をひとつ仮定して先へ進む」ということをする。進んでみて矛盾(つまり行・列・ブロック内ですでに入っているのと同じ数字を入れる羽目になる)が生じたら,仮定したところに戻って別の仮定をしてやり直す。いわば背理法ギャンブルである。
 私の場合は,第1の方法で行き詰まったら(この判断がけっこう難しいこともあるが),鉛筆で入れた数字をペンでなぞって,それまでの成果が消えないようにしてから第2の方法に進む。これによって,仮定が誤っていたときには,鉛筆の数字を消せば仮定の時点に戻れる。

 数独をやるようになって,机以外にカバン3種の中と寝床に鉛筆が必要になり,シャープペンを何本か買った。

| | Comments (0) | TrackBack (0)

Oct 01, 2006

54億と17個――数独のはなし (2)

 数独の文庫本と格闘していた時期に,たまたま手にした『日経サイエンス』9月号にJ.-P.デラヘイ「数独の科学」という記事が載っていた(フランス人だろうと思うのになぜ「ヘ」と書いているのかは不明)。

 それによると,通常の9×9の数独の「解答」(すべてのマスが埋まった状態)の種類は,いろいろな置き換え・変形を除くと54億あまりだという。意外と少ないという感じもするが,ある1つの解答に至る「問題」(スタート状態)は非常にたくさんあるから,「問題の枯渇」の心配はないようだ。

 また,スタート状態で最小何個の数字が入っていれば解が1つに定まるか,という点については,「17個」と予想されているという。初期個数17個の問題の見本が出ているが,なにしろ全体が81個だから,17個というと本当にがらがらで,これで解けるのかと心配になってしまう。
 一般に,初期個数が少ない方が難しい。私が取り組んだ先述の本の初級編・中級編では初期個数30個代半ばから後半が多く,上級編以降は30個未満のことが多かった。ただし,解いてみると,初期個数が少なくてもそれほど難しくないものもあり,その関係が単純でないところがまたおもしろい。

| | Comments (0) | TrackBack (0)

Sep 29, 2006

3か月持ち歩いた文庫本

 6月下旬から3か月かかって,1冊の文庫本が終わった。本の端(小口)は手あかで汚れ,書店でかけてもらったカバーはすり切れそうになり,ページの間には消しゴムのかすが挟まっている。

 それは数独(別名ナンバープレース)――9×9のマス目の各行・各列,およびそれを区切った3×3の9ブロックすべてにおいて,1~9の数字を重複しないように入れるパズル――の本である。数字を扱っているが,計算をするわけではなく,並べるだけである。(だから本当は数字である必然性はなく,A~Iでも,い~りでも,9種の記号であればよい。)
 「読み終えた」のではなく「やり終えた」その本の構成は,

超初級編  10問      初級編   20問
中級編   30問      上級編   40問
プロ級編  30問      超プロ級編 10問

となっていて,中級編までは一部省略したが,上級編以降は全部解いた。

 かなりの期間を要したのは,主に電車の中で取り組んだからだった。通勤時間が(東京にしては)比較的短いので,時間が小間切れになり,効率が悪かった。ただし,数字をひとつ仮定した上で先に進むというテクニック(上記の区分でいうとプロ級編以降で必要になる)を使う場合,消しゴムでたくさん消してやり直したりすることになるので,電車の中ではやりにくく,終盤は家や会社の机の上でもやることになった。

 数独の本は山のようにあるので,次はどんな本にしようかと思案中。他の読書もしたいので,少し休んでからということになるだろう。

| | Comments (0) | TrackBack (0)