我決定爲我的Sudoku應用程序編寫一個邏輯求解算法。我寫的內容適用於有限數量的網格值,但遞歸過快停止。Sudoku的邏輯求解算法(Java)
我的方法: addToThirdDimension():三維數組存儲可以放入邏輯網格值logicGrid [x] [y]的所有可能值。該方法刷新三維數組。它通過在每個網格索引中測試值1-9來完成此操作,並且如果它有效,則會將該數字添加到數組中。如果不是,則將該值設置爲零。
checkValues():檢查三維網格中剩餘多少可能性。它通過logicGrid並返回網格中非零值的數量。 (int row,int col):檢查logicGrid [row] [col]以查看是否有一個值只剩下一個值(如果剩下一個值,則它是網格的唯一可能性)元素在[row,col])。它返回該網格位置中的非零值的數量。
getSingleValue(INT行,INT COL):返回剩下在logicGrid [行] [山口]
immutableValues單號:A二維布爾數組,存儲是否一個特定的柵格元件是不可變的或不。如果它是不可變的,解決方法不應該碰它。
public boolean solveWithLogic(){
addToThirdDimension();
if(checkValues() == 0){
return true;
}
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
if(!immutableValues[row][col]){
if(checkSingleValue(row, col) == 1){
sGrid[row][col] = getSingleValue(row, col);
setValues[row][col] = true;
addToThirdDimension();
}
}
}
}
if(checkValues() != 0){
solveWithLogic();
} else{
return true;
}
return false;
}
我看不到我要去哪裏錯了。經過一定次數的嘗試後,即使應該有更多的可能性,checkValues也會返回0。這裏是addToThirdDimension()的代碼,因爲我確信如果出現問題,它就在這裏。
sGrid是存儲拼圖值的主要二維整數數組。
public void addToThirdDimension(){
logicGrid = new int[9][9][9];
for(int x = 0; x < 9; x++){
for(int y = 0; y < 9; y++){
for(int z = 0; z < 9; z++){
logicGrid[x][y][z] = z + 1;
}
}
}
int[][] temp1 = sGrid;
for(int row = 0; row < 9; row++){
for(int col = 0; col < 9; col++){
if(setValues[row][col]){
for(int i = 0; i < 9; i++){
logicGrid[row][col][i] = 0;
}
} else{
for(int i = 1; i <= 9; i++){
temp1[row][col] = i;
if(!isColumnValid(col, temp1) && !isRowValid(row, temp1) &&
!isQuadrantValid(row, col, temp1){
logicGrid[row][col][i-1] = 0;
}
}
}
temp1[row][col] = sGrid[row][col];
}
}
}
該代碼目前效率不高。在開始最小化解決時間之前,我想讓它工作。
您可能想要在CodeReview上發帖:http://codereview.stackexchange.com/ – DJClayworth 2011-02-25 21:56:59
我不太瞭解java,所以我有一個問題。在行'int [] [] temp1 = sGrid;'''temp1'是'sGrid'的一個克隆或者只是一個對它的引用? – Dialecticus 2011-02-26 09:51:22