带回溯的 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 以上样本数据 returns 以下列表

[[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 行就搞砸了。我猜是因为不能一路回溯。

它唯一的地方"backs up"就在这条线上

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;

较硬的板可能需要相当长的时间才能完全解决，但我测试过的每一个最终都会到达那里。我确信我可以在我的代码中做大量的优化，所以我愿意接受建议。

带回溯的 SML 中的数独求解器

Sudoku Solver in SML with Backtracking

sml

smlnj

sudoku

backtracking