プリズム

数理的アプローチ


Number Place(数プレ)について

投稿日時:

最終更新日時:

カテゴリー:

Number Place(数プレ)について、興味を持ち、ある書物を参考に NumberPlaceFX(下図参照)という、JavaFXアプリケーションを作成したので、それを利用して快適に遊ぶために必要な事柄の現時点でのまとめを行う。

NumberPlaceFXMain
図 NumberPlaceFX

この NumberPlaceFX を利用したい方はこちらを参照して下さい。

ここで述べる Number Place とは、9行9列に並べられた91個のセル(と呼んでおく)に、次のルールが成り立つように、1から9までの数字を入れることである。ただし、あらかじめ、複数のセルに数字が入っており、それらは変更できない。

ルール

各行、各列、各MiniGridにおいて、各数字が丁度1回ずつ出現する。

ただし、ここでの、行、列、MiniGridとその番号付けは下図の通りである。また、例えば、1行5列にあるセルを(1,5)で参照する(先に行番号、後で列番号を示す)。

RowsAndColumns
図 行、列とそれらの番号付け方法
MiniGrids
図 MiniGridとその番号付け方法

問題(パズル)が与えられたとして、まず、行うことは、入る数字が一意に決まるセルを探し、そのセルにその数字を入れる。これを繰り返して解ければ良いが、そうでない場合は、補助として、紙と鉛筆が必要になる。パソコン世代の私は、紙と鉛筆ではなく、パソコンを補助として利用したくなった。その補助機能、(参考にした書物には載っていない)Memo を実装したので、それを利用する際に必要となる事柄を、具体例を利用して、説明する。
具体例として、Easy Level で生成した問題 easyExample と Difficult Levelで生成した問題 difficultExample を利用する。

easyExample

easyExample
図 easyExample

赤色と黄色の円と(6,7)セルに色を付けたのは、説明で利用するためである。ある数字、ここでは1に着目する。1がある行を探すと、黄色の丸が付いた1行と7行、赤色の丸が付いた4行と5行がある。4行、5行、6行を含むMiniGrid中で、まだ1がない(6行を含む)MiniGrid6が存在する。従って、「ルール」により(6,7)セルに1が入ることが分かる。

easyExample1
図 1 at (6,7)

赤色の丸の付いた数字7とMiniGrid6に着目すると、(5,9)セルに7が入ることが分かる。

EasyExample2
図 7 at (5,9)

このようなことを続けていくと、(5,4)セルに8が入る。MiniGrid6と6行に着目すると、9個のセルのうち(8以外の)8個が入力されているので、最後のセルは、共に8となる。

EasyExample3
図 8 at (5,4)
EasyExample5
図 8 at (4,7) and (6,3)

同様に進めて、例えば、(2,1)セルに5、(3,6)セルに5、(8,4)セルに5、(5,1)セルに6、(7,4)セルに7が入る。

EasyExample10
図 5 at (2,1) … 7 at (7,4)

ここで、Memo 機能を利用する。「Show Memo」トグルボタンを押し下げると、Memoウィンドウが表示される。Memoウィンドウのタイトルにあるように、ここにはYour Possibles、すなわち、各セルに入る可能性がある数字を列挙したもの(これをこのセルのPossibleと呼ぶことにする)を自分で記入する。例えば、行、列、MiniGridを見渡して、空白のセルの個数がなるべく少ないものを探し、それらのPossibleから入力した方が容易である。Mainウィンドウを見ると5行は2個なので、(5,5)と(5,6)セルのPossibleを入力する。まず、(5,5)セルの方、5行には1235678が入力されており、5列には2578、MiniGrid5には1235678が入力されているので、これらを1から9の9個の数字から除くと49となる(この操作をSimple Eliminationと呼ぶことにする)。従って、(5,5)セルのPossibleは、49となる。同様に、(5,6)セルのPossibleも49となる。各セルのPossibleをこのSimple Eliminationを利用して正確に求めるのは大変なので、Simple Eliminationにはない数字を入力しても受け付けないようにしておいた。従って、考えるのは面倒だが、労力は惜しまない場合は、多めに、1から9まで入力すればよい。少し労力を惜しむ場合は、例えば、5行、または、5列、または、MiniGrid5にある数字以外の49、13469、49、で個数が少ない、49を入力すればよい。)

EasyMemo00
図 Memoウィンドウ、(5,5),(5,6)セルに49を(8,1),(9,1)セルに24を入力しようとしたところ

(8,1)セルと(9,1)セルのPossibleは、各々、24と2になる。Possibleが1個の数字からなる場合(このセルをSingle Possibleと呼ぶことにする)、このセルに入るのはこの数字となる。すなわち、この時点で(9,1)セルには2が入る。

EasyExample11
図 2 at (9,1)

Mainウィンドウで(9,1)セルをクリックし2を入れると、MemoウィンドウでのPossiblesがそれに応じて自動的に修正される。すなわち、(9,1)セルのPossibleが空白に、(8,1)セルのPossibleが4に、修正される。

EasyMemo01
図 Possibleは自動的に修正される

(8,1)セルもSingle Possibleになったので、Mainウィンドウに戻り(8,1)セルに4を入れる。

EasyExample12
図 4 at (8,1)

同様に続ければ、(この問題は簡単なので)解ける。

EasyExample26
図 easyExampleの答え

以上をまとめる。Memoウィンドウで、各セルのPossibleを入力する。その際、

方法0(Single Possible)

Single Possibleなセルが見つかれば、そのSingle PossibleなセルのPossibleの値が対応するセルに入る。

difficultExample

difficultExampleは下図のような問題である。

DifficultExample0
図 difficultExample

このdifficultExampleを利用して、残りの方法を説明する。上述のeasyExampleでは、各セルのPossibleを自分で入力した。ここでは「Synchronize」ボタンを押し、その時点でNumberPlaceFXが内部で保持している全てのセルのPossiblesの値を自動的に入力させる。(現時点で、NumberPlaceFXが内部で保持しているPossiblesは、その初期値として、Simple Eliminationを適用して得たものである。)

DifficultMemo0
図 Memoウィンドウ、MainウィンドウでのPossiblesと同期された。

「Find:」の右にある「2」トグルボタンを押し下げる。Possibleに2を含むセルにマゼンタ色の印が付く。

DifficultMemoOne1
図 Possibleに2を含むセルにマゼンタ色の印が付いた

3行に着目する。(3,1)セルにのみ2が存在するのが分かる((3,1)セルがOne Confirmedである、ということにする)。「ルール」より、3行のどこか1か所に2が入るので、(3,1)セルに2が入る。

DifficultExample1
図 2 at (3,1)

同様なことが、列とMiniGridにおいても成立する。まとめると、

方法1(One Confirmed)

  1. (R):ある行において、ある数字をPossibleに含むセルがただ1個しか存在しない場合、その数字が対応するセルに入る。
  2. (C):ある列において、ある数字をPossibleに含むセルがただ1個しか存在しない場合、その数字が対応するセルに入る。
  3. (MG):ある列において、ある数字をPossibleに含むセルがただ1個しか存在しない場合、その数字が対応するセルに入る。

ヒント:「Find:」の右にある数字を押し下げると、One Confirmedなセルの有無が容易に分かる。

以降は、セルに入る数字が必ずしも確定するとは限らないが、Possibleの範囲を狭めるのに役立つ。

MiniGrid6に着目する。(6,7)、(6,8)、(6,9)セルのPossibleは2個または3個の数字を含み、これら3個のセルのPossibleをまとめると、368となり、丁度3個であるので、この3個のセルには、どのセルにどれが入るかは現時点で不明であるが、368が入る。従って、MiniGrid6内の他のセルのPossibleに、368があればそれらを取り除くことができる(4個のセルのPossibleを変更する)。この時、(6,7)、(6,8)、(6,9)の3個のセルがThree Confirmedである、ということにする。

DifficultMemoThreeInMG62
図 Three Confirmed、368 at (6,7),(6,8),(6,9)

同様なことが、行と列においても成立する。まとめると、

方法3(Three Confirmed)

  1. (R):ある行において、3個のセルが存在しそれらのPossibleが2個または3個の数字を含み、それらをまとめたものが丁度3個の場合、この行の他のセルのPossibleからこの3個の数字を取り除くことができる。
  2. (C):ある列において、3個のセルが存在しそれらのPossibleが2個または3個の数字を含み、それらをまとめたものが丁度3個の場合、この列の他のセルのPossibleからこの3個の数字を取り除くことができる。
  3. (MG):あるMiniGridにおいて、3個のセルが存在しそれらのPossibleが2個または3個の数字を含み、それらをまとめたものが丁度3個の場合、このMiniGridの他のセルのPossibleからこの3個の数字を取り除くことができる。

MiniGrid6に着目する。(4,8)、(5,9)セルの2個のPossibleは、共に、丁度2個の数字17である。この2個のセルには、どちらのセルにどれが入るかは現時点で不明であるが、17が入る。従って、MiniGrid6内の他のセルのPossibleに、17があればそれらを取り除くことができる(2個のセルのPossibleを変更する)。この時、(4,8)、(5,9)の2個のセルがTwo Confirmedである、ということにする。

DifficultMemoTwoInMG63
図 Two Confirmed、17 at (4,8),(5,9)

同様なことが、行と列においても成立する。まとめると、

方法2(Two Confirmed)

  1. (R):ある行において、2個のセルが存在しそれらのPossibleが共に同じ2個の数字の場合、この行の他のセルのPossibleからこの2個の数字を取り除くことができる。
  2. (C):ある列において、2個のセルが存在しそれらのPossibleが共に同じ2個の数字の場合、この列の他のセルのPossibleからこの2個の数字を取り除くことができる。
  3. (MG):あるMiniGridにおいて、2個のセルが存在しそれらのPossibleが共に同じ2個の数字の場合、このMiniGridの他のセルのPossibleからこの2個の数字を取り除くことができる。
DifficultMemoTwoInMG64
図 Single Possible、2 at (5,8)

今までと異なり、今回は、(5,8)セルがSingle Possibleになったので、(5,8)セルに2を入れる。

DifficultExample2
図 2 at (5,8)

以上で、方法0から3までの説明を行った。最後の方法4(Among 3 MiniGrids)を説明するために、それに至るまでの経過も含め、Memoウィンドウのみで説明する。必要に応じて(Single Possible、One Confirmedの場合)、Mainウィンドウに戻って対応するセルにその時点で確定した数字を入れる必要がある。

DifficultMemoSingle5


図 Single Possible、9 at (5,7)

先に、方法4(Among 3 MiniGrids)を列挙しておく。

方法4(Among 3 MiniGrids)

  1. (R-R):行方向に横に並んだ3個のMiniGridにおいて;その中の1個のMiniGridにおいて、ある数字がある行にだけ存在する場合、他のMiniGrid内でその数字をその行から取り除くことができる。
  2. (R-MG):行方向に横に並んだ3個のMiniGridにおいて;ある行において、ある数字がその中の1個のMiniGrid以外に存在しなければ、その数字をそのMiniGridの他の行から取り除くことができる。
  3. (C-C):列方向に縦に並んだ3個のMiniGridにおいて;その中の1個のMiniGridにおいて、ある数字がある列にだけ存在する場合、他のMiniGrid内でその数字をその列から取り除くことができる。
  4. (C-MG):列方向に縦に並んだ3個のMiniGridにおいて;ある列において、ある数字がその中の1個のMiniGrid以外に存在しなければ、その数字をそのMiniGridの他の列から取り除くことができる。
DifficultMemoAmong3MGsRow66
図 1.(R-R):MiniGrid6に着目し。6行にAmong 3 MiniGridsを適用

MiniGrid4、MiniGrid5、MiniGrid6の3個のMiniGridに着目する。「Find:」の右にある「3」トグルボタンを押し下げる。3が入っているセルが分かり易くなる。MiniGrid6において、6行だけに3が含まれ、他の4行、5行には含まれていない。ルールより、3がMiniGrid6の6行に入ることになるので、MiniGrid4(とMiniGrid5)の6行には3が入ることはない。すなわち、MiniGrid4(とMiniGrid5)の6行に3があれば、取り除くことができる。この時、1.(R-R):MiniGrid6に着目し6行にAmong 3 MiniGridsを適用する、ということにする。

DifficultMemoAmongMGsRow67
図 現時点でのYour Possibles

他の数字で、あるMiniGridに着目し、ある行にAmong 3 MiniGridsを適用してみる。

DifficultMemoAmong3MGsRow68
図 1.(R-R):MiniGrid6に着目し、6行にAmong 3 MiniGridsを適用

数字8に対して、MiniGrid6に着目し、6行にAmong 3 MiniGridsを適用すると、

DifficultMemoAmong3MGsRow69
図 現時点でのYour Possibles

次は、行方向に並んだ3個のMiniGridに適用できる変化形を説明する。

DifficultMemoAmong3MG4Row610
図 2.(R-MG):6行に着目し、MiniGrid4にAmong 3 MiniGridsを適用

6行に着目する。MiniGrid4、MiniGrid5、MiniGrid6の3個のMiniGridにおいて、数字4が存在するのはMiniGrid4だけであり、それ以外のMiniGrid5とMiniGrid6には数字4は存在しない。ルールより、6行に1個だけ4が入るので、それはMiniGrid4に入ることになる。すなわち、MiniGrid4において、(4は1個しか入らないので)6行以外の5行(と4行)に4があれば、取り除くことができる。この時、2.(R-MG):6行に着目し、MiniGrid4にAmong 3 MiniGridsを適用する、ということにする。

しかし、下図が示すように、これは1(R-R):MiniGrid5に着目し、5行にAmong 3 MiniGridsを適用する、とみなすことも可能である。

DifficultMemoAmong3MG4Row610
図 1.(R-R):MiniGrid5に着目し、5行にAmong 3 MiniGridsを適用
DifficultMemoAmong3MG4Row611
図 現時点でのYour Possibles

以下、2(R-MG):ある行に着目し、あるMiniGridにAmong 3 MiniGridsを適用する、が実際必要であることを示す具体例を提示する。かなり手間がかかるので、不要な方はここへ進んで下さい。図のみを列挙する。

DifficultMemoOneIn2412
図 (2,4)セルがOne Confirmed、4 at (2,4)
DifficultMemoOneIn9413
図 (9,4)セルがOne Confirmed、2 at (9,4)
DifficultMemoOne9614
図 (9,6)セルがOne Confirmed、8 at (9,6)
図 MiniGrid2に着目し、3行にAmong 3 MiniGridsを適用、または、2行に着目し、MiniGrid1にAmong 3 MiniGridsを適用、
  MiniGrid8に着目し、8行にAmong3MiniGridsを適用、または、9行に着目し、MiniGrid7にAmong 3 MiniGridsを適用
図 (2,3)セルがOne Confirmed、9 at (2,3)
図 2.(R-MG):2行に着目し、MiniGrid3にAmong 3 MiniGridsを適用
図 現時点でのYour Possibles

1.(R-R)を適用して、この結果を得ることはできない。すなわち、2.(R-MG)は1.(R-R)と独立した事項である。以上は、行方向に並んだ3個のMiniGridに関するものであったが、列方向に並んだ3個のMiniGridに対しても同様のことが成り立つ(既に、列挙した3.(C-C)と4.(C-MG)である)。

ここから、同様な方法を適用していくと、次のように解が見つかる。

図 difficultExampleの答え

以上で、difficultExampleを利用した、方法0から方法4の説明を終える。difficultExampleを解く際、必ずしも、この説明のように解く必要はない。実際、「Solve Puzzle」を押し、自動的に解くと、Single PossibleとOne Confirmedだけを利用して解ける。

入力ミス、操作ミス、に関して

Memoウィンドウを利用し自分でYour Possiblesを操作して解く場合の(あり得る)大きなミスは、MemoのあるセルにPossibleを入力するために、キーボードからある数字を入力した時、キーボードフォーカスがMainウィンドウのあるセルにあったため、その数字がそのセルに入力されることである。この結果、入力(修正)しようとしていたセルのPossibleが空白になるだけでなく、そのセルと同じ行、列、MiniGridにあるセルのPossibleも修正される可能性があり、元に戻すのが大変である。このミスを対処するために、次の2つを行った。

  1. Mainウィンドウのあるセルにキーボードフォーカスがある場合、対応するMemoウィンドウのセルの背景は赤色になる。Memoウィンドウのセルにキーボードフォーカスがある場合、背景はシアン色である。従って、MemoウィンドウでPossibleを入力する際は、Memoウィンドウのそのセルの背景色が赤色ではなくシアン色であることを確認すること。ただし、この時、(あるセルのPossibleを自分で入力する時に、Mainウィンドウでそのセルの位置が確認できる方が楽だから)Mainウィンドウの対応するセルの背景色はシアン色になっている。
    一方、MemoウィンドウのPossibleを参照しながら、Mainウィンドウのセルに数字を入れる場合、Memoウィンドウの参照するセルの背景色が赤色であることを確認して(この状態でMainウィンドウの対応するセルにキーボードフォーカスがあるので)、キーボードからその数字を入力すること。
  2. それでも、Memoウィンドウのあるセルに入力すべきある数字を、間違って、Mainウィンドウの対応するセルに入力してしまった場合、1回だけ元に戻すことができる。まず、Mainウィンドウの「Undo」ボタンを押す。次に、Memoウィンドウの「Set Last」ボタンを押す。

Memoウィンドウの他の利用方法

以上は、自分でPossibleを修正しながらパズルを解く時に、Memoウィンドウを利用した。他には、NumberPlaceFXが自動でどのようにPossiblesを修正し解いているかを(事後に)確認するために利用できる。

Memoウィンドウの「Synchronize」ボタンを押す(その時点でNumberPlaceFXが内部で保持している全てのセルのPossiblesの値を自動的に入力させる)。「Show Last」チェックボックスをチェックする。Mainウィンドウにおいて、「Step by step」チェックボックスをチェックする。以上の設定の下で、「Solve Puzzle」を押す。押す毎に、Mainウィンドウではセルに入力されていき、Memoウィンドウでは、その際、NumberPlaceFXがどのようにPossibleを修正したかが表示される。赤色が直前の値である。「Step by step」がチェックされた時の1ステップは、必ずしも、1個のセルに数字が入る、を意味するわけではない。

下図は上記で説明に利用したeasyExampleの例である。「Solve Puzzle」ボタンを1回押した時点である。(3,2)セルに4が入る。

図 4 at (3,2)

Memoウィンドウでは、(3,2)セルのPossibleが削除され、3行、2列、MiniGrid1内のセルで4を含むPossibleがあれば、4が削除された。

図 関連するPossibleが赤字から修正された