Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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));
- }
- }
RAW Paste Data