数独を最短で完全な解を導くアルゴリズム （Java）

Question

現在Javaで数独のコーディングを行っています。
数独を最短で、完全に解くことのできるコーディングを目指しております。

自分の中で考えるロジックは以下の通りです。

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

実際このコードは完成したのですが、問題が複雑になるにつれ、解答しきれないものが出てくることに気が付きました。

この対策として、
２、背理法を用いる。
消去法⇔背理法をすべてのマスが埋まるまで、繰り返す。

この方法を用いれば、ある程度の数独は解けると考えております。
しかしながら、そのロジック（フローチャート）が実際に、コードに起こすことができず行き詰っています。

また、現在はこれが最速だと、思い込んでいますが、ほかのアルゴリズムのほうが、いいのでは？というものがあれば教えていただければ幸いです。

実際のコードはこちらです。
以前似たような質問を行っておりますが、そちらからは数個修正させていただいているので記載させていただきます。

public class sudoku {
	static int[][] data = {
			{0,9,0,0,0,0,0,0,8},
	        {5,0,6,4,0,9,3,0,1},
	        {0,7,0,1,0,0,0,0,0},
	        {3,5,0,0,0,2,7,0,0},
	        {0,0,0,3,0,0,0,0,0},
	        {0,1,0,7,0,0,0,0,9},
	        {0,8,0,5,0,0,0,0,4},
	        {0,0,0,0,0,0,0,0,0},
	        {0,4,7,0,0,6,9,0,0}};
	
	public static void main(String[] args) {
		Sub.print(data);
		Sub.solve(data, data);
	    Sub.print(data);
		}
}

public class Sub extends sudoku {
	
	public static void print(int[][] data) {
		for(int i = 0; i < 9; i++) {
			for(int j = 0; j < 9; j++) {
				if(data[i][j] != 0) {
					System.out.print(" " + data[i][j] + " ");
				} else {
					System.out.print("( )");
				}
			}
			System.out.println();
		}
		System.out.println("---------------------------");
	}
	
	public static void solve(int[][]data, int[][] field) {
		boolean tf = false;
		do {
			check(data);
			if(field == data) {
				//背理法を用いたメソッドを作成
　　　　　　　　　　//ここでコーディング方法がわからずに困っています
				check2(data);
			}
			print(data);
			int count = 0;
			for(int r = 0; r < 9; r++)
				for(int c = 0; c < 9; c++) {
					if(data[r][c] != 0)
						count++;
				}
			if(count == 81)
				tf = true;
		} while(!(tf));
	}

//消去法を行うメソッド
	public static void check(int[][]data) {
		int[][] field = data;
		
		for(int r = 0; r < 9; r++)
			for(int c = 0; c < 9; c++) {
				int[] num = {0,0,0,0,0,0,0,0,0};
				if(data[r][c] == 0) {
					int count = 0;
					int key = 0;
					int sr = r / 3;
					int sc = c / 3;
					for(int i = 0; i < 9; i++) {//列
						if(data[r][i] != 0)
							num[data[r][i] -1] = 1;
					}
					for(int i = 0; i < 9; i++) {//行
						if(data[i][c] != 0)
							num[data[i][c] -1] = 1;
					}
					for(int s = 3 * sr; s < 3 * sr + 3; s++) {//ブロック
						for(int b = 3 * sc; b < 3 * sc + 3; b++) {
							if(data[s][b] != 0)
								num[data[s][b] -1] = 1;
					       }
					}
					for(int a = 0; a < 9 ; a++) {
						if(num[a] == 1)
							count++;
						else
							key = a + 1;
					}
					if(count == 8) {
						field[r][c] = key;
						solve(data, field);
					}
				}
			}
	}

Comments

[mather]

当人の中では「背理法」が自明なのかもしれませんが、具体的に一手一手の手法を書き出してみましょう。
それができればコードもかけるはずです。
質問は再編集できますので、書き出してみてもわからないというときは質問に追記してみてください。

[ozwk]

前の質問でも貼ったこれ;
http://www.aoky.net/articles/peter_norvig/sudoku.htm
は読まれましたか?

[anpan___]

matherさん
かしこまりました！
一度自分なりに考えたコードをもう一度手直しし、記載させていただきます！

[anpan___]

ozwkさん
はい！そちらの記事を閲覧し、また他のサイトからも情報を得て
提示いただいたサイトの内部の「探索」が、「背理法」であると分かりました。

[coco_bauer]

「最速」という事を考えないで、必ず政界に到達する方法を考えましょう。動的計画法で扱うような問題は、上のほうから調べ始めたほうが早く解ける問題、下のほうから調べ始めたほうが早く解ける問題、、というように同じアルゴリズムで使って解いても、回答に至るコスト(時間)は問題に依存します（そして、解いてみないと、どこから手掛けるのが最適なのかは分からない）。

[anpan___]

coco_bauerさん
なるほど！速度はスタート位置でも変わりますね！頭に入っていませんでした。
まず確実に正解することが、確かにベストな答えです。
上記を完成させて確実に、正しい回答のできるものを意識してコーディングします。

Answer 1

その方法では、ごく簡単なものしか解けないんじゃないでしょうか？
私なら動的計画法を考えます。

まずすべてのマスについて、そこに入れることが可能な数字のリストを作成します。入れることが可能な数字が一つだけなら、それは正解として確定します。

次に、候補の数が最も少ないマスの中から一つ選び、リスト中から一つ選んで入れてみます。これを正解と仮定した上で他のマスのリストを作り直します。すべての数値が確定しなかった場合、この候補は正解と仮定したまま他のマスを選んで同様の処理を行います。これを再帰的に行い、破綻したところでバックトラックを行います。そして、すべてのマスが確定したところで終了します。

Comments

[anpan___]

丁寧にありがとうございます。

APIを用いないように努めておりますので、配列等使って一度そちらの考えを再現させる努力を行います！
ありがとうございます。

[Zuishin]

API は無関係ですね。動的計画法を調べてみてください。ozwk さんが貼られているリンク先でも使われています。

[ozwk]

質問者さんは
確定できるところは確定させ(質問者は消去法と表現)し
できなくなったら適当なマスに対して探索を行う(質問者は背理法と表現)
という方針を考えているようなので、言っていることが結局一緒ではないでしょうか

[Zuishin]

私は前の質問を読んでいなかったので、背理法が何を意味するかわかりませんでしたが、それは私の知っている背理法とは違うようです。

[Zuishin]

背理法は、ある命題が偽であると仮定したときに生じる矛盾をもってその命題が真であることを証明するものという認識です。つまり、あるマスが 1 であることを証明するためには、そのマスは 1 ではないと仮定しなければいけません。

[coco_bauer]

「やってみて、破綻したら、バックトラックして別解を求めてゆく」という動的計画法での解法を質問者が意図していたことを、質問の文章から判断することは無理じゃないでしょうか。

Answer 2

根本的な所なんですけど、プログラムを書く前に
解き方を徹底的に洗ったほうが良い気がします。
候補が複数あっても、埋められる事もありますし。

---

例）
１２３|○○○|７８●
○○○|○○○|○○○
○○○|○９○|○○○

●は４５６９が候補ですが、
９は左のマスの２段目のいずれかに入る為、
右のマスの２段目には９が入れられません。
よって９で確定します。

---

やってみないとな所はありますが、
総当りを減らすことにより、スピードアップに繋がるのではないでしょうか。

Answer 3

パズル作家です。私は速さのところだけ 反応しますね。

まずjavaでは最速のものは作れないのではないかと思います。
＃とりあえず C か Rust か delphi(一部マシン語)ぐらいですかね。

さらに、本当に速さを求めるなら、
メモリを動的に確保する方法は諦めましょう。

ではどうするか。なぜこのパズルが存在するのか、という点に
立ち返ればいいのです。そうすれば人間がそれを楽しめなくては
意味がない、ことが分かるでしょう。

つまり、人間が解けることを前提として作られている、
あるいは そういう理念で作られたと判断されたものだけが
数独のパズルとして出来するのであって、
そうであれば、人間が用いる いくつかの「解法」を
静的に実施するようインプリメントすればいいだけなのです。

そしてそれらは常に、人間が把握できるレベルのわずかな
メモリしか必要とせず、静的に持っておける範囲に収まります。

きちんと数独の解法を整理すれば、アルゴリズム的には
6,7つほどを実装すれば、ニコリ社さんの出版されている
全ての数独が静的に解けることが分かるでしょう。

あとはbit演算などに落とし込めば 速さを追求することには
もはや興味を失う(※)というレベルまで速くすることができます。

※なぜなら問題を読み込む ファイル I/O のほうがはるかに時間がかかるから。