『今週の問題』第234回　解答

広島県　清川　育男　さんが 「数独」作成プログラムを作られたそうです。
十進ベーシックで(OUT OF MEMORY)にならない制約で、RANDOMIZE　を使って位置と数字を決め、単一解であれば、それが問題となるそうです。

◆広島県　清川　育男　さんからのコメント。

ヒント数２４個の問題を紹介します。 

 DATA  8 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 9 
 DATA  0 , 0 , 0 , 4 , 0 , 0 , 0 , 0 , 2 
 DATA  0 , 0 , 0 , 0 , 6 , 5 , 0 , 0 , 0 
 DATA  0 , 0 , 0 , 0 , 3 , 0 , 0 , 0 , 0 
 DATA  3 , 8 , 5 , 0 , 0 , 6 , 0 , 0 , 0 
 DATA  0 , 6 , 0 , 0 , 1 , 7 , 8 , 0 , 0 
 DATA  0 , 0 , 0 , 0 , 0 , 1 , 0 , 9 , 3 
 DATA  0 , 5 , 0 , 0 , 0 , 0 , 6 , 4 , 0 
 DATA  7 , 0 , 2 , 0 , 9 , 0 , 0 , 0 , 0

高橋　謙一郎さんの掲示番からの情報です。
最小のヒント数は１６が可能かどうかということのようです。
１７個の問題が載っていたので解かせてみました。
同じような発想からスタートするようですね。 


 0  9  8  0  0  0  0  0  0 
 0  0  0  0  7  0  0  0  0 
 0  0  0  0  1  5  0  0  0 
 1  0  0  0  0  0  0  0  0 
 0  0  0  2  0  0  0  0  9 
 0  0  0  9  0  6  0  8  2 
 0  0  0  0  0  0  0  3  0 
 5  0  1  0  0  0  0  0  0 
 0  0  0  4  0  0  0  2  0 


 1 局面

 2 局面

 4 局面

 28 局面

 234 局面

 234 局面

 深度  6 
 7  9  8  6  2  4  3  1  5 
 3  1  5  8  7  9  2  4  6 
 2  6  4  3  1  5  9  7  8 
 1  2  9  5  8  7  4  6  3 
 6  8  3  2  4  1  7  5  9 
 4  5  7  9  3  6  1  8  2 
 9  4  2  1  5  8  6  3  7 
 5  3  1  7  6  2  8  9  4 
 8  7  6  4  9  3  5  2  1 

 15.8800000000001 

 OK

 0 局面

 答え 1 個
 探索終了

◆静岡県　ふーさん　さんからの解答


9,7,4‖5,3,1‖6,8,2
1,2,5‖8,6,9‖3,7,4
8,6,3‖7,4,2‖1,9,5
＝＝＝＝＝＝＝＝＝＝
6,3,8‖2,5,4‖9,1,7
2,9,1‖3,8,7‖5,4,6
5,4,7‖9,1,6‖8,2,3
＝＝＝＝＝＝＝＝＝＝
3,1,6‖4,2,8‖7,5,9
4,5,9‖1,7,3‖2,6,8
7,8,2‖6,9,5‖4,3,1
９行９列の行列と考える。 ナンバープレースは面倒な感じでいままでまともに取り組んでいなかった。
今回はちょっと挑戦してみました。

◆広島県　清川　育男　さんからの解答


 9,7,4‖5,3,1‖6,8,2
 1,2,5‖8,6,9‖3,7,4
 8,6,3‖7,4,2‖1,9,5
 ＝＝＝＝＝＝＝＝＝＝
 6,3,8‖2,5,4‖9,1,7
 2,9,1‖3,8,7‖5,4,6
 5,4,7‖9,1,6‖8,2,3
 ＝＝＝＝＝＝＝＝＝＝
 3,1,6‖4,2,8‖7,5,9
 4,5,9‖1,7,3‖2,6,8
 7,8,2‖6,9,5‖4,3,1
A(9,9) としたとき、A(2,4)=8,A(2,5)=6,A(2,6)=9が直ちに決定されます。
次に(2,1)=1,A(2,3)=5,A(3,2)=6,A(3,3)=3 が決定します。
あとは、試行錯誤ですが局面は狭いとおもいます。
この問題は集中力ですね。

プログラムに挑戦しました。　　　 

 0  0  4  5  3  1  6  0  0 
 0  2  0  0  0  0  0  7  0 
 8  0  0  7  4  2  0  0  5 
 6  0  8  0  0  0  9  0  7 
 2  0  1  0  8  0  5  0  6 
 5  0  7  0  0  0  8  0  3 
 3  0  0  4  2  8  0  0  9 
 0  5  0  0  0  0  0  6  0 
 0  0  2  6  9  5  4  0  0 

 第１回目のチェック
 A( 2 , 5 )= 6 ,A( 2 , 6 )= 9 ,A( 5 , 8 )= 4 ,A( 6 , 5 )= 1 ,
 A( 6 , 8 )= 2 ,A( 7 , 3 )= 6 ,A( 8 , 3 )= 9 ,A( 8 , 5 )= 7 ,
 A( 8 , 6 )= 3 ,

 0  0  4  5  3  1  6  0  0 
 0  2  0  0  6  9  0  7  0 
 8  0  0  7  4  2  0  0  5 
 6  0  8  0  0  0  9  0  7 
 2  0  1  0  8  0  5  4  6 
 5  0  7  0  1  0  8  2  3 
 3  0  6  4  2  8  0  0  9 
 0  5  9  0  7  3  0  6  0 
 0  0  2  6  9  5  4  0  0 

 第２回目のチェック　
 A( 2 , 1 )= 1 ,A( 2 , 4 )= 8 ,A( 2 , 7 )= 3 ,A( 2 , 9 )= 4 ,
 A( 3 , 3 )= 3 ,A( 3 , 7 )= 1 ,A( 3 , 8 )= 9 ,A( 4 , 5 )= 5 ,
 A( 4 , 6 )= 4 ,A( 4 , 8 )= 1 ,A( 5 , 6 )= 7 ,A( 6 , 4 )= 9 ,
 A( 6 , 6 )= 6 ,A( 7 , 7 )= 7 ,A( 7 , 8 )= 5 ,A( 8 , 1 )= 4 ,
 A( 8 , 4 )= 1 ,A( 8 , 7 )= 2 ,A( 8 , 9 )= 8 ,A( 9 , 1 )= 7 ,
 A( 9 , 8 )= 3 ,A( 9 , 9 )= 1 ,

 0  0  4  5  3  1  6  0  0 
 1  2  0  8  6  9  3  7  4 
 8  0  3  7  4  2  1  9  5 
 6  0  8  0  5  4  9  1  7 
 2  0  1  0  8  7  5  4  6 
 5  0  7  9  1  6  8  2  3 
 3  0  6  4  2  8  7  5  9 
 4  5  9  1  7  3  2  6  8 
 7  0  2  6  9  5  4  3  1 

 第３回目のチェック
 A( 1 , 1 )= 9 ,A( 1 , 2 )= 7 ,A( 1 , 8 )= 8 ,A( 1 , 9 )= 2 ,
 A( 2 , 3 )= 5 ,A( 3 , 2 )= 6 ,A( 4 , 2 )= 3 ,A( 4 , 4 )= 2 ,
 A( 5 , 2 )= 9 ,A( 5 , 4 )= 3 ,A( 6 , 2 )= 4 ,A( 7 , 2 )= 1 ,
 A( 9 , 2 )= 8 ,

 9  7  4  5  3  1  6  8  2 
 1  2  5  8  6  9  3  7  4 
 8  6  3  7  4  2  1  9  5 
 6  3  8  2  5  4  9  1  7 
 2  9  1  3  8  7  5  4  6 
 5  4  7  9  1  6  8  2  3 
 3  1  6  4  2  8  7  5  9 
 4  5  9  1  7  3  2  6  8 
 7  8  2  6  9  5  4  3  1
完成。　

◆東京都　明　さんからの解答


9,7,4‖5,3,1‖6,8,2
1,2,5‖8,6,9‖3,7,4
8,6,3‖7,4,2‖1,9,5
＝＝＝＝＝＝＝＝＝＝
6,3,8‖2,5,4‖9,1,7
2,9,1‖3,8,7‖5,4,6
5,4,7‖9,1,6‖8,2,3
＝＝＝＝＝＝＝＝＝＝
3,1,6‖4,2,8‖7,5,9
4,5,9‖1,7,3‖2,6,8
7,8,2‖6,9,5‖4,3,1
求め方

●手順１

まず？に１〜９を記載します。

●手順２

各？について、縦、横、同一ブロック内にある確定した数字を消して行きます。
全ての？についてこの操作をします。

●手順３

？に残った数字が１つになった場所がないか確認します。
残った数字が１つの場所があれば、これを確定した数字として手順２に戻ります。

以上の繰り返しで全ての場所の数字が確定すれば完了です。
今回の問題は上記ですべての数字が確定するようです。

上記で確定できない場所が存在する場合。

●手順４

それぞれ、縦、横、同一ブロックごとに複数候補に残った数字を見て、ただ１つの数字がないか確認します。
例、縦列を見て　"1,2,3"　　"2,3,4"　　"2,3,4"　であれば　1
この数字は確定した数字となります。
すべての縦、横、同一ブロックを確認し、新たに確定数字が確認できたら手順２に戻ります。

以上繰り返しですべての数字が確定すれば完了です。
上記で複数の候補が残るようであれば、適当な場所の候補の数字を仮定して手順２から繰り返します。
別に数字を確定させる方法があるのではないかと思っていますが、現在まで考えたアルゴリズムは以上です。

-------------------------

数独は大分前に興味を持ち、プログラムを作りましたが、多くの問題が手順４までで解けました。
難しい問題では候補が残ってしまい、候補の数字を仮定して解かなければなりませんでした。
しかし、数独の楽しみ方はやはり頭の中で解いて行くことでしょうね。
今回WEB検索をしてみましたら解き方講座などがでていました。 その内ゆっくり見てみるつもりです。　

◆群馬県　天10　さんからの解答


9,7,4‖5,3,1‖6,8,2
1,2,5‖8,6,9‖3,7,4
8,6,3‖7,4,2‖1,9,5
＝＝＝＝＝＝＝＝＝＝
6,3,8‖2,5,4‖9,1,7
2,9,1‖3,8,7‖5,4,6
5,4,7‖9,1,6‖8,2,3
＝＝＝＝＝＝＝＝＝＝
3,1,6‖4,2,8‖7,5,9
4,5,9‖1,7,3‖2,6,8
7,8,2‖6,9,5‖4,3,1
求め方

本問題に関しては、数独の標準的な考え方のみで回答可能でした。

1.
各行、各列に同じ数字が入らないという条件から、ある数字のみを着目し、その数字の行と列を除外すると 、3ｘ3のブロック内でひとつだけ空いた場所ができた場合、その場所はその数字が入る場所となる。
問題の場合で8に着目した場合９行２列や、２行４列がその場所になる。

2.（１の発展？）
１のやり方で確認した際に、3ｘ3のブロック内の行または列で位置が特定できなくても、どこかしらに入ると確実な場合、別のブロックには入らないとすることができるので、その部分を除外することでおくことができる
問題の場合で３に着目した場合下の真ん中のブロックには８行目にしか置くことができないので、9行8列が３と確定することができる。

今回の問題では以上の行為を各数字で繰り返すことで、確定することができる。

なお、数独の難度が上がると上の行為だけでは解けない事が多くなる。

その際に自分が使う方法としてmマス空いている内のｎマスで、同じ種類の数字がn個が入る場合、他のマスにそのn個の数字は入らないということを使用している。

例：４マス空いていてa、b、ｃ、ｄの数字が残っている場合でa,ｂがすべてのマスに入る可能性があってもa、bだけが入るマスが２マスのとき、そのマス以外からはa、bを除くことができる

◆大阪府　yamagata　さんからの解答


9,7,4||5,3,1||6,8,2
1,2,5||8,6,9||3,7,4
8,6,3||7,4,2||1,9,5
=====  =====  =====
6,3,8||2,5,4||9,1,7
2,9,1||3,8,7||5,4,6
5,4,7||9,1,6||8,2,3
=====  =====  =====
3,1,6||4,2,8||7,5,9
4,5,9||1,7,3||2,6,8
7,8,2||6,9,5||4,3,1
タテとヨコの列と小枠にすでにはいっている数字をみながら空いているマスにいれられない数字を消去していきのこった数字をすでに入っている数字の並びと検討して絶対ここでしかないという決定的な数字をいれていく。
その決定の基準はタテの列横の列と小枠に１−９の数字を重複しないでいれるという規則が判断基準となる。
タテとヨコと小枠で重複しないという三つの条件を満たす決定的な数字とマスは容易に発見できる。
数字がうまって行くにつれて発見がたやすくなる。
その場所に他の数字も入れられる場合は絶対其処に数字をいれないことあいている各マスにいれられる数字は絶対に一つの数字しかない。
もし数字と場所をまちがえると必ず破綻する。
そして最後まで矛盾なく全数字がはいったらそれは必ず正解であり別解はない。

数独はスイスの数学者が考案したものですが、ニコリという日本の会社が これを発展させ、日本よりヨーロッパの各国の新聞にひろく定期的に掲載されていて それが向こうの沢山の人達をひきつけて現在ものすごい人気になっています。
スイスうまれの日本育ちです。
やさしい問題からとっても難しい問題とか表出数字の配置がとても芸術的な ものまでいろいろ出題されています。
解くばかりでなく難しい問題をつくりだすことに情熱を燃やしている人達 が沢山おられるようでそれをニコリに提出して公表してもらっているようです。
規則はとても単純なのですがとても奥が深いものです。

最大のポイントは特定のマスに入りえない数字を消去法でけしていって、 最後にのこった一つの数字を確定できたときにだけ其処ににいれる
つまり絶対その数字以外にない時だけその数字をいれるということです。

二つ以上候補があったときには、絶対記入しないことです。
１−９の各数字がいれられる場所は九箇所ずつあります。
しかしその各数字が入れられる場所の組あわせは一とうりしかありません。
つまり別解というものはありません.　
回答は一組のくみあわせしかありません。
だから、やっている途中で何処か１箇所でも間違うとかならず重複がでてきて 完成することができなくなります。
だから一マスずつ絶対に確定したものをいれていくことです。
それからタテ、とか横とか小枠の単位で後２数字とかあと一数字とか とかにもっていくと容易に確定します。
それから後３数字のときもそののこった数字とその箇所に交差している 別方向のならびにすでにでてきている数字を検討するとその場所に いれられる数字がうかびあがってきます。
一数字のこった場合は簡単に確定します。
２数字のときはその一方が確定すればもう片方はただちに確定します。

難しい問題は表出数字がとてもすくなくしてあったり、確定のヒントがわかりにくい ところにかくされていたり、それからある特定の１箇所が確定すると 次々に確定していくようになっていたりします。
そのときにはその特定の 場所がわからないといっこうにすすまないようになっていたりします。
とにかく、回答を早くただしくだすためには、集中力と記憶力、論理と分析力がいるとおもいます。
だからヨーロッパの人達に人気があるのだとおもいます。

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる