Sudoku

package s;

import java.io.DataInputStream;
import java.io.IOException;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

class Sudoku {
    private final static short[][] R, C;//those should be static final to allow aggressive optimizations on
    public void genmat() {
        resLine[resLine.length-1]='\n';
    }
    static {
        R = new short[324][9];
        C = new short[729][4];
        int[] nr = new int[324];

        for (int i =0, r = 0; i < 9; ++i) // generate c[729][4]
            for (int j = 0; j < 9; ++j)
                for (int k = 0; k < 9 && r<C.length; ++k, r++) { // this "9" means each cell has 9 possible numbers
                    C[r][0] = (short)(9 * i + j); // row-column constraint
                    C[r][1] = (short)((i/3*3 + j/3) * 9 + k + 81); // box-number constraint
                    C[r][2] = (short)(9 * i + k + 162); // row-number constraint
                    C[r][3] = (short)(9 * j + k + 243); // col-number constraint

                }
        for (short r = 0; r < C.length; ++r) // generate r[][] from c[][]
            for (int c2 = 0; c2 < 4; ++c2) {
                int k = C[r][c2]; R[k][nr[k]++] = r;
            }
    }
    private int sd_update(int[] sr, int[] sc, final int r, int v) {
        int min = 10, min_c = 0;
        final short[] row = C[r];
        for (int c2 = 0; c2 < 4; ++c2) sc[row[c2]] += v<<7;
        for (int c2 = 0; c2 < 4; ++c2) { // update # available choices
            int rr;
            final int c = row[c2];
            final short[] rc = R[c];
            if (v > 0) { // move forward
                for (int r2 = 0; r2 < 9; ++r2) {
                    if (sr[rr = rc[r2]]++ != 0) continue; // update the row status
                    short[] crr=C[rr];
                    for (int cc2 = 0; cc2 < 4; ++cc2) {
                        int cc = crr[cc2];
                        if (--sc[cc] < min) { // update # allowed choices
                            min = sc[cc]; min_c = cc; // register the minimum number
                        }
                    }
                }
            } else { // revert
                for (int r2 = 0; r2 < rc.length; ++r2) {
                    if (--sr[rr = rc[r2]] != 0) continue; // update the row status
                    short[] p = C[rr]; ++sc[p[0]]; ++sc[p[1]]; ++sc[p[2]]; ++sc[p[3]]; // update the count array
                }
            }
        }
        return min<<16 | min_c; // return the col that has been modified and with the minimal available choices
    }
    // solve a Sudoku; _s is the standard dot/number representation
    public int solve(String _s, Collection<String> result) {
        int r2, n = 0, hints = 0; // dir=1: forward; dir=-1: backtrack
        int[] sr = new int[729];
        int[] cr = new int[81];
        int[] sc = new int[324];
        int[] cc = new int[81];
        char[] out = new char[81];
        Arrays.fill(sc, 9);
        for (int i = 0, len=Math.min(_s.length(), 81); i < len; ++i) {
            int a = _s.charAt(i) >= '1' && _s.charAt(i) <= '9'? _s.codePointAt(i) - '1' : -1; // number from -1 to 8
            if (a >= 0) {
                sd_update(sr, sc, i * 9 + a, 1); // set the choice
                ++hints; // count the number of hints
            }
            cr[i] = cc[i] = -1; out[i] = (char)a;
        }
        int dir = 1, cand = 10<<16|0;
        for (int i=0;;) {
            while (i >= 0 && i < cr.length - hints) { // maximum 81-hints steps
                if (dir == 1) {
                    int min = cand>>>16; cc[i] = cand&0xffff;
                    if (min > 1) {
                        for (int c = 0; c < sc.length; ++c) {
                            int m = sc[c];
                            if (m < min) {
                                min = m; cc[i] = c; // choose the top constraint
                                if (min <= 1) break; // this is for acceleration; slower without this line
                            }
                        }
                    }
                    if (min == 0 || min == 10) cr[i--] = dir = -1; // backtrack
                }
                int c = cc[i];
                final short[] resultRef = R[c];
                if (dir == -1 && cr[i] >= 0) sd_update(sr, sc, resultRef[cr[i]], -1); // revert the choice
                for (r2 = cr[i] + 1; r2 < 9; ++r2) // search for the choice to make
                    if (sr[resultRef[r2]] == 0) break; // found if the state equals 0
                if (r2 < 9) {
                    cand = sd_update(sr, sc, resultRef[r2], 1); // set the choice
                    cr[i++] = r2; dir = 1; // moving forward
                } else cr[i--] = dir = -1; // backtrack
            }
            if (i < 0) break;
            {
            char[] resLine = this.resLine;
            for (int j = 0; j < out.length; ++j) resLine[j] = (char)(out[j] + '1');
            for (int j = 0; j < i; ++j) {int  r = R[cc[j]][cr[j]]; resLine[r/9] = (char)(r%9 + '1'); }
            result.add(new String(resLine));
            }
            ++n; --i; dir = -1; // backtrack
        }
        return n;
    }

    private final char[] resLine = new char[82];
    private long readTime;
    @SuppressWarnings("deprecation")
    private ArrayList<String> read(boolean stdin) throws IOException{
        ArrayList<String> lines =new ArrayList<String>(32);
        //Since not reading anything but ASCII DataInputStream is fine
        DataInputStream in = new DataInputStream(stdin?System.in : getClass().getResourceAsStream("sudoku.txt"));
        readTime = System.nanoTime();
        for(String l; (l = in.readLine()) != null && l.length()>0; lines.add(l));
        readTime = System.nanoTime()-readTime;

        in.close();
        return lines;

    }

    public static void main(String[] args) throws Exception {
        Sudoku a = new Sudoku();
        boolean stdin=args.length>0 && "in".equals(args[0]);
        ArrayList<String> lines = a.read(stdin);
        a.genmat();
        System.out.printf("reading from stdin: %s%n", stdin);
        final int warmup=Integer.getInteger("warmup", 2000);
        ArrayList<String> result =new ArrayList<String>(warmup*lines.size());
        for (int i=0, w=warmup;i<warmup;i++){
        for (String l : lines)
            if (l.length() >= 81) {
                a.solve(l, result);
                if (--w==0);
                break;
            }
        }
        int iter = stdin?1:50;
        result =new ArrayList<String>(iter*lines.size());
        System.out.printf("<<<No compilation past here, can test -XX:+PrintCompilation>>>%n");

        //Thread.sleep(10);, for long tests won't matter for sub sec - (attempt at) giving full quant is a good idea
        long started = System.nanoTime();
        for (int i=0;i<iter;i++){
        for (String l : lines)
            if (l.length() >= 81) {
                a.solve(l, result);
            }
        }



        for (String line : result.subList(0, result.size()/1)){
            System.out.println(line);
        }
        long elapsed = System.nanoTime() - started;
        System.out.printf("Elapsed: %.2f%n", BigDecimal.valueOf(elapsed, 6));
        System.out.printf("Elapsed+Read: %.2f%n", BigDecimal.valueOf(elapsed+a.readTime, 6));
    }
}