sudz - 3x3 sudoku minlex solution grid compressor

  sudz [ options ] [ file ... ]

  sudz is a 3x3 sudoku minlex solution grid compressor. If no file operands
  are specified, or if a file is -, then the standard input is read.

  -aN  List grids with >= N automorphisms.
  -fF  Format output according to F (default '%03b %3a %g') for each grid.
       printf(3) style width and fill apply.  The formats are:
        %a  The number of automorphisms in the range 1..648 inclusive.
        %b  The band index in the range 1..416 inclusive.
        %g  The grid in 81 char row order form.
        %i  The grid index in the range 1..5472730538 inclusive.
        %w  The number of grids in the current window.
  -i   List the window information using the default format '%10i %03b %6w %g'.
       Grid information is for the first grid in the window.
  -oF  Write output to the file F instead of the standard output.
  -u   Uncompress the input to the standard output.  This is the default.
  -w   Compress the input to the output.  The input must be lines containing
       the space separated fields: band index, number of automorphisms, and
       the 81 char row order minlex-solution-grid.  The input must be sorted
       by the minlex-solution-grid field in ascending order (or the compression
       rate will deteriorate).

  A minlex solution grid (a.k.a. row order minlex canonical solution grid)
  is a solution grid with values, rows and columns permuted to yield the
  smallest lexicographic row order value.  Grids are organized by the top band
  (top 3 rows).  There are 416 essentially different minlex bands and 5472730538
  essentially different grids.  A byproduct of minlex ordering is that earlier
  bands tend to account for more grids than later bands.  For example, band 001
  contains 1007170 grids, band 006 (the largest) contains 96229042 grids, and
  bands 395,397,398,400,402,403,404,406,408,409,410,412,413,414,415 contain no

  The compression format stores the number of grids and initial band index for
  each window.  Each grid has the band index (if different from the previous
  grid), the number of automorphisms (if > 1), the number of cells that differ
  from the previous grid, and the list of differing cell values encoded using a
  basic singles constraint solver.  The data is compressed using a combination
  of Burrows-Wheeler, move-to-front, run-length, and huffman encoding.

  The entire catalog of 5472730538 essentially different grids, in minlex
  order, compresses to 5.34GiB, or 8.38 bits/grid.  Uncompress rate is
  ~100K grids/sec/Ghz, or ~5 hours minimum to stream through the entire
  catalog on a 2.8Ghz processor.

  sudoku(1), bzlib(3)

  Subgrid (multiple solution) row order minlex canonicalizer by Michael Deverin.

  version     sudz (AT&T Research) 2007-02-14
  author      Glenn Fowler 
  copyright   Copyright (c) 2007-2009 AT&T Knowledge Ventures