kedarbellare

# CHALLENGE PROBLEM: 
#
# Use your check_sudoku function as the basis for solve_sudoku(): a
# function that takes a partially-completed Sudoku grid and replaces
# each 0 cell with a number in the range 1..9 in such a way that the
# final grid is valid.
#
# There are many ways to cleverly solve a partially-completed Sudoku
# puzzle, but a brute-force recursive solution with backtracking is a
# perfectly good option. The solver should return None for broken

kedarbellare

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

kedarbellare

def thresholdLevenshtein(_s: String, _t: String, threshold: Int): Int = {
  val (s, t) = if (_s.length > _t.length) (_s, _t) else (_t, _s)
  val slen = s.length
  val tlen = t.length

  var prev = Array.fill[Int](tlen+1)(Int.MaxValue)
  var curr = Array.fill[Int](tlen+1)(Int.MaxValue)
  for (n <- 0 until math.min(tlen+1, threshold+1)) prev(n) = n

  for (row <- 1 until (slen+1)) {