皆さんはじめまして！去年11月に入社した開発担当のCHOと申します。数理的な問題を考えるのが好きです。メーリングリストでのご対応も担当していますので、宜しくお願い致します。

今回の記事は技術的な長文となりますが、頑張っていきましょう！

さて、お題です。右の図の中央エリアのマスA～Fの中、確定出来るマスはどちらでしょうか？

　　　
1. C
2. F
3. D
4. 複数ある
5. どちらも確定出来ない

分析

答えは三番目のDです。

Dマスの同じ行、同じ列と同じエリアを確認すると、候補は2と4になるということが分かりますが、そのうちD = 2は不可能です。何故かというと、D = 2と「仮置き」するとA = 1、B = 3、C = 3となって矛盾が生じます。

数独の解き方として、「マスに入る数字を１つには決められないけれど絞り込める」という場合に、候補の数字を「仮置き」して、他の箇所で矛盾が起きるかを検証するというものがあります。ただし、「仮置き」してもまた他のマスで「仮置き」が必要な場合があって、そうなると全ての分岐を確認するにはかなりの時間がかかってしまいます。

実は、「仮置き」を使わなくてもDマスを特定できる方法が存在します。また、Dマス以外は確定できないことも、その方法で確認できます。

マスと数字と接続線の図

まず問題の形式を変えましょう。

上の行に未知のマスA～Fを置き、下の行に数字1～6を置きましょう。今まで各マスに対し絞り込んだ結果を灰色の接続線で表します。例えば、マスEの候補は3456なので、上の行のEから下の行の3456にそれぞれ線一本を張ります。

可能な「局所解」

今回、中央エリアのマスしか考えないので、マスのあり得る埋め方を可能な「局所解」と呼びましょう。接続線をどういうふうに選んだら「局所解」になるでしょうか？ （なお今回は「局所解」は複数存在します。）

A～Fにそれぞれ違う数字が入らないといけないので、まず接続線6本を選びましょう。各マスを2本以上の接続線に繋いではいけなくて、各数字に対しても同様です。

つまり、以下のようなものは不可ということになります。

今回の場合、「局所解」はまとめて以下の四通りがあります。

観察してみたら、Dマスが確定されることが分かりました。それ以外のマスがABCとEFに分かれてそれぞれ二通りの可能性があり、組み合わせて四通りになります。実は、それは偶々ではなく、一般的なルールが背後にあります。

接続線の分類

Not all edges are created equal.
接続線（選択肢）はみんな平等ではないんです。

例えば、冒頭の分析から、D = 4は必ず選ぶこととD = 2は選んではいけないことが分かりました。もう少し考えてみたら、A = 1は可能ですが必ずではない。更に、A = 1, B = 2, C = 3とA = 2, B = 3, C = 1二つの組み合わせとも可能な「局所解」の一部としての存在です。

まとめて考えると、以下三つの種別が考えられます。

　　
• 種別1（全て）：その接続線は全ての可能な「局所解」に入る。例えば、D = 4。
• 種別2（不可能）：その接続線はいずれの「局所解」にも入ってはいけない。例えば、D = 2。
• 種別3（未決定）：その接続線は一部の解に入るが、全ての「局所解」には入らない。例えば、A = 1。

数独問題を解く際、もしあるマスに必ずある数字が入ることが分かったら、それが嬉しいに間違いありません（種別1）。一歩譲って、もしあるマスにある数字が入ることが不可能だと分かっても、それも嬉しいでしょう（種別2）。残りはまだ決められないマスと数字の組み合わせです（種別3）。

単に種別を定義しても何も新しい情報が手に入りませんが、仮に種別3の接続線は他の方法で判明できるとしたら話しが変わります。

まず、三種類の接続線を図で表しましょう。

続いて、一つの「局所解」を入手したとしましょう。

その「局所解」と三種類の接続線の関係はどうなるでしょうか？

種別1の接続線は全ての「局所解」に入るので、上右の図の状況は不可能です。

つまり、

持っている「局所解」＝ 種別1の全て + 種別3の一部

ということになります。

仮に種別3（未決定）の接続線が全て判明されたとしたら、種別1と種別2の接続線がそれによって判明出来るはずです。

さて、種別3、つまり一部の「局所解」に入る接続線をどうすれば見つけられるのでしょうか？そのため、もう少し工夫を加えてみましょう。

矢印をつける

右のように矢印をかえてみましょう。

可能な解（接続線六本）をまず一つ見つけて、選んだ接続線を青色で塗って上向きの矢印を付けます。選ばなかった線はそのまま灰色で下向きの矢印を付けます。そうすると、マスもしくは数字から、接続線に沿って他のマスもしくは数字にたどっていくことか可能になります。それを「パス」と呼びましょう。例えば、D→2→B→C→1→A。さらに、出発点と終点のみが同じパスを「サイクル」と呼びます。例えば、E→6→F→5→E。

重要結論

まず、マスABCと数字123の接続構造を考えてみましょう。A=1,B=2,C=3という繋がりでしたら下左のようになりますが、対称的にA=2,C=1,B=3というのも可能です。下右の図で表します。

またマスEFと数字56に対しても同じことが言えます。

それが何故できるかというと、マスと数字の間に偶数辺のサイクルがあるからです。偶数辺のサイクルに入ってさえいれば、その接続線は必ず種別3です。

逆に、決められない種別3の接続線は必ずある偶数辺のサイクルに入っているということも成り立ちます。証明は今回割愛しますが。

さて、結論です。

「ある接続線が（全てではなく）一部の「局所解」に入るということは
その接続線が偶数辺のサイクルに入っていることと等しい。」

それが何の意味を持つかというと、種別3の接続線をそのまま確認しようとすると、「局所解」の数が多すぎてどうしようもない状況に陥りえますが、偶数辺のサイクルを探す方が大いに楽です。例えば、今回の場合は偶数辺のサイクルは二つしかないのです。

因みに、偶数辺のサイクルに入ってない接続線は種別1か種別2になり、手に持っている「局所解」と照合すれば、種別が確定されます。

まとめ

右の図のように、確定出来る線は実線で、まだ候補として残すしかないのは点線とします。そうすると、D = 4ということが確定され、D = 2、E = 3、E = 4という選択肢が実際不可能ということが分かりました。

冒頭の数独問題に戻りますと、候補を以下のように絞り込むことができました。「仮置き」をしなくても。

補足

ここまでやってきたことは制約プログラミング分野のAllDifferent制約という方法を数独問題に適用したものです。「局所解」を一つ求める問題は実際二分グラフの最大マッチング問題で有向グラフの最大流問題に帰着すれば解けます。その後、偶数辺のサイクルを探す問題は有向グラフの強成分分解アルゴリズムを用いれば解けます。いずれも多項式の計算量です。それに比べ、全ての「局所解」を探し出して確認すると指数関数の計算量になります。そして今回唐突に置いた「重要結論」は実際「ベルゲの補題」を数独問題に特有の二部グラフに適用して出来た結果でした。

以上、数独問題のある解き方を紹介してみました。