← StudyX Devlog

数独で仮定(当てずっぽう)を使ってもいいか

Hiroki ObaraHiroki Obara · DeveloperSudoku365使い方
数独で仮定(当てずっぽう)を使ってもいいか

メモを全部書いて、知っている手筋を一通り探しても、次のマスが決まらない。候補が2つだけのマスが目の前にあって、どちらかを入れてみれば先に進めそうに見える。ナンプレを続けていると、こういう場面に何度も出会います。

これまでの記事で、当てずっぽうで数字を入れても解いたことにならない、と書いてきました。ただ、「仮に入れてみる」には、実はいくつかの種類があります。この記事では、その違いと、理由をもって使える仮定の使い方を書きます。

当てずっぽう、試行錯誤、背理法

「仮に入れてみる」には、大きく三つの形があります。

当てずっぽう。 候補のどちらかを入れて、そのまま解き進めます。最後まで解ければ、それで終わりです。途中で行き詰まっても、どこで間違えたのか分からないまま消しゴムを使うことになります。

試行錯誤。 候補のどちらかを入れて解き進め、矛盾が出たら、入れたところまで戻ってもう一方を入れます。これを繰り返せば、いつかは答えに着きます。コンピューターがナンプレを解くときの基本的なやり方は、これです。英語版 Wikipedia の Sudoku solving algorithms では、空いたマスに数字を順に入れ、ルールに合わなくなったら前のマスに戻る「バックトラック」を、総当たりの一種として説明しています。

背理法。 「もしこのマスが4なら」と仮定して、そこから決まるマスをたどります。その先で矛盾が出たら、「このマスは4ではない」と結論して、メモから4を消します。仮定した数字は、盤には残しません。

三つめは、数学の証明で使う背理法と同じ形です。「4だとすると矛盾する。だから4ではない」という推論は、論理として正しいものです。当てずっぽうと違って、結論にはきちんとした理由があります。

背理法の形の仮定

背理法の形の仮定は、使ってよいという考え方もあります。理由は二つ挙げられます。

一つは、名前のついた手筋の中にも、「もしこうなら」と考えるものがあることです。たとえば XY-Wing は、「真ん中のマスが A なら、こちらが C になる。B なら、あちらが C になる。どちらにしても C はどちらかに入る」と、場合を分けて考える手筋です。これは、小さな仮定を二つ並べたものだと言えます。くわしくは ナンプレの上級テクニック に書きました。

もう一つは、上級者のあいだでも、どこからが仮定なのか、境目がはっきりしていないことです。英語の解説サイト SudokuWiki では、一つの候補を仮定して矛盾をたどる Nishio という手筋を、「半分は試行錯誤のようなやり方」と書きながら、決まった手順に沿った手筋として扱っています。

一方で、当てずっぽうと試行錯誤は、解くというより答え合わせに近い、という見方もあります。最後まで入れてみて合うかどうかを確かめる作業で、コンピューターなら一瞬で終わります。

背理法の使い方

背理法を使うときは、次の順番で進めます。

  1. 候補が2つだけのマスを選ぶ。 候補が多いマスで仮定すると、たどる先が広がりすぎます。
  2. 片方を仮定して、決まるマスだけをたどる。 「このマスは4」とすると、同じ行・列・ブロックのメモから4が消えます。その結果、候補が1つになったマスがあれば、それも決まります。こうして、一つずつ決まるマスだけをたどります。
  3. 矛盾を探す。 矛盾とは、同じ行・列・ブロックに同じ数字が2つ入ること、候補が一つもなくなるマスができること、ある数字の入る場所が行・列・ブロックのどこにもなくなることです。
  4. 矛盾が出たら、仮定した数字を消す。 「4ではない」と分かったので、元のマスのメモから4を消します。候補が2つだったので、もう片方の数字に決まります。
  5. 矛盾が出ないまま止まったら、何も分からなかったと考える。 仮定でたどったものは全部消して、元の盤に戻ります。

5がいちばん大事です。矛盾が出なかったことは、仮定が正しい証拠にはなりません。たどれる範囲では矛盾しなかった、というだけです。ここで仮定を残したまま先へ進むと、背理法のつもりが当てずっぽうになります。

小さな例

形だけを示します。あるブロックの中に、メモが次のようになっている3つのマスがあるとします。

  • マスA:4 か 7
  • マスB:4 か 9
  • マスC:4 か 9

マスAを4と仮定します。するとBとCは同じブロックなので、どちらも4ではなくなり、BもCも9になります。同じブロックに9が2つです。これは矛盾なので、Aは4ではありません。Aは7に決まります。

ところで、この例は、仮定を使わなくても解けます。BとCは、候補が「4と9」だけのマスが2つそろっています。4と9は、この2つのマスで使い切られるので、同じブロックのほかのマスからは4と9を消せます。初心者が最初に覚える手筋 に書いた「2つのマスの組」です。

ここに、仮定を使うときの学びがあります。仮定で見つけた矛盾は、たいてい、まだ見えていない手筋の言いかえです。矛盾が出たら、なぜ矛盾したのかを盤の上で見直してみます。そこに名前のある形が見つかれば、次からは仮定なしで同じことができます。

仮定を考える前に

背理法は手間がかかります。仮定を考える前に、確かめておくことが二つあります。

一つは、メモが正しいかです。消してはいけない候補を消していると、どんな手筋も、どんな仮定も、正しく働きません。メモの見直し方は ナンプレで行き詰まったときの見直し方 に書きました。

もう一つは、難易度です。ナンプレの難易度は何で決まるか に書いたとおり、Sudoku365 の「かんたん」は基本の手筋だけで、「むずかしい」も予約や2つ・3つのマスの組までの手筋で、どの問題も最後まで解けることを確かめてあります。この範囲で止まったなら、仮定よりも、見落としている手筋を探すほうが近道です。「エキスパート」では、名前のある手筋を全部使っても解き切れない問題が多く、そこで初めて、背理法のような読みが出番になります。

Sudoku365 で仮定を試すとき

Sudoku365 は、私が作っているナンプレのアプリです。iPhone、iPad、Android で遊べます。4つの難易度に300問ずつ、計1200問が入っていて、どの問題も答えは1つだけです。

アプリで仮定を試すときに知っておいてほしいことがあります。入れた数字は、すぐに答えと照らし合わされます。間違えた数字は赤く表示され、ミスとして数えられ、3回でゲームオーバーです。正しい数字は、そのまま確定します。つまり、仮定のつもりで数字を入れると、それは答え合わせになってしまいます。

ですから、アプリで仮定を試すなら、数字ではなくメモを使います。仮定でたどるマスのメモを書きかえていき、矛盾が出たら、元のマスのメモから仮定した数字を消します。たどった途中のメモは、「もどす」で1手ずつ元に戻せます。数字を置いたときに自動で消えたメモも、もどすで戻ります。ただし、ミスの数は戻りません。

ヒントは最初に10個あり、パズルをクリアすると1個、広告を見ると1個増えます。仮定でも決まらないときは、ヒントで1マスだけ埋めて、なぜそこがその数字なのかを考えることもできます。

アプリは無料で、広告が入ります。「広告を削除」の買い切り(1,500円)で広告を消せます。最初の一問の始め方は Sudoku365 の始め方 に書きました。

App Store でダウンロード Google Play で手に入れよう

Sudoku365毎日ナンプレ、2人でも