2011-02-25 72 views
0

我決定爲我的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]; 
     } 
    } 
} 

該代碼目前效率不高。在開始最小化解決時間之前,我想讓它工作。

+0

您可能想要在CodeReview上發帖:http://codereview.stackexchange.com/ – DJClayworth 2011-02-25 21:56:59

+0

我不太瞭解java,所以我有一個問題。在行'int [] [] temp1 = sGrid;'''temp1'是'sGrid'的一個克隆或者只是一個對它的引用? – Dialecticus 2011-02-26 09:51:22

回答

2

我會做的第一件事就是創建一個SudukoCell對象,其中存儲了可能的值。然後創建一個帶有SudukoCells二維陣列的SudukoBoard。也給它一系列SudukoAreas。一個區域爲行,一個區域爲cols,一個區域爲塊。

適當添加您的suduko細胞。

這將幫助您鞏固您的拼搏並防止愚蠢的錯誤。

然後每次你解決一個數字,你可以去每個區域的單元格,並刪除你從他們解決的數字。

+0

我會嘗試重寫我的代碼以適合您的模型。同時,你是否看到我出錯的地方?或者是我的代碼的全面實現完全錯誤? – SkylineAddict 2011-02-25 22:14:07