数独を総当たりで解く方法が分からない

Question

前提・実現したいこと

数独を総当たりで解くロジックの製作途中で無限ループになってしまいます。
ここでは文字数制限で載せれませんが、候補数字が一つのマスを埋めてから総当たりを行うように作っています。

発生している問題・エラーメッセージ

このソース内で無限ループになってしまいます。

for(int row = 0; row < data.length; row++) {
			for(int col = 0; col < data.length; col++) {


				outside:if(data[row][col].equals("0")) {
					for(int number = 1; number <= 9; number++) {
						strNumber = String.valueOf(number);
						if(isCandidate(row,col,strNumber) == true) {
							setNumber(row,col,strNumber);
							break;
						}else if(number == 9){
							Masu(row,col);
							row = y;
							col = x;
							break outside;

該当のソースコード

SudokuQuestion0.csv

x,x,3,9,x,x,7,6,x
x,4,x,x,x,6,x,x,9
6,x,x,x,1,x,x,x,4
2,x,x,6,7,x,x,9,x
x,x,4,3,x,5,6,x,x
x,1,x,x,4,9,x,x,7
7,x,x,x,9,x,2,x,1
3,x,x,2,x,x,x,4,x
x,2,9,x,x,8,5,x,x

package sudoku;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class First_solve
 */
public class SudokuServlet extends HttpServlet {
	private static final long serialVersionUID = 1L;

	public static final Integer ncol = 9;    /*Const. row and col*/
	public static final Integer sqncol = 3;  /*Const. 3x3 row and col*/

	public String[][] data = new String[ncol][ncol];  //表データ全格納二次元配列
	public String[][] Fdata = new String[ncol][ncol];
	public boolean[][][] Candidate = new boolean [ncol][ncol][ncol + 1];  //数字に対しての有効かどうかがbooleanで格納されている
	public int x = 0;
	public int y = 0;

    /**
     * @see HttpServlet#HttpServlet()
     */
    public SudokuServlet() {
        super();
    }

	/**
	 * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse response)
	 */
	protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
		// TODO Auto-generated method stub
		response.setContentType("text/html; charset=UTF-8");
		PrintWriter out = response.getWriter();


/*
 *******************************
 * 			問題表示領域
 *******************************
 */
		int check = 0;
		 try {
			 //ファイル読み込みと表示
		      File f = new File("C:\KENSHU\pleiades\workspace\Sudoku\src\sudoku\SudokuQuestion0.csv");
		      BufferedReader br = new BufferedReader(new FileReader(f));
		      String line = br.readLine();

		      for (int row = 0; line != null; row++) {
		        data[row] = line.split(",", 0);
		        Fdata[row] = line.split(",", 0);
		        line = br.readLine();
		      }
		      br.close();

		      // CSVから読み込んだ配列の中身を表示
		      out.println("<table border = 1");
		      out.println("<p>" + "****************** 問題 ******************" + "</p>");
			  for(int row = 0; row < data.length; row++) {
				  for(int col = 0; col < data.length; col++) {
					if(data[row][col].equals("x")) {
						data[row][col] = "0";
						Fdata[row][col] = "0";
					}
				  }
			  }
		      for(int row = 0; row < data.length; row++) {
		    	  out.println("<tr>");
		        for(int col = 0; col < data.length; col++) {
		          out.println("<td style = width:30px;>" + data[row][col] + "</td>");
		        }
		        out.println("</tr>");
		      }
		      out.println("</table>");
		    } catch (IOException e) {
		    	out.println(e);
		    }
/*
 *************************************************
 * 					 メイン処理領域
 *************************************************
 */
		 boolean TF = false;

                        do{
			 check = 0;
			
			 Third_Solve();
			 for(int i = 0; i < ncol; i++) {
				 for(int j = 0; j < ncol; j++) {
					 if(data[i][j].equals("0")) { //そのマスが0じゃなかったら
						 check++;                    //カウンターに1を足す。
					 }
				 }
			 }
			 if(check == 0) {                       //全マスが埋まったら
				 TF = true;
			 }
                         }while(!TF)
                             //処理を終了する。


/*****************************************************
 *					 回答表示領域
 ****************************************************/



	out.println("<table border = 1");
    out.println("<p>" + "****************** 回答 ******************" + "</p>");
      for(int row = 0; row < data.length; row++) {
    	  out.println("<tr>");
    	  for(int col = 0; col < data.length; col++) {
    		  out.println("<td style = width:30px;>" + data[row][col] + "</td>");
    	  }
      out.println("</tr>");
      }
    out.println("</table>");

      Candidate = new boolean[ncol][ncol][ncol];


	}

/****************************************
 * 				ステップ3
 * **************************************
 *
 */
	public void Third_Solve() {
		System.out.println("call Third_Solve");
		String strNumber = null;

		for(int row = 0; row < data.length; row++) {
			for(int col = 0; col < data.length; col++) {


				outside:if(data[row][col].equals("0")) {
					for(int number = 1; number <= 9; number++) {
						strNumber = String.valueOf(number);
						if(isCandidate(row,col,strNumber) == true) {
							setNumber(row,col,strNumber);
							break;
						}else if(number == 9){
							Masu(row,col);
							row = y;
							col = x;
							break outside;
						}
					}
				}


			}
		}
	}


/*********************
 * 参照マス変更関数
 * *******************
 * @param i
 * @param j
 */


	public void Masu(int i, int j) {
		if(j == 0) {
			int k = i - 1;
			for(k = i - 1; k >= 0; k--) {
				for(int l = 8; l >= 0; l--) {
					if(Fdata[k][l].equals("0")) {
						y = k;
						x = l;
						break;
					}
				}
			}if(!(data[y][x].equals("9"))) {
				if(!(Fdata[y][x].equals("0"))) {
					i = i - 1;
				}
			}
		}else {
			for(int k = i; k >= 0; k--) {
				for(int l = j; l >= 0; l--) {
					if(Fdata[k][l].equals("0")) {
						y = k;
						x = l;
						break;
					}
				}
			}
			if(!(data[y][x].equals("9"))) {
				if(!(Fdata[y][x].equals("0"))) {
					i = i - 1;
				}
			}
		}
	}

	protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
		// TODO Auto-generated method stub
		doGet(request, response);
	}

}

Comments

[m.ts10806]

コードやエラーはマークダウンのcode機能を利用してご提示ください。
https://teratail.com/questions/238564

[y_waiwai]

このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[kusogomitan]

初めての質問でして、大変申し訳ございません。今修正しました。

[Daregada]

回答者がコードを試せるように、SudokuQuestion0.csvの内容も質問に追加してください。

[y_waiwai]

んで、どこのループで無限ループになるんでしょうか

[kusogomitan]

今修正いたしました。申し訳ございません。

[maisumakun]

無限ループになっていることはどのように確認しましたか？

（単に「全探索をやると範囲が膨大なのでなかなか終わらない」だけ、ということも考えられます）

[dodox86]

細かい指摘をしますと、質問をただ読むと、
質問の件名：「数独を総当たりで解く方法」→を、知りたい？それともコードがそうなっていて、それについてなにか問題？
質問の内容：「数独を総当たりで解くロジックが無限ループになってしまいます。」→　そうですか。
と言うかんじがします。

[kusogomitan]

対象のマスに対して1~9の数字が候補にならなかった場合に一つ前のマスを対象にする関数がMasuで、その返り値をfor文の条件に使ってしまっているのが原因かと思われます。

[kusogomitan]

dodox86さん
言葉足らずですみません。総当たりで解く方法は調べれば出てくるのですが、自分のソースに適応した形にする方法が分からず、質問させて頂きました。

Answer 1

ナンプレの総当たりは私も作ったことがありますが、その時に使ったのは単純にforを81個並べる方法です。

for(int i1=0;i1<9;i1++){
   for(int i2=0;i2<9;i2++){
      for(int i3=0;i3<9;i3++){
         \繰り返し
      }
   }
}

このようにしてもし空白ではなかった場合はその部分のforを飛ばして次のforに行き81回forが終了次第、それがあっているか調べるプログラムをはめ込む方法です。

※上のソースコードはそのままでは使えません。なぜなら空白があった時の処理が書いてないからです。時間がなくて細かく書けませんでした。すいません。