数独

パズルプログラミング勉強会 のページに触発されてこのページを作りました。感謝してます。

初めて研究室に配属されたときにやってみたことが、数独(ナンバープレイス とも呼ばれる)をニューラルネットで解いてみることだった。 ただ、ニューラルネットなどを利用しなくても、 普通に解くことができるはずだと、ずっと思っていた。

パズルの解法でよく使われる手法に「バックトラック」がある。 これは、深さ優先探索とも呼ばる。これをつかって、解いてみる。

バックトラックの基本

基本的には、あり得る盤面を総当たりするという、コンピュータらしい解法。 ただ、総当たりの仕方に少々工夫があり、同じ関数を再帰的に呼び出す。

具体的には、以下のようになる。

solve()
{  
  種々の処理をこなす
  if(終了している){
    終了
  }else{
    for(考えられる手を洗い出して全部){
      一手だけ盤面を進める
      solveをコール
      元に戻す
    }
  }
}

数独とは

数独のルールは、すいません。ご自分で調べてください。 もしくは、 数独のページをどうぞ。 また、解き方のコツは 数独（ナンバープレイス）解法教室 に書かれています。

数独特有の処理

以下の基本的なものをチェックし、はじめに数字を入れられるだけ入れる。

• 一つの列に同じ数字は二つ以上入らない。 (exist_row)
• 一つの行に同じ数字は二つ以上入らない。 (exist_column)
• 一つのエリア(太線で囲まれた部分)に同じ数字は二つ以上入らない。 (exist_area)

• エリアで、数字がある列のみに存在するかをチェック、検出 (check_area_with_row)
• エリアで、数字がある行のみに存在するかをチェック、検出 (check_area_with_column)

以上のルーチンを使ってどうするか

1. まず、以上のルーチンを使って、数字が入り得ないところをすべてチェックする。 その結果残った升目すべてに、数字をいれる。
   以上数字を入れられなかったら終了。 それ以外は続ける。
2. 次に、入る数字の候補が２つの升目を見つけ、 とりあえず一つを入れてみる。
3. 1.に戻る
4. 一歩戻す。

結果

おそらく、ほとんどの問題は解けると思います。 ちなみに、解が複数あるときはそのうちの一つを表示し、 複数個あることを知らないでしょう。

ただ、複数個あることを知るように変更することもできます。 具体的には、バックトラックの中での「終了」の部分で終了せず、 typeとかいう変数を用意して１足せばよいでしょう。 ただ、いまの状態に満足しているので、これ以上の変更はないと思います。 気になる方はやってみてください。

具体的なルーチンの説明

マスに書き込むことができるかどうかをチェックすることが、 このパズルでの最大のポイントです。 というのも、ある数字を書き込めない場所を洗い出し、 その結果唯一残った場所にその数字を書き込む、 という手順を繰り返して解を求めていくからです。

ということで、このプログラム内で使っている、 重要なルーチンの説明をしておきます。

左のような場合、斜線丸の部分を指定した場合、 「3」「5」の場合はすでに おなじ列に「3」「5」が入っているのでtrueを返し、 それ以外の数字の場合はfalseを返す。

左のような場合、斜線丸の部分を指定した場合、 「4」「1」の場合はすでに おなじ行に「4」「1」が入っているのでtrueを返し、 それ以外の数字の場合はfalseを返す。

左のような場合、斜線丸の部分を指定した場合、 「2」「9」の場合はすでに おなじエリアに「2」「9」が入っているのでtrueを返し、 それ以外の数字の場合はfalseを返す。

斜線丸のマス指定すると、そのマスを含んだエリアが検査対象になる。 この場合、「6」は指定したエリアの３行目のどこかに入る。 ということで、「6」を指定すると、3を返す。 例えば「4」は、３行目と５行目両方にはいることが考えられる。 その場合は、-1を返す。 この作業を行なうことにより、(4,0)に「6」が入ることが分かる。

図は描くのがめんどうなので省略。 上と同じで、縦方向に検査するだけ。