世界一難しい数独その４

前回に引き続き、世界一難しい数独を解いてみます。

ステップ６
ステップ５－１の仮定が間違っていることがわかりましたので、５－１の仮定のもう片一方が正解です。
確定させ、解けるところまで解きます。


ステップ６－１
新たに一つ仮定して、解いていきます。
正解・不正解まで到達しませんでした。


ステップ６－１－１
新たにもう一つ仮定して、解いていきます。
正解・不正解まで到達しませんでした。


ステップ６－１－１－１
新たにもう一つ仮定して、解いていきます。
不正解に到達しました。


ステップ６－１－１－２
一つ前のステップで不正解に到達したので、もう片一方で解いていきます。
不正解に到達しました。


ステップ６－１－２
ステップ６－１－１の仮定が間違っていることがわかりましたので、もう片一方で解いていきます。
正解・不正解まで到達しませんでした。


ステップ６－１－２－１
新たにもう一つ仮定して、解いていきます。
正解・不正解まで到達しませんでした。


ステップ６－１－２－１－１
新たにもう一つ仮定して、解いていきます。
・・・？全て埋まりました。そして矛盾もないようです。


というわけで、これが正解です。


数独をそれほどやっていない私ですが、順序だててやっていけば解くことができました。
ステップ数を減らす工夫としては、
・もうちょっと先読みして候補をいっぱい削る
・候補が２つのマスのなかでも、どれを仮定すれば正解・不正解まで確実に到達できるかよく選ぶ
といったところでしょうか。

タグ：数独

世界一難しい数独その３

今日は、前回の続きでステップ４－１－２－２からです。

ステップ４－１－２－２
ステップ４－１－２－１が間違っていたので、もう片一方で解いてみます。
正解・不正解まで到達しませんでした。


ステップ４－１－２－２－１
さらにもうひとつ仮定して、解いてみます。
不正解に到達しました。


ステップ４－１－２－２－２
前のステップで不正解に到達したので、ステップ４－１の仮定後はいずれのパターンにおいても正解に到達できないことが判明しました。


ステップ５
ステップ４－１の仮定が間違っていることが判明したので、その反対が正解となります。
これをもとに、続きを考えます。・・・仮にこれまでのどこかで間違って正解を見逃していると大変なことになりますが、間違ってはいないことを前提に次へいきます。


ステップ５－１
また新たにひとつ仮定して、正解・不正解に到達するまで解いてみます。
正解・不正解まで到達しませんでした。


ステップ５－１－１
また新たにひとつ仮定して、正解・不正解に到達するまで解いてみます。
不正解に到達しました。


ステップ５－１－２
一つ前の仮定が間違っていたので、もう片方で解いていきます。
正解・不正解まで到達しませんでした。


ステップ５－１－２－１
また新たにひとつ仮定して解いていきます。
不正解まで到達しました。


ステップ５－１－２－２
一つ前の仮定がまちがっていることがわかりましたので、もう片方で解いてみます。
正解・不正解まで到達しませんでした。


ステップ５－１－２－２－１
さらにもうひとつ仮定して解いてみました。そして不正解に到達しました。


ステップ５－１－２－２－２
一つ前のステップで不正解に到達したので、一つ前の仮定をもう片方で解いてみます。
正解・不正解まで到達しませんでした。


ステップ５－１－２－２－２－１
さらにもう一つ仮定し、解いていきます。
不正解に到達しました。


ステップ５－１－２－２－２－２
一つ前のステップの仮定が間違っていたので、もう片一方で解いてみます。
こちらも不正解に到達しました。


以上より、ステップ５－１の仮定が間違っていることが判明しました。
続きは次回・・・

正解を見る

タグ：数独

世界一難しい数独その２

次回の続きで世界一難しい数独を解いてみます。

ステップ４－１
ここからは仮定に仮定を重ねて解答を探していきます。
基本的に２つまで候補を絞れているところを、一方だと仮定して解いていき、正解か不正解かわかるところまでやっていきます。
そして正解なら終わりだし、不正解なら仮定が間違っていたことになるので２つの候補のもう片一方で確定させます。
まず、ステップ４でわかった６か７の入るマスの片一方を７とします（図中の橙色のマス）。ここを選ぶと２つ同時に確定できるので効率的だと思うからです。確定していない仮定の数字は緑色で埋めていきます。
そして、候補を絞ったり確定（あくまで仮定上の）できるものを埋めていきます。


ステップ４－１－１
ステップ４－１では正解・不正解まで到達できませんでしたので、また新たに仮定して（図中右側の橙色のマスの１）解いていきます。
今度は最後まで解けました。しかし、最後に候補が１つもないマスなどができてしまいました。これは不正解です。


ステップ４－１－２
ステップ４－１－１の仮定は間違っていたので、もう片一方で試します。


ステップ４－１－２－１
正解・不正解まで到達しなかったのでさらにもうひとつ仮定します。


ステップ４－１－２－１－１
不正解まで到達したのでこの仮定は間違っています。


ステップ４－１－２－１－２
ステップ４－１－２－１－１の仮定は間違っていたので、最後にした仮定をもう片一方で試します。


ステップ４－１－２－１－２－１
正解・不正解まで到達しなかったので、もうひとつ仮定します。
そして不正解に到達しました。


ステップ４－１－２－１－２－２
不正解だったので、最後の仮定をもう片一方で試します。
正解・不正解まで到達しませんでした。


ステップ４－１－２－１－２－２－１
さらにもうひとつ仮定し、不正解まで到達しました。


ステップ４－１－２－１－２－２－２
不正解だったので、最後の仮定をもう片一方で試します。
それでもまた不正解へ到達しました。
これにより、ステップ４－１－２－１の仮定は間違っていることがわかりました。


長い・・・次回へ続きます。

正解を見る

タグ：数独

世界一難しい数独その１

さっそく解いてみました。
問題は

です。

数独のルールをおさらいしましょう。
①１マスに１～９の数字を１つだけ入れる。
②縦列のいずれにも数字の重複がない。
③横行のいずれにも数字の重複がない。
④３×３（図中の白と灰色で色分け）の中で数字の重複がない。
の４つです。

正解はこの記事の一番下のリンクに載せておきます。
今回は画像の作成用にExcelを使用しましたが、関数やマクロやVBAなどの計算ツールとしては一切使っていません。
解く作業自体はおよそ１０時間ほどを必要としました。もちろん正解は見ずに解きました（見て解いたらせっかくの面白さ半減です）。
記事には数週間かかるとなっていましたが…？私のやり方があてずっぽうチックな部分があるためかもしれません。
運よくやや想定より早めに正解に達してしまった感はあります。順を追って書いていきます。

ステップ１
用紙を作って準備します。全ての空白に１～９の候補を記入します。


ステップ２
すでに確定している数字を元に、縦列・横行・３×３マスの候補から重複を排除します。


ステップ３
縦列・横行・３×３マスの中で、候補の数字がひとつしか出てこないものを探します。
図中の赤文字が該当しました。以降は確定したものを赤文字で表現することにします。


ステップ４
ステップ３で確定したものをもとに、縦列・横行の重複を排除します。
…ここで１５分くらい睨めっこ。左側の灰色の３×３マスのなかで、６と７のどちらかしか入らない場所を発見したので、この２マスの６と７以外の候補を排除しました。そしてこれ以上は考えてても進まないかな？という感じになる。大概の人はここでやめるかな？


続きは次回に。

正解を見る

タグ：数独

数独

今日、Yahoo!のトピックスで、世界一難しい数独なるものが載っていました。
なんでもフィンランドの先生が考えたとか。

数独といえば思い出すのが、平成20年4月の情報処理技術者試験です。
あの時私はソフトウェア開発技術者（現在の応用情報技術者）試験を受験していました。
そして午後Ⅱだったと思いますが、アルゴリズムの問題で数独を解くプログラムの穴埋め問題がありました。
あれがあれば、この問題も簡単に解けるかな？とも考えてみる…
でもちょっと自力で数独を考えてみましたが、あの時のプログラムではすぐ総当りのごり押しになりそうです。
それではあんまりにも芸がないので、自力でしばらく取り組んでみようと思います（宅建は？）

ちなみに問題は…
http://gamez.itmedia.co.jp/games/articles/1008/23/news093.html
に掲載されています。試験の息抜き（？）に挑戦されてはいかがでしょうか。

タグ：情報処理技術者 数独