- package chu;
- import java.util.ArrayList;
- /**
- * @author chufazheng@gmail.com
- * update: 2014-11-26
- */
- public final class SudokuSolver {
- private ArrayList<Integer> blank;
- private ArrayList<Integer> fixed;
- private ArrayList<TrialPoint> trials;
- private int[] cell = new int[81];
- public static void main(String[] arg) {
- String str;
- if (arg != null && arg.length > 0 && arg[0].length() >= 81) {
- str = arg[0];
- } else {
- //str="000000500000008300600100000080093000000000020700000000058000000000200017090000060";//the least given
- str = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";//the world hardest
- }
- SudokuSolver game = new SudokuSolver();
- game.load(str);
- game.solve();
- }
- public void solve() {
- if (fixed.size() < 17) {
- System.out.println("Invalid game!");
- System.exit(0);
- }
- showBoard(true);
- long start = System.currentTimeMillis();
- if (!basicSolve()) {
- trialSolve();
- }
- long end = System.currentTimeMillis();
- showBoard(false);
- if (check()) {
- System.out.println("[" + (end - start) + "ms OK!]");
- } else {
- System.out.println("[" + (end - start) + "ms, cannot solve it, are you sure it has solution?");
- }
- }
- public SudokuSolver() {
- blank = new ArrayList();
- fixed = new ArrayList();
- trials = new ArrayList();
- }
- public void load(String str) {
- blank.clear();
- fixed.clear();
- char[] chr = str.toCharArray();
- int i = 0, j = 0, len = chr.length;
- while (i < len && j < 81) {
- if (Character.isDigit(chr[i])) {
- if (chr[i] == '0') {
- cell[j] = 0x1FF;
- blank.add(j);
- } else {
- cell[j] = 1 << chr[i] - 49;
- fixed.add(j);
- }
- j++;
- }
- i++;
- }
- //if the numbers input less than 81, add '0's.
- for (;j < 81; j++) {
- cell[j] = 0x1FF;
- blank.add(j);
- }
- }
- private void reset(int[] data) {
- blank.clear();
- fixed.clear();
- System.arraycopy(data, 0, cell, 0, 81);
- for (int i = 0; i < 81; i++) {
- if (Integer.bitCount(cell[i]) != 1) {
- blank.add(i);
- } else {
- fixed.add(i);
- }
- }
- }
- private void showCell(int idx, boolean hide) {
- if (hide) {
- if (Integer.bitCount(cell[idx]) == 1) {
- System.out.print("[" + (Integer.numberOfTrailingZeros(cell[idx]) + 1) + "]");
- } else {
- System.out.print("[ ]");
- }
- } else {
- StringBuilder sb = new StringBuilder();
- sb.append('[');
- for (int i = 0; i < 9; i++) {
- if ((cell[idx] >>> i & 1) == 1) {
- sb.append(i + 1);
- }
- }
- sb.append(']');
- System.out.print(sb);
- }
- }
- private void showBoard(boolean hide) {
- System.out.print("---------------------------");
- for (int i = 0; i < 81; i++) {
- if (i % 9 == 0) {
- System.out.print("\\n");
- }
- showCell(i, hide);
- }
- System.out.println("\\n---------------------------");
- }
- private boolean updateCandidates(ArrayList<Integer> fixed) {
- for (int i : fixed) {
- int opt = 0x1FF ^ cell[i];
- for (int j : X(i)) {
- cell[j] &= opt;
- //!notice
- if (cell[j] == 0) {
- return false;
- }
- }
- }
- return true;
- }
- private void seekFixedable() {
- fixed.clear();
- for (int i : blank) {
- if (Integer.bitCount(cell[i]) == 1) {
- fixed.add(i);
- //System.out.println("fixed:"+i+"=>"+cell[i]);
- }
- }
- blank.removeAll(fixed);
- }
- private boolean check() {
- int[] checkpoint = new int[]{0, 12, 24, 28, 40, 52, 56, 68, 80};
- for (int i : checkpoint) {
- int r, b, c;
- r = b = c = cell[i];
- for (int j = 0; j < 8; j++) {
- r ^= cell[X(i)[j]];
- c ^= cell[X(i)[8 + j]];
- b ^= cell[X(i)[16 + j]];
- }
- if ((r & b & c) != 0x1FF) {
- return false;
- }
- }
- return true;
- }
- private void seekUniqueCandidate() {
- for (int cel_idx : blank) {
- int row = 0, col = 0, box = 0;
- for (int i = 0; i < 8; i++) {
- row |= cell[X(cel_idx)[i]];
- col |= cell[X(cel_idx)[8 + i]];
- box |= cell[X(cel_idx)[16 + i]];
- }
- if (Integer.bitCount(cell[cel_idx] & ~row) == 1) {
- cell[cel_idx] &= ~row;
- continue;
- }
- if (Integer.bitCount(cell[cel_idx] & ~col) == 1) {
- cell[cel_idx] &= ~col;
- continue;
- }
- if (Integer.bitCount(cell[cel_idx] & ~box) == 1) {
- cell[cel_idx] &= ~box;
- }
- }
- }
- private void seekMutexCell() {
- ArrayList<Integer> two = new ArrayList();
- for (int i : blank) {
- if (Integer.bitCount(cell[i]) == 2) {
- two.add(i);
- }
- }
- for (int i = 0; i < two.size(); i++) {
- for (int j = i + 1; j < two.size(); j++) {
- if (cell[two.get(i)] == cell[two.get(j)]) {
- int opt = ~cell[two.get(i)];
- if (two.get(i) / 9 == two.get(j) / 9) {//same row
- for (int n = 0; n < 8; n++) {
- cell[X(two.get(i))[n]] &= opt;
- }
- }
- if ((two.get(i) - two.get(j)) % 9 == 0) {//same col
- for (int n = 8; n < 16; n++) {
- cell[X(two.get(i))[n]] &= opt;
- }
- }
- if ((two.get(i) / 27 * 3 + two.get(i) % 9 / 3) == (two.get(j) / 27 * 3 + two.get(j) % 9 / 3)) {//same box
- for (int n = 16; n <24; n++) {
- cell[X(two.get(i))[n]] &= opt;
- }
- }
- cell[two.get(j)] = ~opt;
- }
- }
- }
- }
- private boolean basicSolve() {
- do {
- if (!updateCandidates(fixed)) {
- backForward();
- }
- seekUniqueCandidate();
- seekMutexCell();
- seekFixedable();
- } while (!fixed.isEmpty());
- return blank.isEmpty();
- }
- private boolean setTrialCell() {
- for (int i : blank) {
- if (Integer.bitCount(cell[i]) == 2) {
- int trialValue = 1 << Integer.numberOfTrailingZeros(cell[i]);
- int waitingValue = cell[i] ^ trialValue;
- //System.out.println("Try:[" + i + "]->" + (Integer.numberOfTrailingZeros(trialValue) + 1) + "#" + (Integer.numberOfTrailingZeros(waitingValue) + 1));
- cell[i] = trialValue;
- trials.add(new TrialPoint(i, waitingValue, cell));
- return true;
- }
- }
- return false;
- }
- private void backForward() {
- if (trials.isEmpty()) {
- System.out.println("Can not go backforword, no trial point, maybe no solution!");
- return;
- }
- TrialPoint back = trials.get(trials.size() - 1);
- trials.remove(back);
- reset(back.cel);
- cell[back.idx] = back.val;
- fixed.add(back.idx);
- //System.out.println("Back:[" + back.idx + "]->" + (Integer.numberOfTrailingZeros(back.val) + 1));
- }
- private void trialSolve() {
- while (!blank.isEmpty()) {
- if (setTrialCell()) {
- basicSolve();
- } else {
- if (trials.isEmpty()) {
- //System.out.println("Maybe no solution.");
- break;
- } else {
- backForward();
- basicSolve();
- }
- }
- }
- }
- private int[] X(int idx){
- int neighbors[]=new int[24];
- int box[]=new int[]{0,1,2,9,10,11,18,19,20};
- int r=idx/9,c=idx%9,xs=idx/27*27+idx%9/3*3;
- int i=0;
- for(int n=0;n<9;n++){
- if(n==c)continue;
- neighbors[i++]=r*9+n;
- }
- for(int n=0;n<9;n++){
- if(n==r)continue;
- neighbors[i++]=c+n*9;
- }
- for(int n=0;n<9;n++){
- int t=xs+box[n];
- if(t==idx)continue;
- neighbors[i++]=t;
- }
- return neighbors;
- }
- }
- final class TrialPoint {
- public int idx;
- public int val;
- public int[] cel = new int[81];
- public TrialPoint(int i, int v, int[] board) {
- idx = i;
- val = v;
- System.arraycopy(board, 0, cel, 0, 81);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/0707201614810.html
来源: http://www.codesnippet.cn/detail/0707201614810.html