mystiques

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'); }
  110.             result.add(new String(resLine));
  111.             }
  112.             ++n; --i; dir = -1; // backtrack
  113.         }
  114.         return n;
  115.     }
  116.    
  117.     private final char[] resLine = new char[82];
  118.     private long readTime;
  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"));
  124.         readTime = System.nanoTime();
  125.         for(String l; (l = in.readLine()) != null && l.length()>0; lines.add(l));
  126.         readTime = System.nanoTime()-readTime;
  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]);
  136.         ArrayList<String> lines = a.read(stdin);
  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));
  169.         System.out.printf("Elapsed+Read: %.2f%n", BigDecimal.valueOf(elapsed+a.readTime, 6));
  170.     }
  171. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×