Java中的數獨求解器，使用回溯和遞歸

Question

我正在爲Java 9x9網格編程一個數獨求解器。

我有方法：

• 打印網格

• 與給定的值初始化爲板衝突

• 測試（如果相同數量的處於同一行或3×3子格）

• 一種方法來放置數字，一個接一個，這需要最多的工作。

我細講與方法之前，請記住，我不得不用遞歸來解決它，以及（在這裏觀看小程序作爲例子http://www.heimetli.ch/ffh/simplifiedsudoku.html）回溯

另外，我我解決這個數獨的垂直向下運動，從左上角開始，通過第一列，然後通過第二列等

到目前爲止，我有以下幾點：

public boolean placeNumber(int column){ 

    if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over 

     return true; 

    } 

    else 
    { 
     int row=0; //takes you to the top of the row each time 

     while (row < SUDOKU_SIZE) loops through the column downwards, one by one 
     { 

      if (puzzle[row][column]==0){ //skips any entries already in there (the given values) 

       puzzle[row][column]=1; //starts with one 

       while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number 

        puzzle[row][column] += 1; 

       } 


      //BACK TRACKING 

       placeNumber(column);  //recursive call 

      } 
      else{ 
       row++;     // row already has a number given, so skip it 
      } 
     } 

     column++;    // move on to second column 
     placeNumber(column); 

    } 
    return false; // no solutions to this puzzle 
} 

在哪裏我標記爲BACKTRACKING是我相信我的代碼的其餘部分需要去的地方。

我想到了沿着線的東西：

• 如果該值爲10，設定值回零，回去一排，並通過1

增加該值這回溯「戰略」並不完全有幾個原因的工作：

1. 如果什麼上一行，是一個給定值（又名我不應該增加它或觸摸它，但取而代之的是，回到我放在那裏的最後一個值）

2. 如果前一個值是9，那麼該怎麼辦？如果我遞增了1，現在我們就是10，這是行不通的。

有人能幫我嗎？

Answer 1

我不知道你將如何解決數獨，但即使你使用暴力方法（因此聽起來你所描述的），你應該考慮你的數據結構是不恰當的。因此，我的意思是說，每個細胞不應該只是一個數字，而應該是一組數字（可能放在那裏）。

因此，給定的數字將被表示爲單個集合，而空的可以用{1,2,3,4,5,6,7,8,9}初始化。 然後我們的目標是減少非單細胞細胞，直到所有細胞都是單細胞。

（需要注意的是，在解決用鉛筆和紙數獨，一個經常在空白單元格中寫入少量跟蹤的什麼數字是可能有，只要一個已經解決了這個問題。）

而且然後，當「嘗試下一個號碼」時，您從集合中取出下一個號碼。鑑於細胞沒有下一個數字，所以你不能改變它們。這樣，你所描述的困難就會消失（至少有一點）。

------編輯，在已經得知蠻力是必需的。

你的老師顯然想教你遞歸的奇蹟。很好！

在這種情況下，我們只需要知道這是給細胞，哪些不是。

可以在此處使用的特定容易的方法是在任何非給定的小區放置一個0，如給定的細胞是通過定義的1,2,3,4,5,6,7,8,9一個。

現在讓我們思考如何使遞歸蠻力工作。

我們必須解決具有n個空單元格數獨的目標。 如果我們不得不將解決n-1個空單元格數獨的函數（或信號，這是不可解的），那麼這個任務會很容易：

let c be some empty cell. 
let f be the function that solves a sudoku with one empty cell less. 
for i in 1..9 
    check if i can be placed in c without conflict 
    if not continue with next i 
    place i in c 
    if f() == SOLVED then return SOLVED 
return NOTSOLVABLE 

這個僞代碼挑選一些空細胞，然後嘗試所有適合的數字。 由於數獨有 - 根據定義 - 只有一個解決方案，只有以下情況：

• 我們選擇了正確的數字。然後f（）將找到解決方案的其餘部分並返回已解決。
• 我們選了一個錯誤的數字：f（）表示數獨是不可解的，在我們的單元格中有錯誤的數字。
• 我們檢查了所有的數字，但沒有人是正確的：然後我們自己得到了一個無法解決的數獨，並且我們將這個信號發送給我們的呼叫者。

毋庸置疑，該算法是基於這樣一個假設，即我們只將與當前狀態衝突的數字與 衝突。例如，如果在同一行，列或方框中已有9，我們不會放置9。

如果我們現在想想我們的神祕，但未知的功能f()是什麼樣子的，事實證明它與我們已有的幾乎相同！
我們尚未考慮的唯一情況是一個有0個空單元的數獨。這意味着，如果我們發現沒有更多的空單元格，我們知道我們剛剛解決了數獨並返回瞭解決方案。

這是編寫本應解決問題的遞歸函數時的常見技巧。我們正在編寫解決方案（），而且我們知道，問題是可以解決的。因此，只要我們確保每次遞歸都能以某種方式更接近解決方案，我們就可以使用我們只寫的函數。最後，我們達到所謂的基本情況，我們可以在沒有進一步遞歸的情況下給出解決方案。

在我們的案例中，我們知道數獨是可以解決的，而且，我們知道它有正好一個的解決方案。通過在一個空單元中放置一塊，我們更接近解決方案（或診斷爲沒有），並遞歸地向我們剛剛寫入的函數遞交新的小問題。基本情況是「具有0個空單元格的數獨」，實際上是解決方案。

（事情得到，如果有很多種可能的解決方案比較複雜一點，但我們留到下一課。）

Answer 2

我建議通過雙方目前的行和列的遞歸方法 然後找到所有允許該單元號，每個允許的數量recursivly呼籲下一列的方法（或下一行，如果在最後一列），並撤消移動，如果它導致死亡軌道

public boolean fillCell(int r, int c) { 
    if last row and last cell { 
     //report success 
     return true 
    } 
    for i 1 to 9 { 
     if can place i on r, c { 
      board[r][c] = i 
      if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move 
       board[r][c] = 0 
      } 
      /* 
      else { 
       return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also 
      } 
      */ 

     } 
    } 
    return false   
} 

Answer 3

我會檢查每個單元和如果找不到解決方案，請返回遞歸步驟。

詳細信息： 轉到下一個單元格，如果值x == 0，檢查x + 1是否有效，如果爲true，則通過遞歸調用下一個可能的單元格轉到下一個單元格。如果該號碼無效，請檢查x + 2等，如果沒有號碼有效，則返回false並重覆上一次呼叫中的x + 1步驟。如果你用一個數字打了一個單元格，不要調用遞歸，而是直接進入下一個單元格，因此你不需要標記任何預先輸入的單元格。

僞代碼：

fillcell cell 
while cell is not 0 
    cell = next cell 
while cell value < 10 
    increase cell value by one 
    if cell is valid 
    if fillcell next cell is true 
     return true 
return false 

不知道這是否正確的，但它應該顯示的想法。

Answer 4

一些想法，可能是有益的（關於遞歸和回溯）

//some attributes you might need for storing e.g. the configuration to track back to. 

boolean legal(Configuration configuration) { 

} 

int partSolution(Configuration configuration) { 
    if (legal(configuration)) 
    return partSolution(nextConfiguration()) 
    else 
    return partSolution(previousConfiguration())   
} 

Configuration nextConfiguration() { 
//based on the current configuration and the previous tried ones, 
//return the next possible configuration: 
//next number to enter, next cell to visit 
} 

Configuration previousConfiguration() { 
//backtrack 
} 

solve() { 
    call partSolution with start configuration while partSolution < 9x9 
} 

寫持有格與輸入的數字和一些其他屬性，如大小和#numbers進入想想一個配置類什麼否則需要

Answer 5

首先，一個優化的建議：在檢查您打算放入單元格中的數字是否已存在於同一行，列或小圖格中時，您不必運行一個循環或類似的東西。您可以通過數組索引執行即時檢查。

考慮3個9x9的布爾雙維數組：

boolean row[9][9], col[9][9], minigrid[9][9] 

，我們將使用所述第一陣列，用於檢查號碼是否存在於相同行中，用於檢查所述第二陣列一個數是否爲存在於同一列，第三個爲迷你網格。

假如你想放一些ñ在你的我，Ĵ。你會檢查是否行[i] [n-1]爲真。如果是，則i^th行已包含n。同樣，你會檢查是否col [j] [n-1]和minigrid [gridnum] [n-1]爲真。

這裏gridnum是微型電網，要插入大量的細胞，位於指數。要通過3計算小格號電池I，J，除我&Ĵ，乘以前者與3的組成部分，並將其添加到後者的組成部分。

這它的外觀：

gridnum = (i/3)*3 + j/3 

通過望着我爲人人/ 3和j/3 i和j，你會得到的是如何工作的想法值。另外，如果您在單元格中添加數字，也要更新數組。例如。 row [i] [n-1] = true

如果有不明白的部分，請發表評論，我會編輯我的回答以解釋它。

其次，使用遞歸&回溯解決這個很容易。

boolean F(i, j) // invoke this function with i = j = 0 
{ 
If i > 8: return true // solved 

for n in 1..9 
{ 
check if n exists in row, column, or mini grid by the method I described 

if it does: pass (skip this iteration) 

if it doesn't 
    { 
    grid[i][j] = n 
    update row[][], col[][], minigrid[][] 

    if F(if j is 8 then i+1 else i, if j is 8 then 0 else j+1) return true // solved 
    } 
} 
return false // no number could be entered in cell i,j 
}