数独の問題を解決するために、Java でバックトラッキング アルゴリズムを実装しようとしています。
問題が解決方法にあることは 95% 確信していますが、念のため 2 つのアクセサリ メソッドを含めました。
私がやっている奇妙なことのいくつかは、パズルのハードコードされた初期値のように、要件/利便性のためです。問題は解決方法の下部にあると確信していますが、理解できません...
私の現在の問題は次のとおりです。最初の行で作業し、潜在的に有効な値の順列を見つけた後、私のプログラムは単にあきらめます。「ROW IS DONE」を出力する行のコメントを外すと、1行後にそれが出力され、それ以上の出力は提供されません。なぜ最初の行の後にあきらめているのですか? 私の実装について他に心配すべきことはありますか
編集：私は多くの変更を加えました。それは非常に近づいています。EXHAUST が true のときに出力すると、最後の行を除くすべての行が解かれたパズルが得られます。解決した後、またはほぼ解決した後、すべてを元に戻しているようです。パズルが完全に解決されるポイントにすでに到達している可能性があると感じていますが、適切なタイミングで TRUE を返していません...何が間違っていますか?
import java.util.ArrayList;
class Model
{
ArrayList<View> views = new ArrayList<View>();
int[][] grid =
{
{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
/**
* Method solve
*
* Uses a backtracking algorithm to solve the puzzle.
*/
public boolean solve(int row, int col) //mutator
{
if(exhaust(row,col)) {printGrid(); return true;}
int rownext = row;
int colnext = col+1;
if(colnext>8)
{
colnext = 0;
rownext++;
}
if(grid[row][col] != 0) solve(rownext,colnext);
else //is == 0
{
for(int num = 1; num <= 9; num++)
{
if(!conflict(row,col,num)) //try a non-conflicting number
{
grid[row][col] = num;
if(solve(rownext,colnext)) return true;
grid[row][col] = 0;
}
}
}
return false;
}
/**
* Method exhaust
*
* Iteratively searches the rest of the puzzle for empty space
* using the parameters as the starting point.
*
* @return true if no 0's are found
* @return false if a 0 is found
*/
public boolean exhaust(int row, int col)
{
for(int i = row; i <= 8; i++)
{
for(int j = col; j <= 8; j++)
{
if(grid[i][j] == 0) return false;
}
}
System.out.printf("Exhausted.\n");
return true;
}
/**
* Method conflict
*
* Checks if the choice in question is valid by looking to see
* if the choice has already been made in the same row or col,
* or block.
*
* @return true if there IS a conflict
* @return false if there is NOT a conflict
*/
public boolean conflict(int row, int col, int num)
{
for(int j = 0; j <= 8; j++)
{
if(grid[row][j] == num) {
return true;
}
}
for(int i = 0; i <= 8; i++)
{
if(grid[i][col] == num) {
return true;
}
}
int rowstart = 0;
if(row>=3) rowstart = 3;
if(row>=6) rowstart = 6;
int colstart = 0;
if(col>=3) colstart = 3;
if(col>=6) colstart = 6;
for(int r = rowstart; r <= (rowstart + 2); r++)
{
for(int c = colstart; c <= (colstart + 2); c++)
{
if(grid[r][c] == num) {
return true;
}
}
}
return false;
}
}