這個數獨求解器是如何工作的？

我發現了一些解決數獨謎題的代碼，但我只理解它的一部分。這個數獨求解器是如何工作的？

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

這個數獨求解器是如何工作的？

回答

相關問題