Java 数独 消去法

Question

前提・実現したいこと

今、javaでナンプレ(数独)を解くプログラムを作っています。バックトラッキングなどの方法で解くことはできます。そこで、別の方法で解いてみたいなと考え、消去法で解くようなプログラムを作りました。

(消去法)
一つのセルに対し、３×3のブロック、行、列の数字を確認し、8種類の値があれば残りの一種類を代入する。

この方法だけ解くと、数独で解ける問題と解けない問題が存在することがわかりました。むしろ解けない問題の方が多かったです。作る前はこの方法で解ける!と思っていたのですが、考えてみれば解けないやつもある。。。。
そこで、主軸は消去法で、他の方法(バックトラッキング以外)を追加して、解く方法(アルゴリズム)を教えてください。

Comments

[shiketa]

> 解く方法(アルゴリズム)を教えてください。

そこを考えるから、プログラミングって愉しいんじゃないですか。一番の醍醐味を捨てるなんて勿体無い。

Answer 1

お疲れ様です。

私も紙とペンの補助として、Excelを使いながら消去法でチャレンジしてみても、ある程度難しいものは消去法だけでは解けません。

その升に入力できる値を仮においてみるということが必要になります。
将棋のように相当先まで読む力があれば解くことができると思いますが、私には無理です。

数独の解き方というサイトがいろいろありますので、参考にするとよいと思います。
最終的には消去法で解けないものは、力技(バックトラッキング法など)かなと思います。

Comments

[purogutamu]

なるほど仮置きでやってみます。ありがとうございます。