General Logic【暫定版】
General Logicは、数独の解法アルゴリズムのほとんどに共通する手法です。
General Logicは BaseSet/CoverSet の一般化なので、
まず Fish アルゴリズムを理解してください。
Fish拡張の最初の一歩は (Finned)Franken/Mutant Fish です。
なお、この項は
A General Logic for Sudoku(www.sudokuone.com/sweb/general.htm) に基づいています。
弱いリンク
generalLogicの基本は弱いリンクです。
Fishは行・列の弱いリンクで構成する解法アルゴリズムです。数独では行・列以外にもブロックの制約条件があり、
Franken/Mutant Fishは行・列・ブロックで構成する解法アルゴリズムです。
さらに、9x9のセルについても1～9のどれかの数字が入るという数独の性質から、各々のセルも弱いリンクとなっています。
合わせると、数独には324の制約があります。
general Logicは、行・列・ブロック・セルの弱いリンクで構成する解法アルゴリズムです。
（なお、強いリンクは弱いリンクに含まれます。）
BaseSetとCoverSet、ランク
- BaseSet : n個の弱いリンクを重なりがないように選びます。 このn個の弱いリンク群をBaseSetと呼びます（n-BaseSet)。 各々の弱いリンクには1つづつ真があり、BaseSet全体でn個の真があります。
- CoverSet : BaseSetとは異なるm個（m≧n)の弱いリンクを、
BaseSetを完全に被覆するように選びます。
これをCoverSetと呼びます（m-CoverSet)。CoverSetには
BaseSetに属さない要素があっても構いません。（実は、
- ランク : BaseSetとCoverSetの組（BaseSet/CoverSetと表記）のランクを次のように定義します。
BaseSet/CoverSetのランク=m-n
General Logic
(1)ランク0
n-CoverSetがn-BaseSetを完全にカバーするとき、
CoverSet-BaseSet（差集合）のセル・数字は真ではありません。
（差集合が空のときは、ここでの論理は成立しない）
もしも真だとすると、それを含むCoverSetの弱いリンクにはBaseSetと共通部分に真がなくなります。
したがって、CoverSet∩BaseSet に含まれる真は n-1 個になります。
つまり、BaseSetの真が足りなくなります。したがって最初の仮定が誤りです。
次の図は最も単純なFishの BaseSet(列)とCoverSet(行) です。
BaseSetとCoverSet、BaseSet-CoverSet(差)、BaseSet∩CoverSet(共通)を確認してください。
なお、BaseSet-CoverSetは1要素に限りません。複数個あってもそれらすべてが除外できます。
(1)ランク1
n-BaseSetを(n+1)-CoverSetでカバーするケースを考えます。
n-BaseSetをカバーするCoverSetの選び方には自由度があります。
解析アルゴリズムとするためには、次の条件が成立する必要があります。
- 条件1 : (n+1)-CoverSetは、n-BaseSetを完全にカバーしている。
- 条件2 : (n+1)-CoverSetの(n+1)個の弱いリンクのうち2つには共通部分があり、 かつn-BaseSetに含まれない要素(共通部分のセル・数字)がある。
次の図で、共通部分の”要素Xは真”と仮定します。
要素XはBasesetに含まれず、かつCoverSetの2つの弱いリンクに含まれているので、 BaseSetの真を含むCoverSetの弱いリンクは（n-1）個となります。 BaseSetの真が足りなくなるので、最初の仮定が誤りです。
次は、BaseSetがセルのランク1の例です。
(2)ランクk(k≧1）
n-BaseSetを(n+k)-CoverSetでカバーするケースを考えます。考え方はランク1と同じです。
解析アルゴリズムとするためには、次の条件が成立する必要があります。
- 条件1:(n+k)-CoverSetは、n-BaseSetを完全にカバーしている。
- 条件2:(n+k)-CoverSetを構成する弱いリンクのうち（k+1）には共通部分があり、かつn-BaseSetに含まれない要素(共通部分のセル・数字)がある。
共通部分の”要素Xは真”と仮定します。
素XはBasesetに含まれず、かつCoverSetの（k+1）個の弱いリンクに含まれているので、 BaseSetの真を含むCoverSetの弱いリンクは（n-1）個となります。 BaseSetの真が足りなくなるので、最初の仮定が誤りです。
General Logic のプログラムコード
General Logicプログラムコードは、GNPX proj数独解析アプリ ソース・プロジェクト にあります。ダウンロードしてください。
アルゴリズムは、Fishを行・列・ブロック・セルに拡張したものなので、比較的簡単です。
ただし、次の点には注意してください。
- General Logicは、Lockedを壊す位置のセル・数字を”真ではない”と除外する論理です。 候補が唯一となったセル・数字を確定することはしません。General Logicの他に、確定するコード（Single）が必要です。
- General Logicで数独を解く最小限のプログラムは、【single+General Logic】で構成できます。
General Logic 解の例
GeneralLogic解の例を示します。上段は 「LockedTriple[3D] r459c2 #168 r37c2#1 is not True」と除外されるセル・数字は同じですが、従来手法に対応する解法がありません。
下段は、ALS-XZ(SinglyLinked)（右下）で同じセル・数字を除外できます。しかし、使われている手法は全く異なります。
3..5....2.5.2...1.....36.....59.7.31..9...4..23.8.46.....79.....7...8.4.8....2..9
5..7....3.3.4...6.....36.....45.1.29..9...4..68.9.27.....27.....1...3.5.7....5..4
以下の表(General Logicの適用例)に示すように、従来手法の解はGeneralLogicで再解釈できます。
次の例は、4次のGeneral Logic(rank0)です。このようにGeneralLogic解に従来手法が対応しないこともあります。GeneralLogicはより一般的な解法であることを示しています。
1..4....8.9.1...5.....63.....13.5.79..3...8..76.2.94.....75.....1...6.4.8....4..2
GeneralLogic解から新解法(従来手法と同様の専用手法）を探ることも課題です。
General Logicの適用例
通常の数独アルゴリズムで解く場面にGeneral Logicを適用した例を示します。
Singleは、候補が唯一となったセル・数字の確定なので、GeneralLogicは必要ないのですが、
BaseSet/CoverSet の最小の適用例として示しました。
| アルゴリズム | 例 | BaseSet | CoverSet | 解説 |
|---|---|---|---|---|
| Single/ LastDigit |
|
BaseSet:b1#6 |
Coverset:c3#6 |
rank0 r68c3#6 is not true |
| Single/ Naked |
|
BaseSet:r1c1 |
Coverset:r1 |
rank0 r1c8#9 is not true |
| Single/ Naked |
|
BaseSet:b2#2 |
Coverset:r2#2 |
rank0 r2c2#2 is not true |
| LockedCandidate/ (type1) |
|
BaseSet:b5#5 |
Coverset:r5#5 |
rank0 r5c9#5 is not true |
| LockedCandidate/ (type2) |
|
BaseSet:b12#7 |
Coverset:r23#7 |
rank0 r2c8#7 is not true |
| LockedSet/Naked | 
|
BaseSet:r6c45 |
Coverset:r6#38 |
rank0 r4c38#3 r4c789#8 is not true |
| LockedSet/Hidden | 
|
BaseSet:b4#249 |
Coverset: r4c23 r5c2 |
rank0 r4c3#3 r5c2#5 is not true |
| Fish | 
|
BaseSet:r57#4 |
Coverset:c25#4 |
rank0 r48c2#6 is not true |
| FinnedFish | 
|
BaseSet:r17#4 |
Coverset: c57#4 b2#4 |
rank1 r3c5#4 is not true |
| Franken/Mutant Fish | 
|
BaseSet: r1#8 c38#8 |
Coverset: r9#8 b13#8 |
rank1 r9c19#8 is not true |
| Finned F/M Fish | 
|
BaseSet: r4568#7 c1#7 b23#7 |
Coverset: r27#7 c23569#7 b16#7 |
rank2 r2c3#7 is not true |
| SkyScraper | 
|
BaseSet: r2#4 b#4 |
Coverset: C34#4 r6#4 |
rank1 r6c3#4 is not true |
| EmptyRectangle | 
|
BaseSet: c8#6 b4#6 |
Coverset: r68#6 c3#6 |
rank1 r8c3#6 is not true |
| X-Chain | 
|
BaseSet: r5#3 b2#3 |
Coverset: r1#3 c25#3 |
rank1 r1c2#2 is not true |
| XY-Chain | 
|
BaseSet: r1c5 r4c45 r7c4 |
Coverset: r1#8 c2#2 r4#3 c4#1 c4#8 |
rank1 r1c4#8 is not true |
| ColoringTrap | 
|
BaseSet :r1#5 C49#5 |
Coverset: b239#5 C7#5 |
rank1 r7c8#5 is not true |
| ColoringWrap | 
|
BaseSet: r7#5 C69#5 b14#5 |
Coverset: r156#5 C23#5 b3#5 |
(左図例はBase/CoverSetによる解が重なっている。） rank1 r1c7#5 is not true |
| MultiColoringType1 | 
|
BaseSet: r8#4 c58#4 |
Coverset: r5#4 C8#4 b33#4 |
rank1 r12c8#4 is not true |
| MultiColoringType2 | 
|
BaseSet: r6#4 c18#4 (BaseSetに含む セルのみが対象) |
Coverset: r29#4 c3#4 b6#4  Coverset: r9#4 c12#4 b6#4 |
rank1 r2c3#4 is not true rank1 r1c9#4 is not true |
| XY-Wing | 
|
BaseSet: r36c2 r6c8 |
Coverset: r3#7 r6#2 c2#3 c8#7 |
rank1 r3c8#7 is not true |
| W-Wing | 
|
BaseSet: r3c4 r7c7 r1#1 |
Coverset: r7#4 c4#14 c7#1 |
rank1 r7c4#4 is not true |
| RemotePair | 
|
BaseSet: r4c5 r5c4 r5c9 r7c9 |
Coverset: r57#7 c5#7 c9#3 b5#3 |
rank1 r7c5#7 is not true |
| XYZ Wing | 
|
BaseSet: r4c78 r9c8 |
Coverset: r4#5 c8#69 b6#9 |
rank1 r6c8#9 is not true |
| XYZ Wing(ALS) | 
|
BaseSet: r36c1 r456c2 |
Coverset: c1#69 b4#1267 (表示略） |
rank1 r5c1#6 is not true |
| SueDeCoq | 
|
BaseSet: r1c5 r2c469 |
Coverset: c2#19 b2#78 |
rank0 r2c3#1 is not true |
| ALS XZ(SinglyLinked) | 
|
BaseSet: r2c46 r3c24 |
Coverset: r2#67 r3#1 b1#6 b2#5 |
rank1 r1c2#6 is not true |
| ALS XZ(DoublyLinked) | 
|
BaseSet: r1c3459 r3c1238 |
Coverset: r1#236 b3#24 b1#156 |
rank0 r2c67#24 is not true |
| ALS XY-Wing | 
|
BaseSet: r1c78 r12c3 r4c57 |
Coverset: r14#1 r1#9 c3#45 c7#2 |
rank1 r4c3#5 is not true |
| ALS Chain | 
|
BaseSet: r4c5 r4c379 r5c5 r6c7 |
Coverset: r4#247 r5#4 c6#4 b6#45 |
rank1 r5c8#4 is not true |
| ALS DeathBlossom | 
|
BaseSet: r2c3 r12368c2 r27c7 |
Coverset: r2#69 r7#7 c2#34567 c7#5 |
rank1 r7c2#7 is not true |
| NiceLoop Continuous | 
|
BaseSet: r8#9 c36#7 c6#1 |
Coverset: r4#7 r6c7 r8c37 |
rank0 r4c1#7 is not true |
| NiceLoop Discontinuous | 
|
BaseSet: r2#5 c1#2 c3#8 r4c4 |
Coverset:r2c13 r4#2 r7#8 c4#8 |
rank1 r7c4#8 is not true |