プログラミングとかブログ

Unity/C#/SRPGStudio/RPGツクールMVの情報とかその他気になったことを調べて書きます。

数独スコアラー説明書

windowsストアで販売中の数独採点アプリ「数独スコアラー」の説明です。
www.microsoft.com

使い方

f:id:shirakamisauto:20180127190136p:plain
①テキストボックスに数独の問題を入力します。半角数字のみで、空白を0として入力します。
正しく入力できた場合、解くボタンが押せるようになります。
②解くボタンを押すことで問題を解きます。解けた場合はスコアが算出され、スコアがびよーんと動きます。
③リセットボタンを押すと問題と盤面とログをリセットします。
④入力した問題を表示する盤面です。
⑤どんな解法ロジックを使用したかなどを表示します。
⑥ここにチェックを入れると問題が解けなかったときに総当たり法で解きます。
スコアが跳ね上がるので注意です。
⑦ここにチェックを入れるとどの解法ロジックを使用して解いたかをログに表示します。

解くとこんな感じになります。
f:id:shirakamisauto:20180127185600p:plain

※問題は「超難問ナンプレAクラス2」より引用

処理解説

CRBE法→単一候補法→単一マス法の順で適用した後、
共有候補法→双子法→対角線法→三つ子法の順番で解放ロジックを適用していきます。
適用できた場合は単一候補法と単一マス法をやれるだけやって、再び共有候補法から適用します。
これを解けるか解けなくなるまでループします。
終了するまでの探索量を難易度スコアとしています。
具体的なロジックの説明は次項でします。


※盤面図や解法名https://www.oit.ac.jp/japanese/toshokan/tosho/kiyou/rikouhen/56-1/01r.pdfから引用

解説の前に

数独の盤面をi行j列の行列(i,j)として扱います。
f:id:shirakamisauto:20180127190335p:plain
ブロックも行列[i,j]扱いにします。
f:id:shirakamisauto:20180127190326p:plain

CRBE法

ある数字が入り得るマスを周辺の列(column)、行(row)、ブロック(block)から絞り込む(elimination)方法です。
下図では一番数の多い8を対象にします。
f:id:shirakamisauto:20180127190346p:plain
ブロック[1,3]を見ると、空きマスは(1,7)、(2,7)、(2,8)、(2,9)、(3,7)にあります。
すると、(1,5)に8があるため、1行目には8は入りません。
また、(2,1)にも8があるため、2行目にも8は入りません。
よって、下図のように(3,7)にしか8が入らないことが分かります。
f:id:shirakamisauto:20180127190406p:plain
こんな感じでほかのにも適用していきます。

単一候補法

あるマスに候補数字が一つしかなければそのマスはその候補数字で確定するというロジックです。
下図で○のついた候補数字4のあるマスは4以外の候補数字がないため、このマスは4で確定します。
f:id:shirakamisauto:20180127190424p:plain

単一マス法

ある候補数字がマス(i,j)にしか入らないことが分かっているとき、
その候補数字以外の候補数字はマス(i,j)から消去されるというロジックです。
下図で○のついた候補数字2はこのブロック内で1つしかないため、このマスは2で確定します。
f:id:shirakamisauto:20180127190443p:plain

双子法

独立双子法

独立双子法は同じ行、または同じ列、または同じブロックの中で候補数字が2つしかなく、
かつ候補数字が同一である2つのマスがあったとき、
その2マスを含む行、列、ブロックのその2マス以外のマスにその2つの候補数字は入り得ず、
候補から消去されるロジックです。
下図の(2,5)、(2,6)を見ると候補数字が2と3しかありません。
したがって、この2マスを含む行、列、ブロックには2と3は入らないため、
下図のように(2,1)と(2,3)の候補数字から2が消去され、
(1,4)と(1,5)の候補数字から2と3が消去されます。
f:id:shirakamisauto:20180127190455p:plain

居候双子法

同じ行、または同じ列、または同じブロックの中の2マスに共通の候補数字が2種類あったとき、
かつその候補数字がその2マスにしか入らないとき、
その2マスの候補数字から共通の候補数字以外の候補数字は消去されます。
下図の1行目を見ると、この行内で候補数字8、9はマス(1,4)、(1,5)にしかないことが分かります。
よってマス(1,4)、(1,5)のどちらか一方に8が、もう一方に9が入るので、
下図のように、マス(1,4)、(1,5)の8、9以外の候補数字は消去されます。
f:id:shirakamisauto:20180127190506p:plain

三つ子法

基本的に双子法の拡張です。

独立三つ子法

独立三つ子法は同じ行、同じ列、同じブロックの中で候補数字が3つしかなく、
かつ候補数字が同一である3つのマスがあったとき、
その3マスを含む行、列、ブロックのその3マス以外のマスから
その3つの候補数字は消去されるという解法ロジックである。
以下の図に独立三つ子法の例を示します。
f:id:shirakamisauto:20180127190517p:plain
マス(1,1)、(2,1)、(3,1)に着目すると、この3マスには候補数字が2、4、6のどれかしか入りません。
よって、このブロック内の他のマスの候補数字から2、4、6 は消去されます。
ここまでなら独立双子法の単純な拡張ですが、三つ子法の適用条件はこれ以外にもあります。
3つの数字から2つを選ぶ組合せは3C2=3通り存在します。
独立三つ子法は少なくともその3通りが揃っていれば適用できます。
3つの候補数字がn1、n2、n3だとしたとき、(n1,n2)、(n2,n3)、(n1,n3)の組が揃っていれば、独立三つ子法が適用できます。
下図を見てください。
f:id:shirakamisauto:20180127190524p:plain
n1=2、n2=4、n3=6とすると、どの例でも(2,4)、(4,6)、(2,6)の組が
○をつけた候補数字のあるマスに存在しているため、 独立三つ子法が適用できます。

居候三つ子法

居候三つ子法は同じ行、または同じ列、または同じブロックの中の3マスに共通の候補数字が3種類あったとき、
かつ、その候補数字がその3マスにしか入らないとき、
その3マスにある候補数字から3 種類の候補数字以外の候補数字は消去されるという解法ロジックです。
下図のマス(1,3)、(2,3)、(3,3)に着目すると、この3マスにしか候補数字7、8、9は入らないことが確定しています。
f:id:shirakamisauto:20180127190535p:plain
よって、マス(1,3)、(2,3)、(3,3)から7、8、9 以外の候補数字は消去される。
居候三つ子法の場合も独立三つ子法と同様に、3種の数字のうち少なくとも2種が揃っていれば適用できます。
f:id:shirakamisauto:20180127190543p:plain

共有候補法

共有候補法は、あるブロックとある行(または列) で共有するマスの情報を用いる解法ロジックです。
ブロックの情報から行(または列) の候補を消去する方法①と
行(または列) の情報からブロックの候補を消去する方法②がある。
①を下図で説明します。
f:id:shirakamisauto:20180127190553p:plain
ブロック[1,2]ではマス(1,4) か(1,6)にしか6が入りません。
よってこの2マスを共有する1行目のマス(1,1)、(1,2)から6は消去されます。
次に②を下図で説明します。
f:id:shirakamisauto:20180127190602p:plain
1行目ではマス(1,4)か(1,6)にしか8が入りません。
よってこの2マスを共有するブロック[1,2]のマス(3,4)、(3,5)、(3,6)から8は消去されます。

対角線法

下図に対角線法の例を示します。
f:id:shirakamisauto:20180127190611p:plain
○をつけた候補数字5は(2,5)、(2,9)、(6,5)、(6,9)に存在しています。
このとき、(2,5)に5が入ると、2行目と5列目の(2,9)、(6,5)に5は入りません。
よって(6,9)に5が入ることが確定します。
逆に、(2,9)に5が入ると、2行目と9列目、すなわち(2,5)、(6,9)に5は入りません。
よって(6,5)に5が入ることが確定します。
つまり、左上に入れば右下に、右上に入れば左下にと、この2パターンしか候補5の入る組合せはありません。
したがって、候補5がどちらのパターンで入ったとしても、
(2,5)、(2,9)、(6,5)、(6,9)以外の2行目、6行目、5列目、9列目のマスの候補数字から候補数字5は消去されます。
対角線法は下図のようにマスに入った数字を用いても適用できます。
f:id:shirakamisauto:20180127190619p:plain
数字9は3列目でマス(3,3)、(6,3)のどちらかに入り、7列目では、マス(3,7)、(6,7)のどちらかに入ります。
この場合でも数字は対角線上に配置されることになり、
マス(3,3)、(6,3)、(3,7)、(6,7)を除いた3行目と6行目のマスに9が入らないことが分かります。