具有回溯的SML中的數獨求解器

Question

我正在用SML/NJ創建一個數獨求解器。我已經掌握了實際操作輸入數據的所有功能（檢查行的合法性，強制空白空間等），但是我在回溯部分遇到問題。

我碰到過this question但我很困惑如何在SML中實現它。

。注意，板被輸入作爲表示每一行，0中的數字對於一個未知點

[[0,0,0, 2,6,0, 7,0,1], 
[6,8,0, 0,7,0, 0,9,0], 
[1,9,0, 0,0,4, 5,0,0], 

[8,2,0, 1,0,0, 0,4,0], 
[0,0,4, 6,0,2, 9,0,0], 
[0,5,0, 0,0,3, 0,2,8], 

[0,0,9, 3,0,0, 0,7,4], 
[0,4,0, 0,5,0, 0,3,6], 
[7,0,3, 0,1,8, 0,0,0]] 

這是我的（編輯）solve功能列表的列表。

exception Sudoku; 
fun solve board = 
    let fun solve' board k = 
    (* k is the row we are working on, so if it's 9, we SHOULD be done *) 
    if k = 9 then board else 
    let 
     (* get row k from the board *) 
     val row = (List.nth (board, k)); 

     fun trySpot number col = 
     (* if number >= 10, raise an exception to backtrack *) 
     if number > (length row) then raise Sudoku 
     (* if col = 9, raise an exception to backtrack *) 
     else if col = 9 then raise Sudoku 
     (* if row[col] is not a zero, move to next col *) 
     else if not (List.nth(row, col) = 0) then trySpot number (col + 1) 
     (* row doesn't contain this num already *) 
     else if length (List.filter (fn x => x = number) row) = 0 then 
      let 
      (* build the new row and board and check if legal (this works fine) *) 
      val newRow = delete(col + 1, (insertAtPos row number col)); 
      val newBoard = delete(k + 1, (insertAtPos board newRow k)); 
      val isLegal = checkLegal newBoard; 
      in 
      (* if legal, keep solving with new board as base *) 
      if isLegal then 
       solve' (force newBoard) 0 
       handle Sudoku => solve' (force board) (k + 1) 
      (* not legal, try with next num *) 
      else trySpot (number + 1) col 
      end 
     (* row already has this number, skipping *) 
     else trySpot (number + 1) col 
    in 
     (* if board is complete and legal we're done *) 
     if completedBoard board andalso checkLegal board then board 
     (* if row has a zero then try a spot *) 
     else if (zeroInList row) then trySpot 1 0 
     (* otherwise move to next row *) 
     else solve' (force board) (k + 1) 
    end 
    in 
    (* initial solve *) 
    solve' (force board) 0 
    end; 

調用上的採樣數據solve上述返回以下列出

[[4,3,5,2,6,9,7,8,1], 
[6,8,2,5,7,1,4,9,3], 
[1,9,7,8,3,4,5,6,2], 

[8,2,6,1,9,5,3,4,7], 
[3,1,4,6,8,2,9,0,0], 
[0,5,0,0,0,3,0,2,8], 

[0,0,9,3,0,0,0,7,4], 
[2,4,0,0,5,0,0,3,6], 
[7,0,3,0,1,8,0,0,0]] 

現在，這是部分正確。前四行看起來是完全正確的，這是基於我用來檢查的在線數獨求解器，但它會在第5行中搞砸。我認爲這是因爲它無法一路走回頭路。

它「備份」的唯一地方是在這條線

handle Sudoku => solve' (force board) (k + 1) 

這告訴它只是試圖解決舊板（沒有新的號碼），但是，這是防止它回溯多於一步（我認爲）。這怎麼可能完成？

如果有人好奇，想看看完整的代碼，你可以找到它here.

提前感謝！

Answer 1

我似乎已經得到了我的解決函數來處理我嘗試過的所有案例。訣竅是跟蹤我們正在工作的地點的非法數字列表。求解器現在跳過這些數字，並且如果它找不到前進的路徑則回溯。

exception Sudoku; 
(* solves a soduku board input that gives a list of lists representing the rows of a board (0 for unknown spaces) *) 
fun solve board = 
    let fun solve' board row illegalNums = 
    (* if we are on row 9 and board is complete/legal, we are done *) 
    if row = 9 andalso completedBoard board andalso checkLegal board then board else 
    (* if we are on row 9 but the board is not complete/legal, throw an exception to backtrack *) 
    if row = 9 then raise Sudoku else 
    let 
     (* get the current row we are working on *) 
     val cRow = (List.nth (board, row)); 

     (* trys a row[col] on the board with a certain number *) 
     fun trySpot num cRow col = 
     (* if number >= 10, raise an exception to backtrack *) 
     if num > 9 then raise Sudoku 
     (* if row[col] is not a 0, try next col *) 
     else if not (List.nth (cRow, col) = 0) then trySpot num cRow (col + 1) 
     (* if we know that the number we are on isn't allowed, skip to next number *) 
     else if length (List.filter (fn x=> x = num) illegalNums) > 0 then trySpot (num + 1) cRow col 
     (* if row already has this number, skip to next number *) 
     else if length (List.filter (fn x=> x = num) cRow) > 0 then trySpot (num + 1) cRow col 
     (* if col already has this number, skip to next number *) 
     else if length (List.filter (fn x=> x = num) (List.nth((rowsToCols board), col))) > 0 then trySpot (num + 1) cRow col 
     else 
      let 
      (* make our new row and board *) 
      val newRow = delete(col + 1, (insertAtPos cRow num col)); 
      val newBoard = delete(row + 1, (insertAtPos board newRow row)); 
      in 
      (* if new board is legal, continue solving *) 
      if checkLegal newBoard then 
       solve' (force newBoard) 0 [] 
       (* handle any exceptions by adding the number to our list of illegal numbers, thereby backtracking *) 
       handle Sudoku => solve' (force board) row (illegalNums@[num]) 
      (* if new board is not legal, try next number *) 
      else trySpot (num + 1) cRow col 
      end 
    in 
     (* if board is completed and legal, return board *) 
     if completedBoard board andalso checkLegal board then board 
     (* if current row has at least one 0, try a number in that row (beginning at col 1) *) 
     else if (zeroInList cRow) then trySpot 1 cRow 0 
     (* else, skip to next row and solve *) 
     else solve' (force board) (row + 1) [] 
    end 
    in 
    (* initial solve *) 
    solve' (force board) 0 [] 
    end; 

較硬板可能需要相當長一段時間完全解決，但每一個我最終測試到達那裏。我確信在我的代碼中可以做很多優化，所以我願意提供建議。