#!/usr/bin/awk -f
# a backtracking sudoku solver - marcus fritzsch http://fritschy.de 20070120
#
#   ./sudoku.awk < puzzle.txt
#   where puzzle is a file of 9 lines a nine characters in range
#   [0..9] where 0 stands for empty cells
BEGIN {
  for (a=0; a<9; a++) for (b=0; b<9; b++) puzzle[a*9+b]=0
  FS=""; cr=0; ctr=0
}
{
  gsub(/-\. \*/,"0")
  for (b=0; b<9; b++) puzzle[cr*9+b-1]=int($b)
  cr++
}
function IsValid () {
  for (i=0; i<9; i++) # check row and col
    if (puzzle[r*9+i]==s || puzzle[i*9+c]==s) return 0
  for (a=int(r/3)*3; a<int(r/3)*3+3; a++) # check block
    for (b=int(c/3)*3; b<int(c/3)*3+3; b++)
      if (puzzle[a*9+b]==s) return 0
  return 1
}
function Push () { sr[ctr]=r; sc[ctr]=c; ss[ctr]=s; ++ctr }
function Pop () { --ctr; r=sr[ctr]; c=sc[ctr]; s=ss[ctr] }
function pl () {
  printf "+"
  for (aa=0; aa<9; aa++) printf "-%s", (aa%3==2)?"+":"--"
  print ""
}
function Print () {
  for (a=0; a<9; a++) {
    if (a%3==0) pl()
    printf "| "
    for (b=0; b<9; b++) printf "%d%s", puzzle[a*9+b], (b%3==2)?" | ":" "
    print ""
  }
  pl(); print ""
}
function Solve () {
  Push()
  while (puzzle[r*9+c]) {
    if (c==8) { r++; c=0 } else c++
    if (r==9) { Print(); ++solutions; Pop(); return }
  }
  for (s=1; s<=9; s++)
    if (IsValid()) { puzzle[r*9+c]=s; Solve(); puzzle[r*9+c]=0 }
  Pop()
}
END {
  ctr=0; r=0; c=0; s=1; solutions=0
  Solve()
  printf "Found %d solution%s\n", solutions, solutions==1?"":"s"
}