私について

私は１６歳で、プログラミングをこの数年楽しんでいます。

ソルバーについて

ソルバーは backtrackingという手法を使っています。３ケタの番号をもつナンバーロックを開けることを考えてみてください。まず111からはじめて、112,113とやってみます。119までやってだめならつぎは121からはじめます。そして112,113と。数独を解くのもこれと同じです。ただし桁数は3桁ではなく50-60となります。

アプレットが、「解く」ボタンを押すことなく、自動的にパズルの入力が終了したことを検出できるようにしました。その方法はどこにも見つけられなかったので、いろいろ考えました。

たとえば数独の問題が１行の数列で表されているとします。ソルバーはそれを左から右に向かって解を探します。この方法では多数の解のなかの最初の一つを見つけることしかできません。たとえばユーザが１つか２つだけ数字を入力した場合です。しかしもしソルバーが反対方向からもう一度解を探した場合はどうでしょう？つまり左から右へ解を探した後、右から左へ解を探索します。

そして２つの解を比較して同一の解ならば、２つの解が「まんなかで出会った」ということで、解が唯一であるといえます。 つまりユーザが入力しおわったということになります。そうでないばあい、まだ入力中であるということです。

コンピュータはキー入力される毎にこれらの処理を一瞬で行います。

Translated by Hiroki Mori