在此應用程序中遇到遞歸問題

我正在爲Sudoku拼圖編寫一個遞歸求解器。我用0存儲空白的地方，以便我的程序可以更輕鬆地讀取它們。我有從下標1開始存儲的原始拼圖，以更好地可視化網格。我不確定我對遞歸有充分的把握，那就是問題所在。我得到的輸出似乎正在解決這個難題，但它在那裏留下的不應該在那裏的零。我認爲這與放置unsetSquare或返回語句有關。在此應用程序中遇到遞歸問題

下面是輸出的一個樣本...

************************************************** 
7 4 3 | 8 2 1 | 5 6 8 
2 6 8 | 0 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 9 
2 6 8 | 0 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 1 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 2 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
************************************************** 
************************************************** 
7 4 3 | 8 2 1 | 5 6 0 
2 6 8 | 3 9 0 | 0 1 0 
0 0 0 | 0 0 6 | 0 0 4 
---------|---------|--------- 
0 0 0 | 0 0 0 | 2 3 9 
0 0 0 | 0 0 0 | 0 0 0 
4 1 5 | 0 0 0 | 0 0 0 
---------|---------|--------- 
9 0 0 | 5 0 0 | 0 0 0 
0 2 0 | 0 1 0 | 7 4 0 
0 0 0 | 2 0 0 | 9 0 5 
**************************************************

通知在第一行的末尾，它進入8尋找一個解決方案，然後到9,9是不合法的，它有達到for循環的結尾，所以它用零代替它，並繼續。我怎樣才能讓它回到第一行嘗試不同的數字來獲得更完整的解決方案？

這裏是我的遞歸函數...

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    for(int i = ONE; i <= NINE; ++i){ 
     for(int j = ONE; j <= NINE; ++j){ 
      if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){ 
       cout << i << "  " << j << endl; 
       return true; 
      } 
      //cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
      if(board.getSquare(i, j) == ZERO){ 
       //cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
       for(int k = ONE; k <= NINE; ++k){ 
        board.setSquare(i, j, k); 
        board.display(outStream); 
        if(board.isLegal()){ 
         return addSquare(depth, outStream); 
        } 
        else{ 
         board.unsetSquare(i, j); 

        } 
       } 
      } 

     } 
    } 
    board.display(outStream); 
    return false; 
}

來源

2013-10-29 Trevor Hutto

你真的認爲我們爲你調試了代碼嗎？也許你可以創建一個更小的案例，顯示相同的問題。 – Walter

這是一樣小。這是一個功能......就像15行代碼。 –

你應該在addSquare（depth，outStream）後刪除返回true;並使其返回addSquare（深度，outStream）;代替。雖然這不能解決你的問題。 – drescherjm

事實證明，我有出頭順序錯誤，而不是在合適的範圍內。在用while循環成功完成之後，我找到了帶for循環的解決方案。

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    for(int i = 1; i < 10; ++i){ 
     for(int j = 1; j < 10; ++j){ 
      if(board.getSquare(i, j) == 0){ 
       if(i == 10){ 
        return true; 
       } 
       for(int k = 1; k <= 9; ++k){ 
        board.setSquare(i, j, k); 
        if(board.isLegal() && addSquare(depth, outStream)){ 
         return true; 
        } 

       } 
       board.unsetSquare(i, j); 
       return false; 

      } 
     } 
    } 
}

來源

2013-10-30 03:41:05

我可以看到一個問題：

它應該是：

if(board.isLegal()){ 
    if(addSquare(depth, outStream)) 
     return true; 
}

意味着如果整個董事會解決，然後回滾。

編輯想一想：

你把1中的第一方陣，則返回false。你不想嘗試把2？

EDIT2 更多問題：

if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){ 
      cout << i << "  " << j << endl; 
      return true; 
}

這是假設是一個完成檢查？你只檢查1平方米。並在您的示例中填充！你需要檢查有沒有0

EDIT3：

bool DoTheWork::addSquare(int& depth, ostream& outStream){ 
    //use flag to let you know if all completed 
    bool zeroFound = false; 
    for(int i = ONE; i <= NINE; ++i){ 
    for(int j = ONE; j <= NINE; ++j){ 
     //cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
     if(board.getSquare(i, j) == ZERO){ 
     zeroFound = true; 
     //cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl; 
     for(int k = ONE; k <= NINE; ++k){ 
      board.setSquare(i, j, k); 
      board.display(outStream); 
      if(board.isLegal()){ 
      if(addSquare(depth, outStream)){ 
       return true; 
      } 
      else{ 
       board.unsetSquare(i, j); 
      } 
      } 
     } 
     } 
    } 
    } 
    board.display(outStream); 
    return !zeroFound; //true in case it is full! 
}

來源

2013-10-29 22:08:58 SHR

我試過了，它沒有解決問題。我相信@drescherjm提供的是相同的答案，但語法不同。 –

如果發生錯誤，你不想返回，你想移動到下一個值。 – SHR

哦，我明白了，但是它仍然沒有擺脫輸出中殘留的零點。 –

在此應用程序中遇到遞歸問題

回答

相關問題