Sudoku

# A sudoku solver for simple sudokus and
# a backtracking solver for harder ones.

function string_to_list(s)
   k = 0; a = []; b = []
   for c in s
      if c.isdigit()
         k+=1; a.push(int(c))
      elif c=='.'
         k+=1; a.push(0)
      end
      if k==9
         k = 0; b.push(a)
         a = []
      end
   end
   return b
end

function list_to_string(a)
   a.map(fn|x|
      x.chunks(3).list().map(fn|y|
         y.map(|d| '.' if d==0 else str(d)).join()
      end).join("|")
   end).chunks(3).list().map(fn|y|
      y.join("\n")
   end).join("\n---+---+---\n")
end

function row_set(a,i)
   set(a[i].filter(|x| x!=0))
end

function col_set(a,j)
   set(list(0..8).map(|i| a[i][j]).filter(|x| x!=0))
end

function box_set(a,i,j)
   i = (i//3)*3; j = (j//3)*3
   set(list(0..2).map(fn|x|
      list(0..2).map(|y| a[i+x][j+y])
   end).chain().filter(|x| x!=0))
end

function step(a)
   for i in 0..8
      for j in 0..8
         if a[i][j]==0
            M = set(1..9)-(row_set(a,i)|col_set(a,j)|box_set(a,i,j))
            if len(M)==1
               a[i][j] = list(M)[0]
               return true
            end
         end
      end
   end
   return false
end

function solve(a)
   t = true
   while t
      t = step(a)
   end
end


# Backtracking 

function bsolve(a)
   for i in 0..8
      for j in 0..8
         if a[i][j]==0
            M = set(1..9)-(row_set(a,i)|col_set(a,j)|box_set(a,i,j))
            s = []
            for x in M
               b = a.map(copy)
               b[i][j] = x
               s.append(bsolve(b))
            end
            return s
         end
      end
   end
   return a.map(copy)
end

function main(s)
   a = string_to_list(s)
   solve(a)
   print(list_to_string(a),"\n")
end

function bmain(s)
   a = bsolve(string_to_list(s))
   print(list_to_string(a),"\n")
end

s1 = """
..3|..9|6..
4..|..2|..3
862|153|.9.
---+---+---
5.7|2.6|.3.
.3.|5..|...
6.9|.7.|.51
---+---+---
.2.|4.8|..7
.4.|.3.|.2.
3..|.25|148
"""

main(s1)
bmain(s1)