数独解算器回溯

我正在浏览一些数独求解器，我正在寻找一种利用回溯的方法，现在我已经找到了这个代码，但我不确定它是使用回溯还是其他算法？数独解算器回溯

帮助表示赞赏。

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

数独解算器回溯

回答

相关问题