爲什麼數獨求解器的這種遞歸方法繼續旋轉？

Question

在一個學校任務中​​，我們應該做一個soduko求解器。我有一個遞歸方法可以幫助我解決soduko難題。它是這樣的：

public void setNumber() { 

if (getNext() == null) { 

    for (int i = 1; i < 10; i++) { 
    if (acceptValue(i)) { 
     value = i; 
    } 
    } 
    board.stopRec(); 
    return; 

} else { 


    if(predefined()) { // if the square allready has a number 
    getNext().setNumber(); 
    } else { // find value for undefined square 

    for (int i = 1; i < 10; i++) { 
     if (acceptValue(i)) { 
     value = i // Does the Row class take notice of this? 
     getNext().setNumber(); 
     } 
    } 
    /* no value was assigned */ 
    value = -1; 

    } 

} 

} 

董事會類有一個方法initGrid，創建所有的廣場和使用nextSquare參考Row類的

class Board { 

[...] 

public void initGrid(int nSquaresBoxRowCol, int nRowsBox, int nColsBox, int[][] values) { 

[...] 

/* Create the rows, columns and squares */ 
Square prev = null; 
for (int row = 1; row <= nRowsBoard; row++) { 

    //Row r = new Row(row, squares[row-1]); 
    Row r = new Row(row); 
    rows[row-1] = r; 

    for (int col = 1; col <= nColsBoard; col++) { 
    if (row == 1) { 
     Column c = new Column(col); 
    } 

    Square current = new Square(row, col, Math.ceil((float)row/(float)nRowsBox), Math.ceil((float)col/(float)nColsBox), values[row-1][col-1], r, this); 

    if (!((row-1) == 0 && (col-1) == 0)) { 
     prev.nextSquare = current; 
    } 

    prev = current; 
    squares[row-1][col-1] = current; 

    r.addSquare(current); 

    /* Fill the boxes with squares */ 
    boxes[(int)(Math.ceil((float)row/(float)nRowsBox)) - 1][(int)(Math.ceil((float)col/(float)nColsBox)) - 1].addSquare(squares[row-1][col-1]); 
    nSquares++; 

    } 

} // END for (int row ... 

對象將它們鏈接在一起有望保持方形物體添加到Board類中的initGrid方法中。

class Row { 
int id; 

Square[] squares; 
ArrayList<Square> squareList; 

Row(int id) { 
this.id = id; // not currently used for anything 
squareList = new ArrayList<Square>(); 
} 

boolean checkValue(int val) { 
System.out.println("Checking values for row " + id);  
Iterator<Square> iter = squareList.iterator(); 
while(iter.hasNext()) { 
    System.out.println("Value (boolean checkValue() in Row): " + iter.next().value); 
    if (iter.next().value == val) { 
    System.out.println("returned false"); 
    return false; 
    } 
} 
return true; 

} 

public void addSquare(Square s) { 
squareList.add(s); 
System.out.println("class Row, method addSquare: Square with value " + s.value + " added to row."); 
} 

}

---

關於半遞歸方法

的方法是類方形的內部，所有的平方被組裝在二維陣列。該方法假設爲數獨板上的每個方塊調用它自己。所有的正方形都有一個Square nextSquare指針，指向方塊[] []中的下一個正方形。 getNext（）返回nextSquare。

acceptValue（i）檢查Squares'Row是否存在帶有i值的Square對象，如果不存在則返回true（Row有一個方形[]，其正方形分配給它從董事會）

我真的認爲這會做的伎倆，但復發只是繼續旋轉。

我能想到的唯一的事情是，Row-object中的方格可能沒有在遞歸中進行值更新，並且這可能會導致遞歸方法永遠持續下去。但我仍然不明白爲什麼這會有意義，它應該根據數獨規則給我錯誤的價值。

請告知我是否應該包含任何更多的代碼。

任何建議，非常感謝。謝謝。

Answer 1

好一件事，如果你所有的其他代碼按預期工作和acceptValue(i)會真的選擇正確每次，那麼你會希望後一回你的getNext().setNumber();

喜歡的東西

for(i=1;i<10;i++){ 
    if(acceptValue(i)){ 
     value = i; 
     getNext().setNumber(); 
     return; 
    } 
} 

否則，如果您的代碼選擇2作爲setNumber()返回時的值，將嘗試3,4,5 ......等等。