Судоку Solver в SML с обратным отсчетом

Question

Я работаю над созданием Soloku Solvo с 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]] 

Теперь это отчасти верно. Первые четыре строки выглядят полностью корректными на основе онлайн-решения sudoku, который я использовал для проверки, но он перепутался с 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; 

Более твердые доски могут потребовать довольно долгого времени, чтобы полностью решить проблему, но каждый, который я испытал, в конечном итоге попадает туда. Я уверен, что в моем коде есть много оптимизаций, поэтому я открыт для предложений.