sudoku solve

SudokuTest.java

import java.util.Arrays;

public class SudokuTest {

    private static int[][] sudoku = new int[9][9];
    private static int step = 0;

    private static void init() {
        String src = "" +
                "009002400" +
                "300500200" +
                "600000100" +
                "010008009" +
                "700000003" +
                "800300010" +
                "001000006" +
                "005001002" +
                "008700500";
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.valueOf("" + src.charAt(i * 9 + j));
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("================================");
        long startTime = System.currentTimeMillis();
        init();
        deepGuess(sudoku);
        if (isDone(sudoku)) {
            System.err.println();
            System.err.println();
            for (int[] line : sudoku) {
                System.err.println(Arrays.toString(line));
            }
            System.err.println();
            System.err.println();
        }
        System.out.println("总用时：" + (System.currentTimeMillis() - startTime) + "ms");
    }

    private static void deepGuess(int[][] sudoku) {
//        System.out.println("\n");
//        for (int[] line : sudoku) {
//            System.out.println(Arrays.toString(line));
//        }
        int[][] newSudoku = getSudoku(sudoku);
        simpleGuess(newSudoku);
        if (isDone(newSudoku)) {
            System.out.println("Done!");
            SudokuTest.sudoku = newSudoku;
            return;
        }
        if (!isSame(sudoku, newSudoku)) {
            deepGuess(newSudoku);
        } else {
            step++;
            StringBuilder s = new StringBuilder();
            for (int i = 1; i < step; i++) {
                s.append("        ");
            }
//            System.out.println(">>>>>>deep guess");
            int[] undoPoint = getFirstUndoPoint(newSudoku);
            System.out.println(s + "~ undoPoint " + Arrays.toString(undoPoint));
            if (null == undoPoint) {
//                System.out.println(s + "没有找到空的点");
                step--;
                return;
            }
            int[] guessNum = guessUndoPoint(newSudoku, undoPoint[0], undoPoint[1]);
            if (guessNum == null) {
                System.out.println(s + "× error " + Arrays.toString(undoPoint));
                step--;
                return;
            }

            System.out.println(s + "> start guess point:" +
                    Arrays.toString(undoPoint) + "    " + Arrays.toString(guessNum));
            for (int i = 0; i < 9; i++) {
                if (guessNum[i] > 0) {
                    System.out.println(s + "    - guess " +
                            Arrays.toString(undoPoint) + " -> " + guessNum[i]);
                    newSudoku[undoPoint[0]][undoPoint[1]] = guessNum[i];
                    deepGuess(newSudoku);
                }
            }
            System.out.println(s + "= end guess point:" + Arrays.toString(undoPoint));
            step--;
        }

    }

    private static void simpleGuess(int[][] sudoku) {
//        System.out.println("_____simple guess");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (sudoku[i][j] < 1) {
                    int[] list = new int[9];
                    for (int k = 0; k < 9; k++) {
                        int num = sudoku[i][k];
                        if (num > 0) {
                            list[num - 1] = num;
                        }
                    }
                    for (int k = 0; k < 9; k++) {
                        int num = sudoku[k][j];
                        if (num > 0) {
                            list[num - 1] = num;
                        }
                    }
                    int[] center = getCellCenter(i, j);
                    int x = center[0];
                    int y = center[1];
                    for (int p = x - 1; p <= x + 1; p++) {
                        for (int q = y - 1; q <= y + 1; q++) {
                            int num = sudoku[p][q];
                            if (num > 0) {
                                list[num - 1] = num;
                            }
                        }
                    }

                    int count = 0;
                    int result = 0;
                    for (int k = 0; k < 9; k++) {
                        if (list[k] < 1) {
                            count++;
                            if (count > 1) {
                                break;
                            }
                            result = k + 1;
                        }
                    }
                    if (count == 1) {
                        sudoku[i][j] = result;
                    }
                }
            }
        }
    }

    private static int[] getFirstUndoPoint(int[][] newSudoku) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (newSudoku[i][j] < 1) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    private static int[] guessUndoPoint(int[][] sudoku, int i, int j) {
        if (sudoku[i][j] < 1) {
            int[] list = new int[9];
            for (int k = 0; k < 9; k++) {
                int num = sudoku[i][k];
                if (num > 0) {
                    list[num - 1] = num;
                }
            }
            for (int k = 0; k < 9; k++) {
                int num = sudoku[k][j];
                if (num > 0) {
                    list[num - 1] = num;
                }
            }
            int[] center = getCellCenter(i, j);
            int x = center[0];
            int y = center[1];
            for (int p = x - 1; p <= x + 1; p++) {
                for (int q = y - 1; q <= y + 1; q++) {
                    int num = sudoku[p][q];
                    if (num > 0) {
                        list[num - 1] = num;
                    }
                }
            }
            int[] guess = new int[9];
            int count = 0;
            for (int k = 0; k < 9; k++) {
                if (list[k] < 1) {
                    count++;
                    guess[k] = k + 1;
                }
            }
            if (count > 0) {
                return guess;
            }
        }
        return null;
    }

    private static int[][] getSudoku(int[][] sudoku) {
        int[][] backup = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                backup[i][j] = sudoku[i][j];
            }
        }
        return backup;
    }

    private static boolean isSame(int[][] sudoku, int[][] newSudoku) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (newSudoku[i][j] != sudoku[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean checkRow(int[][] sudoku, int index) {
        int[] list = new int[9];
        for (int i = 0; i < 9; i++) {
            int num = sudoku[index][i];
            if (num < 1) {
                return false;
            }
            list[num - 1] = num;
        }
        for (int i = 0; i < 9; i++) {
            if (list[i] < 1) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkCol(int[][] sudoku, int index) {
        int[] list = new int[9];
        for (int i = 0; i < 9; i++) {
            int num = sudoku[i][index];
            if (num < 1) {
                return false;
            }
            list[num - 1] = num;
        }
        for (int i = 0; i < 9; i++) {
            if (list[i] < 1) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkCell(int[][] sudoku, int x, int y) {
        int[] center = getCellCenter(x, y);
        int i = center[0];
        int j = center[1];
        int[] list = new int[9];
        for (int p = i - 1; p <= i + 1; p++) {
            for (int q = j - 1; q <= j + 1; q++) {
                int num = sudoku[p][q];
                if (num < 1) {
                    return false;
                }
                list[num - 1] = num;
            }
        }
        for (int k = 0; k < 9; k++) {
            if (list[k] < 1) {
                return false;
            }
        }
        return true;
    }

    private static int[] getCellCenter(int x, int y) {
        if (x % 3 == 0) {
            x++;
        } else if (x % 3 == 2) {
            x--;
        }
        if (y % 3 == 0) {
            y++;
        } else if (y % 3 == 2) {
            y--;
        }
        return new int[]{x, y};
    }

    private static boolean isDone(int[][] sudoku) {
        for (int i = 0; i < 9; i++) {
            if (!checkRow(sudoku, i)) {
                return false;
            }
            if (!checkCol(sudoku, i)) {
                return false;
            }
        }
        for (int i = 1; i <= 9; i += 3) {
            if (!checkCell(sudoku, i, i)) {
                return false;
            }
        }
        return true;
    }
}