import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;

import java.util.StringTokenizer;
import java.util.BitSet;
import java.util.Arrays;
import java.util.Comparator;

/**
 * Implementation of two algorithms to solve Sudoku/Sodoku/S'doku puzzles.
 * <p>
 * (c) 2005 Frank Nestel
 * </p>
 * <p>
 * This Java class contains two straight forward implementations to solve
 * Sudokus. This is a plain commandline tool, no GUI whatever. Puzzles
 * are entered via a simple text format. However the contained API is 
 * rich and would allow to programm a GUI on top of this class to set up
 * a problem. Unfortunately I then got tired of it, so the solutions found
 * (algorithm does not stop with the first) a only reported to console :-(
 * </p>
 * <p>
 * The text format for sudoku puzzles uses (extended) coordinates to localize
 * settings, whitespaces and newlines all work as seperators. The famous
 * 17 hints Sudoku looks like this:
 * <pre>
        A11
        B22
        C33
        D44
        E55 E61 E72 E83 E94
        F66
        G77 G92 G84 G63
        H88
        I99 I18
 * </pre>
 * </p>
 * <p>
 * While this class does not contain any fiddly bit level opimisations and
 * is rather implemented in a abstract style, the second algorithm is 
 * sufficiently fast to solve any Sudoku I found so far in fractions of
 * a second on a stone agePentium III 500MHz.
 * </p>
 * <p>
 * More remarks: The algorithm and datastructures displayed should make it
 * to implement a Sudoku-Creator in a few hours (with nice symmetry conditions
 * and unique solution). The second, fast algorithm calculates a number as 
 * spin of which can be seen as a rough approximation of the complexity of
 * a puzzle. This would allow for a automagic classification of Sudokus in
 * terms of complexity. The formulare currently used for this has not been
 * tuned. It would require to feed a bunch of Sudoku of know complexity, to
 * observe this data and then to create an optimum approximation.
 * </p>
 * 
 */
public class Sudoku
    implements Cloneable
{
    // XXX While these parameters suggest generality, 9x9x9 seems to be
    // built in here and there
    private final static int DIMI = 3;
    private final static int MAXVALUE = DIMI*DIMI;
    private final static int DIMX = 9;
    private final static int DIMY = 9;
    private final static BitSet FIXED_ALLSET = newAllSet();

    /**
     * Represent an "decided" field which has everything forbidden but one.
     */
    private static BitSet[] ONESETS = new BitSet[MAXVALUE];

    private static int[][] connects = new int [DIMX * DIMY][DIMX - 1 + DIMY - 1 + (DIMI-1)*(DIMI-1)];

    static 
    {
        for(int i = 0; i < MAXVALUE; i++)
        {
            ONESETS[i] = new BitSet(MAXVALUE);
            ONESETS[i].set(i);
        }
        // Build the topology of the net
        for(int i = 0; i < connects.length; i++)
        {
            int j = 0;
            int pix = i % DIMX;
            int piy = i / DIMX;
            for(int k = 0; k < connects.length; k++)
            {   
                int pkx = k % DIMX;
                int pky = k / DIMX;
                if ( ( pkx == pix ) || ( pky == piy )
                    || ( ( pix/3 == pkx/3 ) && ( piy/3 == pky/3 ) )
                    )
                {
                    if ( k != i )
                    {
                        connects[i][j++] = k;
                    }
                }
            }
            if ( j != connects[i].length )
            {
                System.err.println("Setup problem "+square(i)+" c="+j);
            }
        }
    }

    private BitSet[] allows = new BitSet[DIMX * DIMY];

    public Sudoku()
    {
    }

    /**
     * @return null when everything is OK. Errormessage otherwise.
     */
    public String set(String target)
    {
        char xc = Character.toLowerCase(target.charAt(0));
        if ( xc < 'a' || xc > 'i' )
            return "Illegal x="+xc+"@"+target;
        char yc = target.charAt(1);
        if ( yc < '1' || yc > '9' )
            return "Illegal y="+yc+"@"+target;
        char vc = target.charAt(2);
        if ( vc < '1' || vc > '9' )
            return "Illegal v="+vc+"@"+target;
        int pos = ( xc - 'a' ) + DIMX * ( yc - '1' );
        return set(pos, vc - '1');
    }

    private String set(int pos, int value)
    {
        if ( allows[pos] != null && !allows[pos].get(value) )
            return "Forbidden setting "+square2(pos,value);
        allows[pos] = ONESETS[value];
        int[] con = connects[pos];
        for(int i = 0; i < con.length; i++)
        {
            int p = con[i];
            // We initialize lazyly!
            BitSet curSet = allows[p];
            if ( curSet == null )
            {
                allows[p] = curSet = newAllSet();
            }
            if ( curSet.get(value) && curSet.cardinality() == 1 )
                return "Impossible on "+square(p)+" due to "+square2(pos,value);
            curSet.clear(value);
        }
        return null;
    }

    public SudokuSolver solver()
    {
        return new SudokuSolver(this);
    }

    public static class SudokuSolver
    {
        private Sudoku root;

        private int count = 0;

        private long t0;

        public SudokuSolver(Sudoku root)
        {
            this.root = root;
        }

        public void solve()
        {
            count = 0;
            t0 = System.currentTimeMillis();
            recurse(0, root);
        }

        public void smartSolve()
        {
            count = 0;
            t0 = System.currentTimeMillis();
            Integer[] tasks = new Integer[DIMX * DIMY];
            for(int i = 0; i < tasks.length; i++)
                tasks[i] = new Integer(i);
            smartRecurse(0, tasks, root, 0, 0, 0);
        }

        public int getCount()
        {
            return count;
        }

        private void smartRecurse(int nr, Integer[] tasks, Sudoku pred,
                                            int choice, int times, int width)
        {
            if ( nr >= connects.length )
            {
                long t1 = System.currentTimeMillis();
                prettyPrint((++count)+"["+choice+"/"+width+"/"+times+" ==> estimated complexity="+((int)(16.0*choice*times/Math.sqrt(width)))+"].("+(t1-t0)+"ms)",pred);
                return;
            }
            int pos = tasks[nr].intValue();
            if ( pred.allows[pos].cardinality() > 1 )
            {
                Arrays.sort(tasks, nr, tasks.length,
                                        new CardinalityComparator(pred));
                pos = tasks[nr].intValue();
            }
            int card = pred.allows[pos].cardinality();
            choice += card - 1;
            if ( card > 1 )
                times++;
            for(int i = nr + 1; i < connects.length && pred.allows[i].cardinality() == card; i++ )
                width++;
            BitSet me = pred.allows[pos];
            if ( me == null ) me = FIXED_ALLSET;
            int[] con = connects[pos];
        outerLoop:
            for(int v = me.nextSetBit(0); v >= 0; v = me.nextSetBit(v+1))
            {
                Sudoku deep = new Sudoku();
                int k = 0;
                for(int j = 0; j < connects.length; j++)
                {
                    if ( j == pos )
                    {
                        deep.allows[j] = ONESETS[v];
                    }
                    else if ( k >= con.length || j < con[k] ) 
                    {
                        deep.allows[j] = pred.allows[j];
                    }
                    else
                    {
                        BitSet curSet = pred.allows[j];
                        if ( curSet == null )
                        {
                            deep.allows[j] = newAllSet();
                        }
                        else
                        {
                            if ( curSet.get(v) && (curSet.cardinality() == 1) )
                            {
                                continue outerLoop;
                            }
                            deep.allows[j] = (BitSet) curSet.clone();
                        }
                        deep.allows[j].clear(v);
                        k++;
                    }
                }
                smartRecurse(nr+1, tasks, deep, choice, times, width);
            }
        }

        private void recurse(int pos, Sudoku pred)
        {
            if ( pos >= connects.length )
            {
                long t1 = System.currentTimeMillis();
                prettyPrint((++count)+".("+(t1-t0)+"ms)",pred);
                return;
            }
            BitSet me = pred.allows[pos];
            if ( me == null ) me = FIXED_ALLSET;
            int[] con = connects[pos];
        outerLoop:
            for(int v = me.nextSetBit(0); v >= 0; v = me.nextSetBit(v+1))
            {
                Sudoku deep = new Sudoku();
                int k = 0;
                for(int j = 0; j < connects.length; j++)
                {
                    if ( j == pos )
                    {
                        deep.allows[j] = ONESETS[v];
                    }
                    else if ( k >= con.length || j < con[k] ) 
                    {
                        deep.allows[j] = pred.allows[j];
                    }
                    else
                    {
                        BitSet curSet = pred.allows[j];
                        if ( curSet == null )
                        {
                            deep.allows[j] = newAllSet();
                        }
                        else
                        {
                            if ( curSet.get(v) && (curSet.cardinality() == 1) )
                            {
                                continue outerLoop;
                            }
                            deep.allows[j] = (BitSet) curSet.clone();
                        }
                        deep.allows[j].clear(v);
                        k++;
                    }
                }
                recurse(pos+1, deep);
            }
        }

    }

    public static void main(String args[])
        throws IOException
    {
problemLoop:    
        for(int i = 0; i < args.length; i++)
        {
            System.out.println("***"+args[i]+":");
            Sudoku sudoku = new Sudoku();
            BufferedReader br = new BufferedReader(new FileReader(args[i]));
            String line;
            while ( ( line = br.readLine() ) != null )
            {
                if ( line.length() == 0 || line.charAt(0) == '#' )
                    continue;
                StringTokenizer st = new StringTokenizer(line, " ");
                while ( st.hasMoreTokens() )
                {
                    String token = st.nextToken();
                    String err = sudoku.set(token);
                    if ( err != null )
                    {
                        System.out.println("    "+err);
                        continue problemLoop;
                    }
                }
            }
            SudokuSolver solver = sudoku.solver();
            solver.solve();
            solver.smartSolve();
        }
    }

    public static BitSet newAllSet()
    {
        BitSet res = new BitSet(MAXVALUE);
        res.set(0,MAXVALUE);
        return res;
    }

    public static String square(int pos)
    {
        return ((char)('a' + (pos % DIMX)))+""+((char)('1' + (pos / DIMX)));
    }

    public static String square2(int pos, int value)
    {
        return square(pos)+((char)('1'+value));
    }

    public Object clone()
    {
        Sudoku res = new Sudoku();
        for(int i = 0; i < allows.length; i++)
        {
            res.allows[i] = (BitSet) this.allows[i].clone();
        }
        return res;
    }

    public static void prettyPrint(String msg, Sudoku sudoku)
    {
        System.out.println("    "+msg+":");
        for(int y = DIMY-1; y >= 0; y--)
        {
            System.out.print("        ");
            for(int x = 0; x < DIMX; x++)
            {
                int pos = x + DIMX * y;
                BitSet curSet = sudoku.allows[pos];
                char v;
                if ( curSet == null )
                    v = '?';
                else if ( curSet.cardinality() > 1 )
                    v = '.';
                else
                    v = (char)('1'+curSet.nextSetBit(0));
                System.out.print(v);
                if ( x % DIMI == DIMI - 1 && x+1 < DIMX )
                    System.out.print('|');
            }
            System.out.println();
            if ( y % DIMI == 0 && y > 0 )
            {
                System.out.print("        ");
                for(int x = 0; x < DIMX; x++)
                {
                    System.out.print('-');
                    if ( x % DIMI == DIMI - 1 && x+1 < DIMX )
                        System.out.print('+');
                }
                System.out.println();
            }
        }
    }

    public static class CardinalityComparator
        implements Comparator
    {
        Sudoku sdk;

        public CardinalityComparator(Sudoku sdk)
        {
            this.sdk = sdk;
        }

        public int compare(Object o1, Object o2)
        {
            int p1 = ((Integer)o1).intValue();
            int p2 = ((Integer)o2).intValue();
            int h = sdk.allows[p1].cardinality() - sdk.allows[p2].cardinality();
            if ( h == 0 )
            {
                h = p1 - p2;
            }
            return h;
        }
    }
}