摘要：題目要求也就是給出一個解決數(shù)獨的方法，假設(shè)每個數(shù)獨只有一個解決方案。并將當前的假象結(jié)果帶入下一輪的遍歷之中。如果最終遍歷失敗，則逐級返回，恢復(fù)上一輪遍歷的狀態(tài)，并填入下一個合理的假想值后繼續(xù)遍歷。

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ".".

You may assume that there will be only one unique solution.

也就是給出一個解決數(shù)獨的方法，假設(shè)每個數(shù)獨只有一個解決方案。

不使用數(shù)據(jù)結(jié)構(gòu)意味著我們自己在每一次遇到一個空格時，需要在board中對該空格所在的行，列以及方塊進行遍歷，判斷填入什么數(shù)字是合適的。并將當前的假象結(jié)果帶入下一輪的遍歷之中。如果最終遍歷失敗，則逐級返回，恢復(fù)上一輪遍歷的狀態(tài)，并填入下一個合理的假想值后繼續(xù)遍歷。這里涉及的時間復(fù)雜度是很高的，畢竟只是遍歷整個board就需要O(n^2)，如果遇到一個空格還需要O(n)來判斷填入值是否合理。總共O(n^3)的時間復(fù)雜度。代碼如下：

    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0)
            return;
        solve(board);
    }
    
    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == "."){
                    for(char c = "1"; c <= "9"; c++){//trial. Try 1 through 9
                        if(isValid(board, i, j, c)){
                            board[i][j] = c; //Put c for this cell
                            
                            if(solve(board))
                                return true; //If it"s the solution return true
                            else
                                board[i][j] = "."; //Otherwise go back
                        }
                    }
                    
                    return false;
                }
            }
        }
        return true;
    }
    
    //橫 豎 方塊
    private boolean isValid(char[][] board, int row, int col, char c){
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != "." && board[i][col] == c) return false; //check row
            if(board[row][i] != "." && board[row][i] == c) return false; //check column
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != "." && 
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
        }
        return true;
    }

我們使用boolean[][] rows, boolean[][] columns, boolean[][] squares分別記錄行列和方塊的所有值情況。其中rowsi記錄i行是否有值j，columnsi記錄i列是否有值j，squaresi記錄第i個方塊是否有值j?？傮w思路還是和上一個差不多，只是通過消費了存儲空間的基礎(chǔ)上提高了性能。

    public void solveSudoku2(char[][] board) {
        int length = board.length;
        //記錄第i行是否出現(xiàn)j數(shù)字
        boolean[][] rows = new boolean[length][length+1];
        //第i列是否出現(xiàn)j數(shù)字
        boolean[][] columns = new boolean[length][length+1];
        //第i個小方格是否出現(xiàn)j數(shù)字。
        boolean[][] squares = new boolean[length][length+1];
        for(int i = 0 ; i < length ; i++){
            for(int j = 0 ; j
更多解法
看到一個解答 效率很高 但是不是很明白 希望看到的大神解答一下
    private boolean solver(int idx, char[][] board, ArrayList stack, int[] store) {
        if (idx == stack.size()) return true;
        int n = stack.get(idx);
        int y = n / 9;
        int x = n - y * 9;
        int h = y;
        int v = 9 + x;
        int b = 18 + (y / 3 * 3 + x / 3);
        int available = ~store[h] & ~store[v] & ~store[b] & 0b111111111;
        while (available > 0) {
            int bit = available & -available;
            int num = Integer.numberOfTrailingZeros(bit);
            store[h] ^= bit;
            store[v] ^= bit;
            store[b] ^= bit;
            board[y][x] = (char)(num + "1");
            if (solver(idx + 1, board, stack, store)) return true;
            store[h] ^= bit;
            store[v] ^= bit;
            store[b] ^= bit;
            // board[y][x] = ".";
            available &= available - 1;
        }
        return false;
    }
    public void solveSudoku3(char[][] board) {
        ArrayList stack =  new ArrayList<>();
        // int[] stack = new int[81];
        int len = 0;
        int[] store = new int[27]; // 0-8 h, 9 - 17 v, 18 - 26 b
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == ".") stack.add(i * 9 + j);
                else {
                    int h = i;
                    int v = 9 + j;
                    int b = 18 + (i / 3 * 3 + j / 3);
                    store[h] ^= 1 << board[i][j] - "1";
                    store[v] ^= 1 << board[i][j] - "1";
                    store[b] ^= 1 << board[i][j] - "1";
                }
            }
        }
        solver(0, board, stack, store);
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~