use sys

function error(s)
   print("Error: ", s)
   sys.exit(1)
end

function str_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_str(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

function main(s,L)
   a = str_to_list(s)
   solve(a)
   if list_to_str(a)!=L
      error("#sudoku")
   end
end

# Backtracking 

function bsolve(a)
   # solve(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 bmain(s,L)
   a = bsolve(str_to_list(s))
   if len(a)!=1 or list_to_str(a[0])!=L
      error("#sudoku-backtracking")
   end
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
"""

L1 = """\
753|849|612
491|762|583
862|153|794
---+---+---
517|286|439
234|591|876
689|374|251
---+---+---
925|418|367
148|637|925
376|925|148\
"""

main(s1,L1)
bmain(s1,L1)