數獨遞歸回溯，無法過早

因此，我正在用C++編寫一個數獨求解器，並遇到了一個小問題。以下是我的解決板子代碼。它適用於謎題的前三行，但在第四行結束時不會反轉。看看gdb上的代碼，它會觸及第4行的末尾，回溯到第6列，然後嘗試，然後不會結束。數獨遞歸回溯，無法過早

關於代碼的一些其他說明是保持sudoku板開始在1,1不是0,0的矩陣。所以當solveBoard最初被調用時，參數是（1，1，0）。我還附加了setCell和checkConflicts函數，以獲取更多信息。我有三個向量rowConf，colConf和squConf來存儲已經放置在相應的行，列或方塊中的值。我一直在這裏待了好幾個小時，無法越過第三排。任何援助都非常適合。謝謝！

編輯：添加clearCell（）

bool board::solveBoard(int i, int j, int count) 
{ 

    if (j > 9) 
    { 
     j = 1; 
     i++; 

     printBoard(); 
     if (isSolved()) 
     { 
      printBoard(); 
      cout <<"The Board has been solved!" <<endl 
       <<" The number of recursive calls was: " <<count <<endl; 
      return true; 
     } 
    } 

    if (isBlank(i, j)) 
    { 
     for (int n = 1; n < 10; n++) 
     { 
      if (setCell(i, j, (char)n + '0')) 
      { 
       if (solveBoard(i, j + 1, count + 1)) 
       { 
        return true; 
       } 
       } 
      } 
     } 
     else 
     { 
      return (solveBoard(i, j + 1, count + 1)); 
     } 

     clearCell(i, j); 
     return false; 
} 

bool board::setCell(int i, int j, char val) 
{ 
    int intVal; 

    intVal = atoi(&val); 

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize && 
     intVal >= 1 && intVal <= BoardSize) 
    { 
     if (!(checkConflicts(intVal, i, j, squareNumber(i, j)))) 
     { 
     return false; 
     } 

     value[i][j] = intVal; 

     // Set flags of the conflicts 
     rowConf[i][intVal] = true; 
     colConf[j][intVal] = true; 
     squConf[squareNumber(i, j)][intVal] = true; 

     return true; 
    } 
    else 
    { 
     throw rangeError("bad value in setCell"); 
    } 
} 

bool board::checkConflicts(int val, int i, int j, int k) 
{ 
    if (i < 1 && i > BoardSize && j < 1 && j > BoardSize && 
     k < 1 && k > BoardSize && val < 1 && val > BoardSize) 
    { 
     throw rangeError("bad value in checkConflicts()"); 
    } 

    if (rowConf[i][val] || colConf[j][val] || squConf[k][val]) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
} 

Initial Board: 
----------------------------- 
| 3  | 8 |   ----------------------------- 
|   | 7  |  5 ----------------------------- 
| 1  |   |   ----------------------------- 
----------------------------- 
|   |   | 3 6  ----------------------------- 
|  2 |  4 |   ----------------------------- 
| 7 |   |   ----------------------------- 
----------------------------- 
|   | 6 | 1 3  ----------------------------- 
| 4 5 | 2  |   ----------------------------- 
|   |   | 8  ----------------------------- 
----------------------------- 

Final Output: 
----------------------------- 
| 3 2 4 | 1 8 5 | 6 7 9 ----------------------------- 
| 6 8 9 | 7 2 3 | 4 1 5 ----------------------------- 
| 1 5 7 | 4 9 6 | 2 8 3 ----------------------------- 
----------------------------- 
|   |   | 3 6  ----------------------------- 
|  2 |  4 |   ----------------------------- 
| 7 |   |   ----------------------------- 
----------------------------- 
|   | 6 | 1 3  ----------------------------- 
| 4 5 | 2  |   ----------------------------- 
|   |   | 8  ----------------------------- 
----------------------------- 

void board::clearCell(int i, int j) 
{ 
    int intVal; 

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize) 
    { 
     if (value[i][j] != -1) 
     { 
      intVal = value[i][j]; 
      rowConf[i][intVal] = false; 
      colConf[j][intVal] = false; 
      squConf[squareNumber(i, j)][intVal] = false; 
      value[i][j] = -1; 
     } 
    } 
    else 
    { 
     throw rangeError("bad value in setCell"); 
    } 
}

來源

2012-11-04 zberry92

是否輸出板卡解決？這將是遞歸結束的一種可能性。 – phant0m

另外，請提供'clearCell'功能。 – phant0m

我添加了明確的單元文件。它從來沒有被宣佈解決。發生什麼事情是由於某種原因，由於沒有可用的移動來放置，而不是移動到第一個空白單元的for循環的下一個迭代，所以它不會回到開始嘗試新的方法，而是希望一個遞歸和結束。 – zberry92

你的問題很可能是在這裏：

if (isBlank(i, j)) 
{ 
    for (int n = 1; n < 10; n++) 
    { 
     if (setCell(i, j, (char)n + '0')) 
     { 
      if (solveBoard(i, j + 1, count + 1)) 
      { 
       return true; 
      } 
      } 
     } 
    }

不知怎的，它是通過這一部分，這就是爲什麼它不通過else打算去最後，但由於它以前沒有返回，它會卡住。

這需要更多的調試，但這裏是一個想法，可能會導致一個解決方案：

if (isBlank(i, j)) 
{ 
    for (int n = 1; n < 10; n++) 
    { 
     if (setCell(i, j, (char)n + '0')) 
     { 
      if (solveBoard(i, j + 1, count + 1)) 
      { 
       return true; 
      } else { 
       echo 'Looks like it ended on the farthest-level..'; 
      } 
     } else { 
      echo 'Looks like it ended on the second-farthest level.'; 
     } 
    }

來源

2012-11-05 14:54:10

爲什麼你有多個'else'子句？另外，你的'else'基本上是這樣說的：''如果第一次沒有用，我們再試一次''。這是行不通的。 – phant0m

@ phant0m，謝謝，編輯。對於沒有運行的每一個「如果」來說，這只是另一個。無論如何，我的觀點是，看起來這是它退出OP代碼的地方，OP應該找到一種方法來跟蹤它。 –

的atoi函數需要串作爲一個參數，即用字符'\0'終止字符數組，ASCII NUL。你給一個參數是一個指向字符的指針（相當於一些字符），但不保證它是零終止的。請intVal = (int)val - '0';

而且你checkConflicts更換intVal = atoi(&val);應該有||運營商，而不是在第一if&&。

這些可能不是錯誤的原因，但肯定需要更正。

來源

2014-03-09 00:48:02 CiaPan

數獨遞歸回溯，無法過早

回答

相關問題