(* returns true if there is a zero in the given list *)
fun zeroInList list =
  if length (List.filter (fn x => x = 0) list) > 0 then true else false;

(* returns true if a list of lists has no 0's (does not check for valid Sudoku board) *)
fun completedBoard lists =
  if length (List.filter zeroInList lists) > 0 then false else true;

(* inserts an element into a list at the specified position *)
fun insertAtPos [] x k = [x]
  | insertAtPos ls x 0 = x::ls
  | insertAtPos (l::ls) x k = l::(insertAtPos ls x (k - 1));

(* sums a list *)
fun total [] = 0
  | total (x::xs) = x + (total xs);

(* calculates the triangular sum of a given number
ex: triangularSum 5 = 5 + 4 + 3 + 2 + 1 = 15 *)
fun triangularSum 0 = 0
  | triangularSum num = num + triangularSum (num - 1);

(* remove an element from a list *)
fun removeElem s [] = []
  | removeElem s (x::xs) =
      if s = x then xs
      else x::(removeElem s xs);

(* remove an element (by index) from a list *)
fun delete (_,   nil) = nil
  | delete (0, _::xs) = xs
  | delete (i, x::xs) = x::delete(i-1,xs);

(* replaces a 0 in a list with the "missing number" *)
fun insertNum list =
  if not(zeroInList list) then list
  else
    let
      fun insertNum' list index =
       if List.nth(list, index) = 0 then
         let
           fun numberMissing list = (triangularSum (length list)) - (total list);
         in
           removeElem 0 (insertAtPos list (numberMissing list) index)
         end
       else insertNum' list (index + 1)
    in
      insertNum' list 0
  end;


(* fills the missing spot of a given list (used to force sudoku rows / cols / boxes *)
fun fillList list =
  if length (List.filter (fn x => x = 0) list) = 1 then insertNum list
  else list;

(* returns true if there is a duplicate of any number other than zero in a given list *)
fun isNonZeroDupe [] = false
  | isNonZeroDupe (x::xs) =
    (List.exists (fn y => if y = 0 then false else x = y) xs)
    orelse (isNonZeroDupe xs);

(* returns the index of an element in a list *)
fun index (x, []) = raise Subscript
  | index (x, y::ys) =
    if x = y then 0 else 1 + index (x, ys);

fun getNth num list = List.nth(list, num);

(* converts a list of lists that represent the rows of a sudoku board into the columns *)
fun rowsToCols rows =
  let
    fun rowsToCols' rows cols index =
      if index = (length rows) then cols
      else rowsToCols' rows (cols@[(map (getNth index) rows)]) (index + 1)
  in
    rowsToCols' rows [] 0
  end;

(* converts a list of lists that represent the rows of a sudoku board into the 3x3 boxes *)
fun rowsToBoxes rows =
  let
    fun rowsToBoxes' rows boxes index =
      if index + 2 >= (length rows) then boxes
      else
        let
          val box1 = List.take(List.nth(rows, index), 3)
                    @List.take(List.nth(rows, index + 1), 3)
                    @List.take(List.nth(rows, index + 2), 3);

          val box2 = List.drop(List.take(List.nth(rows, index), 6), 3)
                    @List.drop(List.take(List.nth(rows, index + 1), 6), 3)
                    @List.drop(List.take(List.nth(rows, index + 2), 6), 3);

          val box3 = List.drop(List.take(List.nth(rows, index), 9), 6)
                    @List.drop(List.take(List.nth(rows, index + 1), 9), 6)
                    @List.drop(List.take(List.nth(rows, index + 2), 9), 6);
        in
          rowsToBoxes' rows (boxes@[box1]@[box2]@[box3]) (index + 3)
        end;
  in
    rowsToBoxes' rows [] 0
  end;

(* forces any empty spots of a given sudoku board *)
fun force board =
  let
    fun forceRows board =
      map fillList board;
    fun forceCols board =
      rowsToCols(map fillList (rowsToCols board));
    fun forceBoxes board =
      rowsToBoxes(map fillList (rowsToBoxes board));
  in
    forceBoxes (forceCols (forceRows board))
  end;

(* checks if a given sudoku board is legal *)
fun checkLegal board =
  let
    fun checkRows board =
      if length (List.filter isNonZeroDupe board) > 0 then false else true;
    fun checkCols board =
      if length (List.filter isNonZeroDupe (rowsToCols board)) > 0 then false
      else true;
    fun checkBoxes board =
      if length (List.filter isNonZeroDupe (rowsToBoxes board)) > 0 then false
      else true;
  in
    checkRows board andalso checkCols board andalso checkBoxes board
  end;

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;

(* test board
solve by calling: solve easy; *)
val easy = [
[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]];