數獨解算器回溯

我正在瀏覽一些數獨求解器，我正在尋找一種利用回溯的方法，現在我已經找到了這個代碼，但我不確定它是使用回溯還是其他算法？數獨解算器回溯

幫助表示讚賞。

abstract class SudoKiller { 
private SudokuBoard sb; // Puzzle to solve; 

public SudoKiller(SudokuBoard sb) { 
    this.sb = sb; 
} 


private boolean check(int num, int row, int col) { 
    int r = (row/sb.box_size) * sb.box_size; 
    int c = (col/sb.box_size) * sb.box_size; 

    for (int i = 0; i < sb.size; i++) { 
     if (sb.getCell(row, i) == num || 
      sb.getCell(i, col) == num || 
      sb.getCell(r + (i % sb.box_size), c + (i/sb.box_size)) == num) { 
      return false; 
     } 
    } 
    return true; 
} 


public boolean guess(int row, int col) { 
    int nextCol = (col + 1) % sb.size; 
    int nextRow = (nextCol == 0) ? row + 1 : row; 

    try { 
     if (sb.getCell(row, col) != sb.EMPTY) 
      return guess(nextRow, nextCol); 
    } 
    catch (ArrayIndexOutOfBoundsException e) { 
      return true; 
    } 

    for (int i = 1; i <= sb.size; i++) { 
     if (check(i, row, col)) { 
      sb.setCell(i, row, col); 
      if (guess(nextRow, nextCol)) { 
       return true; 
      } 
     } 
    } 
    sb.setCell(sb.EMPTY, row, col); 
    return false; 
} 
}

如果這不是回溯，有沒有簡單的方法來「轉換」它？

整個項目可在the authors site上找到。

來源

2013-02-17 Bob Smith

你看着回溯的定義是什麼？ – Michael 2013-02-17 16:36:53

看起來像它通過遞歸回溯。

在這裏，我們邁出第一步：

sb.setCell(i, row, col);

在這裏，我們後退一步：

sb.setCell(sb.EMPTY, row, col);

來源

2013-02-17 16:36:29

你怎麼看到它是一個回溯算法？還有一種方法可以添加延遲，以便我可以實時看到回溯（正好發生）。 – 2013-02-17 16:40:22

@BobSmith在答案中增加了更多細節。 – 2013-02-17 17:05:02

數獨解算器回溯

回答

相關問題