アルゴリズムの設計

ナンプレ解法のアルゴリズム

私自身、ナンプレに関してはかなり難問でも解くことができる。私の考えを図にまとめてそのまま実装するのも良い。しかし考え方に抜けがあったり、世間一般の解法を私の解法があまりに離れていると、私の考える難易度と、世間一般の難易度と違いが出てしまい、「人間らしく解く」が「私らしく解く」になってしまう。これでは自己満足の世界に終始してしまう。そこで、インターネットで調査することにした。

検索の結果

ここに多種多様な解法テクニックが記載されていた。
http://sudopedia.enjoysudoku.com/Solving_Technique.html
おそらくすべてを愚直に実装しなくても、ナンプレを解くことはできると思われるが、自分の勉強の意味もあるので、今回は全てを実装してみようと思う。

アルゴリズムのアレンジは?

基本しない方向で考えている。勉強の意味もあるが、先に記載したサイトの用語は、他のサイトでも用いられているため、ナンプレのアルゴリズムを調べている方々にとって判りやすいと思った。また自分が英語の翻訳やアルゴリズムの実装で詰まった場合に、キーワードになり得るので、後々楽かも知れない。

紹介していたサイトが閉鎖したら?

可能性はゼロではない。というか上記サイトも既にミラーサイトであるので危険はある。今回のナンプレを解くプログラムを作成するにあたっては、特にバックアップを取ったりはしない。もし閉鎖されたら、そこからは「人間らしく解く」が「私らしく解く」に変わるかもしれない。

アルゴリズムを説明するまえに

申し訳ないが、本サイトではナンプレのルールの説明は特にしない。ルールを知りたければwikipedia等を参照いただきたい(wikipedia:https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC)。蛇足だが、このページによると、ナンプレ自動作成プログラムを6年かけて作成した方がいるようである。私の開発はそこまで長くなることを想定していないが、ひょっとしたら私が考えていないような技術的な壁があるのかも知れない。こればかりは実装してみないと何とも言えない。

次回からアルゴリズムとプログラムの実装に入るが、私のプログラムではGlobal変数として
・oriSQR[9][9] → 与えられた問題を記憶している配列。
・ansSQR[9][9] → 解いている途中経過を記憶している配列。
・chkSQR[9][9][9] → 解いている途中経過で、各マスに入る候補を記憶している配列。
としている。変数の詳細については後日説明する。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です