# Sudoku

Apr 7th, 2013
109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. package s;
2.
3. import java.io.DataInputStream;
4. import java.io.IOException;
5. import java.math.BigDecimal;
6. import java.util.ArrayList;
7. import java.util.Arrays;
8. import java.util.Collection;
9.
10. class Sudoku {
11.     private final static short[][] R, C;//those should be static final to allow aggressive optimizations on
12.     public void genmat() {
13.         resLine[resLine.length-1]='\n';
14.     }
15.     static {
16.         R = new short[324][9];
17.         C = new short[729][4];
18.         int[] nr = new int[324];
19.
20.         for (int i =0, r = 0; i < 9; ++i) // generate c[729][4]
21.             for (int j = 0; j < 9; ++j)
22.                 for (int k = 0; k < 9 && r<C.length; ++k, r++) { // this "9" means each cell has 9 possible numbers
23.                     C[r][0] = (short)(9 * i + j); // row-column constraint
24.                     C[r][1] = (short)((i/3*3 + j/3) * 9 + k + 81); // box-number constraint
25.                     C[r][2] = (short)(9 * i + k + 162); // row-number constraint
26.                     C[r][3] = (short)(9 * j + k + 243); // col-number constraint
27.
28.                 }
29.         for (short r = 0; r < C.length; ++r) // generate r[][] from c[][]
30.             for (int c2 = 0; c2 < 4; ++c2) {
31.                 int k = C[r][c2]; R[k][nr[k]++] = r;
32.             }
33.     }
34.     private int sd_update(int[] sr, int[] sc, final int r, int v) {
35.         int min = 10, min_c = 0;
36.         final short[] row = C[r];
37.         for (int c2 = 0; c2 < 4; ++c2) sc[row[c2]] += v<<7;
38.         for (int c2 = 0; c2 < 4; ++c2) { // update # available choices
39.             int rr;
40.             final int c = row[c2];
41.             final short[] rc = R[c];
42.             if (v > 0) { // move forward
43.                 for (int r2 = 0; r2 < 9; ++r2) {
44.                     if (sr[rr = rc[r2]]++ != 0) continue; // update the row status
45.                     short[] crr=C[rr];
46.                     for (int cc2 = 0; cc2 < 4; ++cc2) {
47.                         int cc = crr[cc2];
48.                         if (--sc[cc] < min) { // update # allowed choices
49.                             min = sc[cc]; min_c = cc; // register the minimum number
50.                         }
51.                     }
52.                 }
53.             } else { // revert
54.                 for (int r2 = 0; r2 < rc.length; ++r2) {
55.                     if (--sr[rr = rc[r2]] != 0) continue; // update the row status
56.                     short[] p = C[rr]; ++sc[p[0]]; ++sc[p[1]]; ++sc[p[2]]; ++sc[p[3]]; // update the count array
57.                 }
58.             }
59.         }
60.         return min<<16 | min_c; // return the col that has been modified and with the minimal available choices
61.     }
62.     // solve a Sudoku; _s is the standard dot/number representation
63.     public int solve(String _s, Collection<String> result) {
64.         int r2, n = 0, hints = 0; // dir=1: forward; dir=-1: backtrack
65.         int[] sr = new int[729];
66.         int[] cr = new int[81];
67.         int[] sc = new int[324];
68.         int[] cc = new int[81];
69.         char[] out = new char[81];
70.         Arrays.fill(sc, 9);
71.         for (int i = 0, len=Math.min(_s.length(), 81); i < len; ++i) {
72.             int a = _s.charAt(i) >= '1' && _s.charAt(i) <= '9'? _s.codePointAt(i) - '1' : -1; // number from -1 to 8
73.             if (a >= 0) {
74.                 sd_update(sr, sc, i * 9 + a, 1); // set the choice
75.                 ++hints; // count the number of hints
76.             }
77.             cr[i] = cc[i] = -1; out[i] = (char)a;
78.         }
79.         int dir = 1, cand = 10<<16|0;
80.         for (int i=0;;) {
81.             while (i >= 0 && i < cr.length - hints) { // maximum 81-hints steps
82.                 if (dir == 1) {
83.                     int min = cand>>>16; cc[i] = cand&0xffff;
84.                     if (min > 1) {
85.                         for (int c = 0; c < sc.length; ++c) {
86.                             int m = sc[c];
87.                             if (m < min) {
88.                                 min = m; cc[i] = c; // choose the top constraint
89.                                 if (min <= 1) break; // this is for acceleration; slower without this line
90.                             }
91.                         }
92.                     }
93.                     if (min == 0 || min == 10) cr[i--] = dir = -1; // backtrack
94.                 }
95.                 int c = cc[i];
96.                 final short[] resultRef = R[c];
97.                 if (dir == -1 && cr[i] >= 0) sd_update(sr, sc, resultRef[cr[i]], -1); // revert the choice
98.                 for (r2 = cr[i] + 1; r2 < 9; ++r2) // search for the choice to make
99.                     if (sr[resultRef[r2]] == 0) break; // found if the state equals 0
100.                 if (r2 < 9) {
101.                     cand = sd_update(sr, sc, resultRef[r2], 1); // set the choice
102.                     cr[i++] = r2; dir = 1; // moving forward
103.                 } else cr[i--] = dir = -1; // backtrack
104.             }
105.             if (i < 0) break;
106.             {
107.             char[] resLine = this.resLine;
108.             for (int j = 0; j < out.length; ++j) resLine[j] = (char)(out[j] + '1');
109.             for (int j = 0; j < i; ++j) {int  r = R[cc[j]][cr[j]]; resLine[r/9] = (char)(r%9 + '1'); }
111.             }
112.             ++n; --i; dir = -1; // backtrack
113.         }
114.         return n;
115.     }
116.
117.     private final char[] resLine = new char[82];
119.     @SuppressWarnings("deprecation")
120.     private ArrayList<String> read(boolean stdin) throws IOException{
121.         ArrayList<String> lines =new ArrayList<String>(32);
122.         //Since not reading anything but ASCII DataInputStream is fine
123.         DataInputStream in = new DataInputStream(stdin?System.in : getClass().getResourceAsStream("sudoku.txt"));
127.
128.         in.close();
129.         return lines;
130.
131.     }
132.
133.     public static void main(String[] args) throws Exception {
134.         Sudoku a = new Sudoku();
135.         boolean stdin=args.length>0 && "in".equals(args[0]);
137.         a.genmat();
138.         System.out.printf("reading from stdin: %s%n", stdin);
139.         final int warmup=Integer.getInteger("warmup", 2000);
140.         ArrayList<String> result =new ArrayList<String>(warmup*lines.size());
141.         for (int i=0, w=warmup;i<warmup;i++){
142.         for (String l : lines)
143.             if (l.length() >= 81) {
144.                 a.solve(l, result);
145.                 if (--w==0);
146.                 break;
147.             }
148.         }
149.         int iter = stdin?1:50;
150.         result =new ArrayList<String>(iter*lines.size());
151.         System.out.printf("<<<No compilation past here, can test -XX:+PrintCompilation>>>%n");
152.
153.         //Thread.sleep(10);, for long tests won't matter for sub sec - (attempt at) giving full quant is a good idea
154.         long started = System.nanoTime();
155.         for (int i=0;i<iter;i++){
156.         for (String l : lines)
157.             if (l.length() >= 81) {
158.                 a.solve(l, result);
159.             }
160.         }
161.
162.
163.
164.         for (String line : result.subList(0, result.size()/1)){
165.             System.out.println(line);
166.         }
167.         long elapsed = System.nanoTime() - started;
168.         System.out.printf("Elapsed: %.2f%n", BigDecimal.valueOf(elapsed, 6));