C++ - 解決數獨遊戲

我是C++的新手，必須做一個家庭作業（數獨）。我被困在一個問題上。C++ - 解決數獨遊戲

問題是要實現一個解決數獨的搜索功能。

指令：爲了找到解決方案遞歸搜索使用如下。假設有一個尚未分配字段的數字（d1 .... dn）（n> 1）。然後我們首先嚐試將字段賦值給d1，執行傳播，然後遞歸地繼續搜索。可能發生的情況是傳播導致失敗（一個字段變爲爲空）。在這種情況下，搜索失敗，需要嘗試不同的數字作爲字段之一。由於搜索是遞歸的，因此嘗試了最後一個考慮的字段的下一個數字。如果沒有數字導致解決方案，搜索將再次失敗。這在轉，將導致嘗試從以前的領域不同的數字，等等。

一個數字d之前被分配領域它試圖，你必須創建一個新的董事會被現任董事會的一個副本（使用拷貝構造函數和新堆中分配的板）。只有然後在副本上執行分配。如果搜索的遞歸調用返回失敗，則可嘗試爲下一個數字創建新的電路板。

我已經試過：

// Search for a solution, returns NULL if no solution found 
Board* Board::search(void) { 
    // create a copy of the cur. board 
    Board *copyBoard = new Board(*this); 
    Board b = *copyBoard; 

    for(int i = 0; i < 9; i++){ 
     for(int j = 0; j < 9; j++){ 

       // if the field has not been assigned, assign it with a digit 
      if(!b.fs[i][j].assigned()){ 
       digit d = 1; 

        // try another digit if failed to assign (1 to 9) 
       while (d <=9 && b.assign(i, j, d) == false){ 
         d++; 


         // if no digit matches, here is the problem, how to 
         // get back to the previous field and try another digit? 
         // and return null if there's no pervious field 
       if(d == 10){ 
         ... 
        return NULL; 
       } 
      } 
     } 
    } 
    return copyBoard; 
}

的另一個問題是在哪裏使用遞歸調用？有小費嗎？謝謝！

完整的指令能夠被發現這裏：http://www.kth.se/polopoly_fs/1.136980!/Menu/general/column-content/attachment/2-2.pdf

代碼：http://www.kth.se/polopoly_fs/1.136981!/Menu/general/column-content/attachment/2-2.zip

來源

2011-12-06 Ferry

你有什麼想法在這一點遞歸，以及如何使用它？ –

。在你的代碼中沒有遞歸。你不能只訪問每個領域一次，並嘗試給它分配一個值。問題在於，你可以將5分配給字段（3,4），也可能只有當你到達字段（6,4）時，結果表明不能有5（3），4）。最終你需要退出遞歸，直到你回到（3,4）並在那裏嘗試另一個值。

遞歸可能不會使用嵌套for循環訪問字段，而是通過遞歸調用訪問下一個字段。要麼你設法到達最後一個領域，要麼嘗試所有可能性，然後讓功能回到你前面訪問過的領域。

旁註：絕對不執行此任務動態分配內存空間：

//Board *copyBoard = new Board(*this); 
Board copyBoard(*this); //if you need a copy in the first place

來源

2011-12-06 15:16:45 UncleBens

基本上你可以嘗試是這樣的（pseudocode'ish）

bool searchSolution(Board board) 
{ 
Square sq = getEmptySquare(board) 
if(sq == null) 
    return true; // no more empty squares means we solved the puzzle 

// otherwise brute force by trying all valid numbers 
foreach (valid nr for sq) 
{ 
    board.doMove(nr) 

    // recurse 
    if(searchSolution(board)) 
     return true 

    board.undoMove(nr) // backtrack if no solution found 
} 

// if we reach this point, no valid solution was found and the puzzle is unsolvable 
return false; 

}

的getEmptySquare （...）函數可以返回一個隨機空方塊或剩餘選項數最少的方塊。使用後者會使算法收斂得更快。

來源

2011-12-06 16:32:40 danca

C++ - 解決數獨遊戲

回答

相關問題