麻煩理解遞歸如何與這個數獨求解器一起工作

我一直在看這個代碼塊幾個小時了，我不知道它是如何工作的。有人可以請詳細解釋遞歸如何與這些函數一起工作嗎？請記住，我在編程方面非常新穎。麻煩理解遞歸如何與這個數獨求解器一起工作

讓我最困惑的部分是solve（）如何反覆調用？難道它會在達到謎題後停止[row] [col] = 0？

這是工作代碼的方式。

編輯：謝謝你的回答！但我不知道它在哪裏回溯。

void solve(int row, int col) throws Exception 
{ 
    if(row > 8) 
    { 
     throw new Exception("Solution found") ; 
    } 

    if(puzzle[row][col] != 0) 
    { 
     next(row, col); 
    } 
    else 
    { 
     for(int num = 1; num < 10; num++) 
     { 
      if(checkHorizontal(row,num) && checkVertical(col,num) && checkBox(row,col,num)) 
      { 
       puzzle[row][col] = num ; 
       next(row, col) ; 
      } 
     } 
     puzzle[row][col] = 0 ; 
    } 
} 

public void next(int row, int col) throws Exception 
{ 
     if(col < 8) 
     { 
      solve(row, col + 1) ; 
     } 
     else 
     { 
      solve(row + 1, 0) ; 
     } 

}

來源

2014-02-07 Natsu

的next函數可以描述爲發現的第一個自由場，並從該字段開始求解過程的功能。

實際的遞歸是一個簡單的回溯（http://en.wikipedia.org/wiki/Backtracking）。總體方案可能會更容易一些僞把握：

Solution findSolution(Board board) { 
    if (board.isSolved()) return solutionFor(board); 


    // An "action" here refers to placing any number 
    // on any free field 
    for (each possible action) { 

     do the action // That is: place a number on a free field 

     // The recursion: 
     Solution solution = findSolution(board); 
     if (solution != null) return solution; 

     // No solution found 
     UNdo the action // That is: remove the number from the field 

     // Now the loop continues, and tries the 
     // next action... 
    } 

    // Tried all possible actions, none did lead to a solution 
    return null; 
}

通常情況下，一個將決定這些「行動」有兩個嵌套的for循環：

for (each free field f) 
{ 
    for (each number n in 1..9) 
    { 
     place 'n' on 'f' 
     try to find solution 
     remove 'n' from 'f' 
    } 
}

外環在這種情況下有些「隱藏」在next函數中。

在這種情況下，對於數獨，這種回溯的特定實現可能不會很好。它可能需要幾萬億年才能找到解決方案，因爲這種可能性非常多。但是這主要取決於如何實施「巧妙」的方法。快速檢測（部分）解決方案已無效的情況很重要。也就是說，您是否遇到過無法找到解決方案的情況。例如，當一個3x3-sqares的兩個單元格包含相同數字時，情況已經「無效」。例如，這可以通過顯式存儲仍然可用的數字來避免，但是當然，代碼會變得更加複雜。

來源

2014-02-07 13:37:03 Marco13

麻煩理解遞歸如何與這個數獨求解器一起工作

回答

相關問題