難問 - 井畑氏からの質問の問題



目次へ

井畑氏から質問された数独の問題を Mathematica で解いた。

SUDOKUWiKI.ORG を参考にした。解き方の定石が書いてあります。

The Logic of Sudoku

問題の出典:  

www.sudokugame.org

問題 - most

f:id:MMAys:20171029205747p:plain

候補図

f:id:MMAys:20171029205814p:plain

Step by step の解答

このパズルは NakedSingle (裸のシングル)、Hidden Single (隠れたシングル)と Naked Pairs を使って答えが求まる。

この表の1番目の手順が意味することは Naked Singleを探した結果、3行1列に 1を入れる。以下同様にして 計19回の手順を解けない配置に至る。

f:id:MMAys:20171029205832p:plain

手順 16 の Naked Pairs の説明

Naked Pairs の説明は SUDOKUWIKI.ORG の Naked Candidates に載っている。

f:id:MMAys:20171029223136p:plain

手順 17 の Naked Pairs の説明

f:id:MMAys:20171029223148p:plain

手順 18 の Naked Pairs の説明

f:id:MMAys:20171029223158p:plain

手順 19 の Naked Pairs の説明

f:id:MMAys:20171029223228p:plain

手順1 から 19 までのアニメーション

次をクリックして解答のアニメーションを見ることができる。

[ テスト-2:  Button ]  + をクリックすれば次の手順に行くことができる。1回目のクリックでは kkk = 1 , i = 0 になり図は変化しない。2回目のクリックで kkk = 2 , i = 1 になり図が変化する。これを繰り返して手順を進める。

[ テスト-4:  Animator ]  + をクリックすれば次の手順に行くことができる。1回目のクリックでは  i = 0 になり図は変化しない。2回目のクリックで  i = 1 になり図が変化する。これを繰り返して手順を進める。

手順 20 の 候補の図

f:id:MMAys:20171029212142p:plain

Simple Coloring の定石

Simple Coloring の説明は SUDOKUWIKI.ORG の Single's Chains に載っている。

3 について共役ペア( conjugate pair ) を探し図に示す。3行2列の 3 と 3行7列の 3 が共役ペアになっている。3 の全ての共役ペアを探すと8個が見つかる。図に赤と緑の丸で描き入れてある。ただし赤と緑色は交互に色分けしてある。

f:id:MMAys:20171029213712p:plain

{4,7}番地の3 が緑で {7,7}番地の3 が緑なので緑色の3 を削除できる。削除されるべき 3 は次の5個である。 {4,7}番地の 3 を {3,{4,7}} と表記すれば次のようにリストで表記できる。

{{3,{4,7}}, {3,{6,3}}, {3,{6,3}}, {{3,{7,7}}, {3,{9,2}}}
f:id:MMAys:20171029213732p:plain

手順 21 の図

f:id:MMAys:20171029215336p:plain

手順 21 の候補の図

f:id:MMAys:20171029215354p:plain

手順 21 以降 の step by step の解答

f:id:MMAys:20171029215411p:plain

手順 21 以降のアニメーション

次をクリックして解答のアニメーションを見ることができる。

[ テスト-2:  Button ]  + をクリックすれば次の手順に行くことができる。1回目のクリックでは kkk = 1 , i = 0 になり図は変化しない。2回目のクリックで kkk = 2 , i = 1 になり図が変化する。これを繰り返して手順を進める。

[ テスト-4:  Animator ]  + をクリックすれば次の手順に行くことができる。1回目のクリックでは  i = 0 になり図は変化しない。2回目のクリックで  i = 1 になり図が変化する。これを繰り返して手順を進める。

今後の課題

  • Simple Coloring 定石を使って解くことができた。この定石のアルゴリズムのプログラムを作ることが課題です。
  • Simple Coloring の定石は Simple Chains とも呼ばれる。共役ペアの繋がり(チェイン)を解析して解く方法なので、繋がりを表現するために Mathematica のグラフ( Graph ) オブジェクトを使うことを試みている。
  • Sudoku を行列( Matrix ) を使って表現してきたがグラフの表現に変換することによりグラフの特性を調べる関数を利用できる。

備考:

  • 今回は、最新版の Mathematica 11.2 を使った。Wolfram Cloud で Manipulate に インクレメントボタン+ を使えるようになった。改善が進んでいることを確認した。
  • Wolfram Cloud 環境が整備され Manipulate の不具合が劇的に改善された。

目次へ