解法アルゴリズム
□ 用語とデータ表現
<<用語> ・マス ：９ｘ９に区切られた８１個の領域のひとつひとつ
・行 ：横１行
・列 ：縦１列
・ブロック：３ｘ３に区切らてた小さな仕切り
・タップル：行、列、ブロックを総称して扱うときの呼称
・ヒント ：問題の初期値として与えられた数字とその位置
各々のマスには、そのマスに可能性のある数字のリスト（候補リスト）を保持する。
マスの数字が確定するにしたがって、候補リスト内の数字は絞られていく。
・内部形式
１ー９の数字をビット位置で表す。候補リストはこれらのビット位置
ＯＲで表現する。
”１”．．．０ｘ０１ ”２”．．．０ｘ０２
”３”．．．０ｘ０４ ”４”．．．０ｘ０８
”５”．．．０ｘ１０ ”６”．．．０ｘ２０
”７”．．．０ｘ４０ ”８”．．．０ｘ８０
”９”．．．０ｘ１００
｛１，３，９｝という候補リストは、０ｘ１０５となる。
・アドレス表現
ｉ行、ｊ列のマスを（ｉ，ｊ）であらわす。
・確定処理
あるマス（ｉ，ｊ）の数字が確定した場合、関連するマスの候補リストから確定
した数字を消去し、マス（ｉ，ｊ）の確定処理済表示（最上位ビット）をオンに
する処理をいう。
関連するマスとは、ｉ行に含まれるマス、ｊ列に含まれるマス、（ｉ，ｊ）を含
むブロックのマスである。
・（あるマスの）ビット数
候補リストの要素の数は、内部表現のビット数に等しい。例えば上記の候補リス
トの内部表現０ｘ１０５のビット数は３である。特に、
ビット数＝０のマスは候補リストが空集合を意味しており、ナンプレ問題と
しては不適切と判断できる
ビット数＝１のマスは候補リストの要素が１つしかないので、マスの数字が
確定したことを意味する
□ Ａ１：通常のアルゴリズム（探索をベースとした）
探索をベースとした試行錯誤のアルゴリズムであるため、どんな問題でも解くこと
ができる。問題を解くだけの目的であれば、このアルゴリズムで十分と思われる。
（０）初期値の設定
各マスの０ｘ１ｆｆを設定する（１−９のすべての数字を候補リストに）
ヒントで指定されたマスに該当のビットを設定する
以下の（１）−（３）は再帰呼び出しの処理となっている。
（１）全マスをスキャンして最小のビット数（ｍ）とそのマスの位置をもとめる。
ただし、確定処理済のマスは対象外とする。
（２）上記の結果、すべてのマスが確定済の場合は、解がひとつ得られたので、
もし、既に解が得られていれば、重複解のエラーで終了する。
これが、最初の解であれば、この解を覚えておき、次の解を探す。
（エラー復帰する）
（３）上記の結果、最小のビット数（ｍ）に応じて以下の処理を行う。
ｍ＝０であれば、解なしのエラーでリターンする。
ｍ＝１であれば、そのマスを確定処理を行い、次のマスを決定するため、
再帰的に（１）をｃａｌｌする。
ｍ＞１の場合、 候補の数字は複数あるので、そのなかの数字をひとつ選
択して、確定処理を行い再帰的に（１）をｃａｌｌする。
再帰呼び出しが重複解エラーで復帰した場合は直ちに復帰
する。そうでない場合は、次の数字を選択して同様の処理
を繰り返す。
すべての数字の処理が終了した場合は復帰する。
□ Ａ２：確定的アルゴリズム（経験的アルゴリズム）
ナンプレ問題を解く技そのものです。技自身は、発見的アプローチであるため、網
羅性に不安がのこります。
Ａ２−１：Ｓｂｉｔサーチ
ビット数が１のマスがあれば、そのマスの確定処理を行う。
ビット数が０のマスがあれば、解なしであるので処理を終了する。
Ａ２−２：Ｕｂｉｔサーチ
ひとつのタップルに着目したとき、あるマスにしか現れないビットがあれば
そのマスをそのビットに確定する。下図の例ではGのビット位置がＵｂｉｔ
となっているので、マス１は０１０００００００（０ｘ８０）に確定する。
HGFEDCBA@ ＜−−ビット位置
マス１：０１１０００１１１
マス２：１０１１１１０１１
マス３：００１００１１１０
マス４：１００００１１０１
マス５：００１１１００１１
マス６：１０１０１０１００
マス７：００００１１１１１
マス８：０００１００１００
マス９：００００１１１１１
Ａ２−３：ＩｎｔｅｒＳｅｃｔｉｏｎ
交差する２つのタップル（ｅｘ．行とブロック）の関係に着目する。
＋−−−−−＋−−−−＋
｜ ａ ｜ ｃ ｜ タップル１の構成は、ａ，ｃ
＋−−−−−＋−−−−＋ タップル２の構成は、ｂ，ｃ
｜ ｂ ｜
｜ ｜
＋−−−−＋
あるビット位置（数字）の出現パターンとその対処
ａ ｃ ｂ
(1) １ １ １
(2) １ １ ０ −−＞ ａの部分の１を０にする
(3) １ ０ １
(4) ０ １ １ −−＞ ｂの部分の１を０にする
(5) １ ０ ０ −−＞ 解なし
(6) ０ １ ０
(7) ０ ０ １ −−＞ 解なし
(8) ０ ０ ０ −−＞ 解なし
Ａ２−３：Ｅ（ｎ） ｎ＝２−４
あるタップルｔ内のｎケのマスのＯＲをとったものをＥとし、Ｅのビット数を
ｍとする。
ｍ ＜ ｎ ：解なし（ｎケのますより候補のリストの要素がすくない）
ｍ ＝ ｎ ：これをＥｎｃｌｏｓｕｒｅ（ｎ）と定義する。
この場合、タップルｔ内の他のマスにあるＥのビットをすべて
０にしてよい。
ｍ ＞ ｎ ：Ｅｎｃｌｏｓｕｒｅ（ｎ）は成立していない。
例題
HGFEDCBA@ ＜−−ビット位置
マス１：０１１０００１１１
マス２：１０１１１１０１１
マス３：０００００１１１０
マス４：０００００１１００ マス３、４、７のＯＲをとると０ｘ０ｅと
マス５：００１１１００１１ なり、Enclosure(3)が成立している
マス６：１０１０１０１００
マス７：０００００１０１０
マス８：０００１００１００
マス９：０１００１１１１１
Enclosure(3)の処理でビットが０になる部分は
以下の＊の部分である。
マス１：０１１０００＊＊１
マス２：１０１１１＊０＊１
マス３：０００００１１１０
マス４：０００００１１００
マス５：００１１１００＊１
マス６：１０１０１０＊００
マス７：０００００１０１０
マス８：０００１００＊００
マス９：０１００１＊＊＊１
上記の結果、マス８ではＳｂｉｔが成立する
Ａ２−４：Ｘ（ｎ） ｎ＝２−４
あるタップルｔ内のｎケのビットに着目する。ｎケのビットのいずれかを持つ
マスの数をｍとする。
ｍ ＜ ｎ ：解なし（ｎケのビットをもつ候補のリストの要素がすくない）
ｍ ＝ ｎ ：これをＥｘｃｌｏｓｕｒｅ（ｎ）と定義する。
この場合、該当するマスの他のビットをすべて０にしてよい。
ｍ ＞ ｎ ：Ｅｘｃｌｏｓｕｒｅ（ｎ）は成立していない。
例題
HGFEDCBA@ ＜−−ビット位置
マス１：０１１０００１１１
マス２：１０１１１１０１１
マス３：０００００１１１０
マス４：０００００１１００ ビットH，G，Fに着目すると、マス１，
マス５：０００１１００１１ マス２，マス６のみが該当する
マス６：１０１０１０１００ ｎ＝３，ｍ＝３なので Exclosure（３）
マス７：０００００１０１０
マス８：０００１００１００
マス９：００００１１１１１
Exclosure(3)の処理でビットが０になる部分は
以下の＊の部分である。
マス１：０１１０００＊＊＊
マス２：１０１＊＊＊０＊＊
マス３：０００００１１１０
マス４：０００００１１００
マス５：０００１１００１１
マス６：１０１０＊０＊００
マス７：０００００１０１０
マス８：０００１００１００
マス９：００００１１１１１
上記の結果、マス３，４，７でEnclosure(3)が成立する
(補足）
EnclosureとExclosureの関係は縦と横が入れ替わったようなものです。
Ａ２−５：Ｎｅｇａｔｉｏｎ − 背理法
ある任意のマス（Ｐ）の候補リストをｍとする。ｍから１ビット（＝ａ）落と
した候補リストを~ａとする。
「マス（Ｐ）を~ａに置き換えて上記のアルゴリズムＡ２−１〜Ａ２−４を適用
したとき、解なしという結果がえられた」
とするとマス（Ｐ）は ａに決定してよい。（解があるとしたらａしかない）
例えば、ｍ＝０ｘ２９とすると
ａ＝０ｘ２０ −＞ ~ａ＝０ｘ０９
ａ＝０ｘ０８ −＞ ~ａ＝０ｘ２１
ａ＝０ｘ０１ −＞ ~ａ＝０ｘ２８
を順に解なしの結果がえられるまで調べていけばよい。
（補足−１）
上記のアルゴリズムの結果を整理すると
解なしという結論がえられない場合 ： 解が複数存在する
解なしという結論が複数ある場合 ： 解が存在しない
(補足−２）
マス（Ｐ）は任意に選ぶことができるので、なるべくｍのビット数が少ない
位置を選ぶのが効率がよい。
Ａ２−６：試行錯誤 (最後の砦）
上記のいずれでも解がえられない場合、試行錯誤的に解をさがす方法がある。
Ａ２−５とＡ２−６の相違は、Ａ２−５は再帰的ではない点にある。一方、
Ａ２−６の本質は、再帰的に探す部分にある。
□ Ｒａｎｋ − 難易度
Ａ２−１は一番簡単であり、Ａ２−５，６はかなり複雑で難しい。
この確定的アルゴリズムの難しさを使って、ナンプレ問題の難易度を測ることがで
きる。
Ｒａｎｋ 表示 説明 解法に必要なアルゴリズム
（１） ＊ 大変やさしい Ａ２−１（Ｓｂｉｔ）のみ
（２） ＊＊ やさしい Ａ２−２（Ｕｂｉｔ）まで
（３） ＊＊＊ 普通 Ａ２−３ (InterSection）まで
（４） ＊＊＊＊ ちょっと難しい Ａ２−４（E(2),X(2)）まで
（５） ＊＊＊＊＊ 難しい Ａ２−４（E(3),X(3)）まで
（６） ＊＊＊＊＊＊ 難しい Ａ２−４（E(4),X(4)）まで
（７） ＊＊＊＊＊＊＊ 大変難しい Ａ２−５（Negation）まで
（８） ＊＊＊＊＊＊＊＊ 超難問 Ａ２−６（試行錯誤）まで
Ｒａｎｋ（８）が存在するかどうかが興味深いところであるが、現時点（99.08.12)
では見つかっていない。
□ 確定的アルゴリズム仮説
まず、Ａ２−１〜Ａ２−５を整理する。
ＥｎｃｌｏｓｕｒｅをＥ（１）−Ｅ（８）に拡張し、Ｓｂｉｔ，Ｕｂｉｔ，Ｘ（ｎ）
を包含する。
Ｓｂｉｔ ：Ｅ（１） これは自然な拡張
Ｕｂｉｔ ：Ｅ（ｔ−１） ｔはタップル内の要素の数
Ｘ（ｎ） ：Ｅ（ｔ−ｎ） ｔはタップル内の要素の数
Ｕｂｉｔ，Ｘ（ｎ）は、アルゴリズムの説明の例題をよく見て理解してください。
InterSectionは、Negationにふくまれる。これは、InterSectionで消すことのでき
るビットはNegationでも消すことができるので問題ないでしょう。
以上により、Ａ２−１〜Ａ２−５は、以下の２つの操作に集約できる。
・Ｅｎｃｌｏｓｕｒｅ
・Ｎｅｇａｔｉｏｎ
現時点では、Ａ２−６を必要とする問題は検出されていないので、以下の仮説を
提案する。
仮説
「すべてのナンプレ問題は、ＥｎｃｌｏｓｕｒｅとＮｅｇａｔｉｏｎの操作を
繰り返し適用することにより解くことができる」
この件に関して、反例・完備性の証明等の情報がありましたらお知らせください。