这个数独求解器是如何工作的？

我发现了一些解决数独谜题的代码，但我只理解它的一部分。这个数独求解器是如何工作的？

static boolean solve(int i, int j, int[][] cells) { 
    if (i == 9) { 
     i = 0; 
     if (++j == 9) 
      return true; 
    } 
    if (cells[i][j] != 0) // skip filled cells 
     return solve(i+1,j,cells); 

    for (int val = 1; val <= 9; ++val) { 
     if (legal(i,j,val,cells)) { 
      cells[i][j] = val; 
      if (solve(i+1,j,cells)) 
       return true; 
     } 
    } 
    cells[i][j] = 0; // reset on backtrack 
    return false; 
} 

static boolean legal(int i, int j, int val, int[][] cells) { 
    for (int k = 0; k < 9; ++k) // row 
     if (val == cells[k][j]) 
      return false; 

    for (int k = 0; k < 9; ++k) // col 
     if (val == cells[i][k]) 
      return false; 

    int boxRowOffset = (i/3)*3; 
    int boxColOffset = (j/3)*3; 
    for (int k = 0; k < 3; ++k) // box 
     for (int m = 0; m < 3; ++m) 
      if (val == cells[boxRowOffset+k][boxColOffset+m]) 
       return false; 

    return true; // no violations, so it's legal 
}

我明白法律（）方法，它只是检查不允许的重复。不太清楚的是solve（）中的递归如何完成它的工作。

任何人都可以提供有关该部分如何工作的见解。我真的很想理解它，所以我可以自己实现一个。

谢谢

来源

2011-11-30 jmasterx

你应该找到[这]（http://www.norvig.com/sudoku.html）非常有趣的 - 即使它是错误的语言:) – Voo

该算法使用递归和回溯，基本上它“蛮力”数独，直到找到正确的答案。

它将遍历数字1 - 9，直到找到一个当前合法的数字。当算法不在有效组合中时，该算法将回溯（即重置数字）数字。它会做每一列和行，直到它解决了整个难题。

来源

2011-11-30 00:43:46 Deco

感谢您指出，我知道我的意思，但写得很差:)我会更新 – Deco

它尝试每个插入此刻是合法的。
当然，只有其中一个会导致真正的解决方案，所以它会检查它们的真假。

不正确的尝试将在某处发生死角，并返回false。

来源

2011-11-30 00:39:59

在通俗地说，solve执行以下操作：

solve(position, field): 
    for all values of all positions: 
    fill current position of field with current value 
    solve(neighboring position, field) # solve 'the rest' 
    if field is a legal solution: 
     return field 
    else: 
     unfill current position of field 
    # the loop proceeds to next position

来源

2011-11-30 00:51:00 9000

这个数独求解器是如何工作的？

回答

相关问题