数独ナンバープレース

数独(ナンバープレース)解法プログラムを作って見ました。
「解法」などと言う難しいことは知らなかったので、コンピュータを酷使する方法で実現しました。
手順は次のとおりです。

数値の決まっていないセルに指定可能な値をすべて求める。
指定可能な値を一つしか持っていないセルには「指定可能な値」を割り当てる。
指定可能な値が一つしか無いセルが無い場合２以上の「指定可能な値」を持つセルに指定可能な値の小さい方(理由はない単なる決め打ち)を割り当てる。
上記(1～ )を繰り返し、「指定可能な値」がルールに反する(割り当てられない)場合に２以上の「指定可能な値」を持つセルまで戻って値を変更する。
戻るときに指定値をクリアーする。
「指定可能な値」は数独の特性から最大は９である。
9 までのすべての「指定可能値」を対象にすれば何も指定していない場合にも解を出せる。
サーバに負担が掛かるのでセルの変更回数を 3000 回に制限しています。
全部とは言えませんが、某社の電子辞書にある数独問題の上級も解けます。
何もし指定せずに実行させるとすぐに答えが出るのに(いつも同じです)、中々答えのでない組み合わせがあります

最初に数値を直接入力する html を作ったところ、「面倒くさい」と言われたので数値を選択する html も作ってみました。入力時点では数値チェックは入っていないので、実現不能なパターンも拒否していません(CGI ではチェックしています)。

数独データの数値を選んで「解く」をクリックして下さい。
Select を使用したタイプです

数独データの入力して「解く」をクリックして下さい。
TEXT 入力で実行しています。マウスとキーを使用すればこちらの方が使いやすいと思うのですが、所詮個人差です。

数独解法プログラム
CGI で使用しているプログラムです。
このプログラムで使用しているcgiの原型を置きます。
文字コードは「ISO-2022-JP」です。直接ダウンロードすると読めない部分があるかも知れません。
Linux で作成しています。次の様に直接実行できます(Debug 機能です)。
- 環境変数 REQUEST_METHOD に "STDIN" を設定すると標準入力からセルの値を入力できます。
  次の様に実行すると計算結果が得られます。
```
  $ mv sudoku.txt sudoku.pl   <<-- 変更する必要はない。
                                   txt を実行するのは気分が悪いので
  $ chmod +x sudoku.pl
  $ export REQUEST_METHOD="STDIN"
  $ ./sudoku.pl
  17=1
  27=2
  37=3
  47=4
  57=5
  67=6
  77=7
  87=8
  97=9
  +---+---+---+---+---+---+---+---+---+
  | 2 | 3 | 6 | 7 | 8 | 9 | 1 | 4 | 5 |
  +---+---+---+---+---+---+---+---+---+
  | 5 | 8 | 9 | 1 | 3 | 4 | 2 | 6 | 7 |
  +---+---+---+---+---+---+---+---+---+
  | 1 | 4 | 7 | 2 | 5 | 6 | 3 | 8 | 9 |
  +---+---+---+---+---+---+---+---+---+
  | 3 | 9 | 8 | 6 | 2 | 5 | 4 | 7 | 1 |
  +---+---+---+---+---+---+---+---+---+
  | 6 | 1 | 4 | 3 | 7 | 8 | 5 | 9 | 2 |
  +---+---+---+---+---+---+---+---+---+
  | 7 | 2 | 5 | 9 | 4 | 1 | 6 | 0 | 3 |
  +---+---+---+---+---+---+---+---+---+
  | 8 | 6 | 2 | 5 | 9 | 3 | 7 | 1 | 4 |
  +---+---+---+---+---+---+---+---+---+
  | 9 | 5 | 3 | 4 | 1 | 7 | 8 | 2 | 6 |
  +---+---+---+---+---+---+---+---+---+
  | 4 | 7 | 1 | 8 | 6 | 2 | 9 | 3 | 0 |
  +---+---+---+---+---+---+---+---+---+
```
- 標準出力に表示するのは計算結果だけで入力チェックは HTMLのままです。
- CGI で現用中のものは速度を上げるために少し変更しました。
  面倒になるので原型を置くことにしました。
  ハッシュを使用しているところをアレーに直すと速度が上がるようです。
  このプログラムはあらゆる形式のものが解けると思っています。
  いくつかのパターんで、おびただしい繰り返しが発生し処理時間短縮の必要が発生しました。
  速度向上を狙って変更したのですが、４倍くらいにしかなりませんでした。
  マトリックスなので、方法はあると思います。
- 670 MHz の Pentium 3 で 20分くらい掛かっても解けないものもありました。
  この難解な問題の初期値を１つ代えるだけで1分もかからず答えが出る事もあります。このあたりが「アルゴリズム」を無視した、たたり(?)なのでしょう。

Top に戻る

数独 ナンバープレース

数独ナンバープレース