Making and Slaying Monster Sudoku

⟨functions⟩ +≡ ↑↓
  def load_board(s, validate_vals=True):
      '''
      given a string representing a board, returns a board object. For a board of
      a given order:
  
      - Order is computed as the fourth root of board length, and it must be an 
        integer.
  
      - Each cell must be represented by an integer in [1, order**2] inclusive, 
        or `.' to denote unknown cells. This check can be disabled by setting
        validate_vals to False.
  
      - Cells must be separated from each other by any sequences of characters in
        /[^0-9.]+/.
  
      On failure, raises ValueError.
      '''
  
      vals = [cell
              for cell in ''.join(c if c in '0123456789.' else ' '
                                  for c in s).strip().split()
              if cell.isdigit() or cell == '.']
  
      order = int(len(vals) ** 0.25)
      n = order**2
      if len(vals) != order**4: raise ValueError
  
      bd = blank(order)
  
      for (cell, val_) in enumerate(vals):
          if val_ == '.': continue
          val = int(val_)
          if validate_vals and (val < 1 or val > n): raise ValueError
          bd.mark(cell, val)
  
      return bd

⟨functions⟩ +≡ ↑↓
  def blank(order):
    'generate a blank board'
    n = order**2
    possible_vals = set(range(1, n + 1))
    return board({},
                 {i:set(possible_vals) for i in range(n**2)},
                 *board_divs(order))

⟨functions⟩ +≡ ↑↓
  def isvalid(bd):
      '''
      returns True if
      - no known cells' values conflict
      - no unknown cell's possibilities conflict with any known cell's value
      '''
      return not any(val0 in {bd.known.get(cell)} | bd.unknown.get(cell, set())
                     for (cell0, val0) in bd.known.items()
                     for cell in neighbors(bd, cell0)
                     if cell in bd.known and cell != cell0)
  
  def neighbors(bd, cell0):
      return union(bd.div2cells[div] for div in bd.cell2divs[cell0])
  
  def union(xss):
      return {x for xs in xss for x in xs}

⟨functions⟩ +≡ ↑↓
  def dump_board(bd):
      'returns a "pretty printed" string representation of board bd'
      order = int((len(bd.known) + len(bd.unknown)) ** 0.25)
      n = order**2
  
      svals = [str(bd.known[i] if i in bd.known else '.')
               for i in range(n**2)]
  
      width = max(map(len, svals))
      fmt = lambda cell: ('%%%ds' % width) % cell
  
      n_x_n = [svals[i*n : i*n + n] for i in range(n)]
      cols_grpd = [' | '.join(' '.join(map(fmt, row[j*order : j*order + order]))
                             for j in range(order))
                   for row in n_x_n]    
      rows_grpd = ['\n'.join(cols_grpd[i*order : i*order + order])
                   for i in range(order)]
  
      rule = '\n' + ''.join('+' if c == '|' else '-' for c in cols_grpd[0]) + '\n'
  
      return rule.join(rows_grpd)

⟨functions⟩ +≡ ↑↓
  def mark_single_vals(bd):
      'applies the "single candidate" (a.k.a. "naked single") rule'
      marked = False
      for (cell, vals) in list(bd.unknown.items()):
          if len(vals) == 1:
              bd.mark(cell, set(vals).pop())
              marked = True
  
      return marked

⟨functions⟩ +≡ ↑↓
  def mark_single_cells(bd):
      'applies the "hidden single" rule'
      marked = False
      hidden = ((val, cells.pop())
                for div in bd.div2cells
                for (val, cells) in placements(bd, div).items()
                if len(cells) == 1)
      for (val, cell) in hidden:
          if val in bd.unknown.get(cell, set()):
              bd.mark(cell, val)
              marked = True
      return marked

⟨functions⟩ +≡ ↑↓
  def placements(bd, div):
      return transpose({cell: bd.unknown[cell]
                        for cell in bd.div2cells[div]
                        if cell in bd.unknown})

⟨functions⟩ +≡ ↑↓
  def mark_excluded(bd):
      marked = False
      excluded = ((cell, val)
                  for div0 in bd.div2cells
                  for (val, cells) in placements(bd, div0).items()
                  for div in (intersection(bd.cell2divs[cell] for cell in cells)
                              - {div0})
                  for cell in bd.div2cells[div] - cells - set(bd.known)
                  if val in bd.unknown[cell])
      for (cell, val) in excluded:
          bd.elim(cell, val)
          marked = True
      return marked

⟨imports⟩ +≡ ↑↓
  from functools import reduce

⟨functions⟩ +≡ ↑↓
  def intersection(xs): return reduce(lambda a,x: a&x, xs)

⟨functions⟩ +≡ ↑↓
  def mark_forced(bd):
      '''
      iteratively applies single candidate, hidden single, and rule of exclusion
      until no further modifications are possible
      '''
      fns = (mark_single_vals, mark_single_cells, mark_excluded)
      while any(fn(bd) for fn in fns): pass
      return bd

⟨bin/sudoku2tex⟩ ≡ 
  ⟨formatter usage⟩
  ⟨formatter imports⟩
  ⟨formatter functions⟩
  ⟨common⟩

⟨formatter usage⟩ ≡ 
  '''
  Usage: %s [OPTIONS] [HIGHLIGHT]...
  Given a Sudoku board, generate Latex source code.
  
  Options:
                  x
    -h, --help    print this help and exit
  
    -p            print pencil marks for all unknown cells
  
  Cells are numbered sequentially from 0 in row-major order. Each HIGHLIGHT 
  indicates a cell whose value (or pencil marks) will have its value surrounded
  by a red box; HIGHLIGHTs and any cell sharing a possible value with a HIGHLIGHT
  will have their possibilities set in red. In the absence of the -p option, only
  cells sharing a division with a HIGHLIGHT will be pencil marked.
  
  Used separately, the code generated by this program requires the sudokuii Latex 
  package, included in the source repository (as latex/sudokuii.sty).
  '''

\begin{sudoku}[2]
  |1|2|3|4|.
  |1|2|3|4|.
  |1|2|3|4|.
  |1|2|3|4|.
\end{sudoku}

⟨formatter functions⟩ ≡ ↓
  def sudoku_env(bd, pencil_marks, special):
      ncells = len(bd.known) + len(bd.unknown)
      order = int(ncells**0.25)
      n = order**2
      cells = [str(bd.known.get(i, ' ')) for i in range(ncells)]
  
      if pencil_marks: apply_pencils(bd, cells, order)
  
      reds = set()
      redboxes = set()
  
      for cell in special:
          dr, drb = highlight(cell, bd, cells, order)
          reds |= dr
          redboxes |= drb
  
      cells_fmtd = fmt_cells(cells, bd, reds, redboxes)
      grid = form_body(cells_fmtd, n)
      sudokusize = n/9 * (17 if pencil_marks or redboxes else 12)
      unitlength = sudokusize / n
      fboxsep = {2: 2, 3: 7, 4: 9}.get(order, 9) / 4 / n
  
      return f'''
      \\setlength\\sudokusize{{{sudokusize}cm}}
      \\setlength\\unitlength{{{1/n}\\sudokusize}}
      \\setlength\\fboxsep{{-{fboxsep}\\unitlength}}
      \\renewcommand\\sudokuformat[1]{{\\Huge\\sffamily#1}}
  
      \\begin{{sudoku}}[{order}]
      {grid}
      \\end{{sudoku}}
      '''
  
  def form_body(cells, n):
      rows = [cells[i*n : (i + 1) * n] for i in range(n)]
      lines = ['|%s|.' % '|'.join(row) for row in rows]
      return '\n'.join(lines)

⟨formatter functions⟩ +≡ ↑↓
  def pencils(possible, order):
      vals = [str(val) if val in possible else '.'
              for val in range(1, 1 + order**2)]
      coldesc = 'c' + 'c' * order
      grid = ' \\\\\n'.join(' & '.join(map(str, ['\\ \\ ']
                                           + vals[order*i : order*(i + 1)]))
                            for i in range(order))
  
      return f'''
      \\resizebox{{\\unitlength}}{{.6\\unitlength}}{{
      \\begin{{tabular}}{{{coldesc}}}
      \\ \\\\
      {grid} \\\\
      \\ \\\\
      \\end{{tabular}}
      }}
      '''
  
  def apply_pencils(bd, cells, order):
      for (unk, vals) in bd.unknown.items():
          cells[unk] = pencils(vals, order)

⟨formatter functions⟩ +≡ ↑↓
  def highlight(cell0, bd, cells, order):
      reds = set()
      redboxes = {cell0}
  
      for div in bd.cell2divs[cell0]:
          for cell in bd.div2cells[div] - set(bd.known):
              cells[cell] = pencils(bd.unknown[cell], order)
              if bd.unknown[cell0] & bd.unknown[cell]:
                  reds.add(cell)
      return reds, redboxes

⟨formatter functions⟩ +≡ ↑↓
  def fmt_cells(cells, bd, reds, redboxes):
      red = lambda s: '{\\color{red}%s}' % s
      redboxed = lambda s: '{\\color{red}\\fbox{%s}}' % s
      black = lambda s: '{\\color{black}%s}' % s
  
      return [redboxed(cell) if i in redboxes
              else red(cell) if i in reds
              else black(cell)
              for (i, cell) in enumerate(cells)]

⟨formatter imports⟩ ≡ 
  import getopt
  import sys
  import sudoku as sd

⟨formatter functions⟩ +≡ ↑
  def main(argv):
      try:
          opts_, args = getopt.gnu_getopt(argv, 'hp')
          special = {int(cell) for cell in args}
      except getopt.GetoptError: sys.exit(usage())
      except ValueError: sys.exit(usage())
  
      opts = dict(opts_)
      pencil_marks = '-p' in opts
  
      try:
          bd = sd.load_board(sys.stdin.read(), validate_vals=False)
      except ValueError:
          sys.exit('ill-formed board')
  
      not_special = set(special) & set(bd.known)
      if not_special:
          print("Won't hightlight known cells", not_special, file=sys.stderr)
          exit(1)
  
      print(sudoku_env(bd, pencil_marks, special))

⟨latex sudoku definitions⟩ ≡ ↓
  \renewenvironment{sudoku}[1][3]{
    \newcount\order
    \order = #1
    \newcount\n
    \n = \numexpr(#1*#1)
    \FPeval{\sudodelta}{1/#1/#1}
  
    \renewenvironment{sudoku-block}{
      \catcode`\|=\active
      \@sudoku@activate
      \setcounter{@sudoku@col}{-1}
      \setcounter{@sudoku@row}{\numexpr(\n-1)}
      \setlength\unitlength{\sudodelta\sudokusize}
      \begin{picture}(\n,\n)
        \@sudoku@grid\@sudoku@grab@arguments
    }{
      \end{picture}
    }
  
    \renewcommand*\@sudoku@grid{
      \linethickness{\sudokuthinline}
      \multiput(0,0)(1,0){\numexpr(\n+1)}{\line(0,1){\n}}
      \multiput(0,0)(0,1){\numexpr(\n+1)}{\line(1,0){\n}}
      \linethickness{\sudokuthickline}
      \multiput(0,0)(\order,0){\numexpr(\order+1)}{\line(0,1){\n}}
      \multiput(0,0)(0,\order){\numexpr(\order+1)}{\line(1,0){\n}}
      \linethickness{0.5\sudokuthickline}
      \put(0,0){\framebox(0,0){}}
      \put(\n,0){\framebox(0,0){}}
      \put(0,\n){\framebox(0,0){}}
      \put(\n,\n){\framebox(0,0){}}}
  
    \begin{center}
      \begin{sudoku-block}
  }{
      \end{sudoku-block}
    \end{center}
  }

⟨latex sudoku definitions⟩ +≡ ↑
  \def\@sudoku@grab@arguments#1.{
    \scantokens{#1.}}

⟨latex/sudokuii.sty⟩ ≡ 
  \NeedsTeXFormat{LaTeX2e}[1999/12/01]
  \ProvidesPackage{sudokuii}[2020/04/18 Big Sudoku]
  
  \RequirePackage{sudoku}
  \RequirePackage{fp}
  
  ⟨latex sudoku definitions⟩
  
  \endinput

⟨bin/sudoku2img⟩ ≡ 
  ⟨image converter functions⟩
  ⟨handle image converter arguments⟩
  ⟨image converter dispatch⟩

⟨image converter functions⟩ ≡ ↓
  function usage() {
      cat <<EOF
  Usage: `basename $0` [OPTIONS]
  Generate images from Sudoku boards or puzzles (i.e., paired boards and
  solutions, as produced by sudokugen).
  
  Options
    -h, --help  print this help and exit
  
    -P OUTDIR   generate images for a puzzle. Expected input is of the form
                produced by sudokugen. At conclusion, OUTDIR will contain:
  
                  - new.png       the unsolved board
                  - solved.png    the completed board
                  - penciled.png  the unsolved board with pencil marks applied
                  - input.txt     the original input
  
    --          indicates the end of options for `basename $0`; any remaining 
                arguments will be passed to sudoku2tex
  
  Input is taken from STDIN.
  EOF
  }

⟨image converter functions⟩ +≡ ↑↓
  function pipetex() {
      d=`mktemp -d`
      pushd $d >/dev/null
      {
          cat <<'EOF' > sudokuii.sty
   ⟨latex/sudokuii.sty⟩
  EOF
          pdflatex --jobname tmp >/dev/null
          [[ -f tmp.pdf ]] && cat tmp.pdf
      }
      popd > /dev/null
      rm -rf $d
  }

⟨image converter functions⟩ +≡ ↑↓
  function topng() { convert - -trim -transparent white -colorspace RGB png:-; }
  
  function tex2png() {
      cat <<EOF | pipetex | topng
  \documentclass[border=2pt,varwidth=\maxdimen]{standalone}
  \usepackage{graphics}
  \usepackage{sudokuii}
  \usepackage{xcolor}
  \usepackage{tcolorbox}
  
  \begin{document}
  \begin{varwidth}{\linewidth}
  \huge
  $(cat)
  \end{varwidth}
  \end{document}
  EOF
  }

⟨image converter functions⟩ +≡ ↑
  function convert_puzzle() {
      infile=$1
      outd=$2
      shift 2
  
      mkdir -p $outd
      cp $infile $outd/input.txt
      egrep    '>'    $infile | sudoku2tex "$@"    | tex2png > $outd/solved.png
      egrep -v '[:>]' $infile | sudoku2tex "$@"    | tex2png > $outd/new.png
      egrep -v '[:>]' $infile | sudoku2tex -p "$@" | tex2png > $outd/penciled.png
  }
  
  function convert_board() {
      sudoku2tex "$@" | tex2png
  }

⟨handle image converter arguments⟩ ≡ 
  while [[ "$1" ]]; do
      case "$1" in
          -h|--help)
              usage
              exit 0
              ;;
          -P)
              shift
              outd="$1"
              problem=1
              if ! [[ "$outd" ]]; then
                  echo "'-P' requires output directory"
                  usage
                  exit 1
              fi
              ;;
          --)
              shift
              break
              ;;
          *)
              echo unknown option "'$1'"
              usage
              exit 1
              ;;
      esac
      shift
  done

⟨image converter dispatch⟩ ≡ 
  tmpfile=`mktemp`
  cat > $tmpfile
  err=0
  
  if [[ "$problem" ]]; then
      convert_puzzle $tmpfile $outd "$@"
  elif grep -q difficulty $tmpfile; then
      echo 'sudokugen output detected; re-run with -P option.' >&2
      err=1
  else
      <$tmpfile convert_board "$@"
  fi
  
  rm -f $tmpfile
  exit $err