数独解法Java实现

早先做过用OpenCV识别数独数字,然后解出,因为主要是为了用OpenCV实现识别部分,因此解法就从网上搬了一个。结果识别能行了,发现不是所有的数独都能顺利解出。于是想自己实现数独解法。没想到自己低估了数独解法的复杂度,几次实现,对于极难数独都胜算不高。

这次沉下心来重新写了一个,目前还没有解决不了的,(只要确有可行解)。

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);
    }
}
0 条评论