題目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.
寫代碼解決數(shù)獨問題勾徽。
A sudoku solution must satisfy all of the following rules:
數(shù)獨規(guī)則如下：

1. Each of the digits 1-9 must occur exactly once in each row.
   1-9每行必須出現(xiàn)且只能出現(xiàn)一次
2. Each of the digits 1-9 must occur exactly once in each column.
   1-9每列必須出現(xiàn)且只能出現(xiàn)一次
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
   每個3*3的子格子內(nèi)（粗框標(biāo)記的），1-9必須出現(xiàn)且只能出現(xiàn)一次
   Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
  給出的數(shù)組中只有1-9和'.'
• You may assume that the given Sudoku puzzle will have a single unique solution.
  給出的數(shù)獨只有一個唯一解
• The given board size is always 9x9.
  給的數(shù)組永遠(yuǎn)是9*9继找，不用多余的判斷

思路分析

其實沒啥更好的解法口猜，就是DFS深度優(yōu)先搜索找結(jié)果负溪，

• 遍歷格子，如果發(fā)現(xiàn)'.'济炎，就開始執(zhí)行下面的操作：
• 從1到9依次填數(shù)川抡，從填1開始，
  1. 然后看下行有沒有問題须尚，
  2. 看下列有沒有問題崖堤，
  3. 看下3*3的子格子有沒有問題，
  4. 都沒問題就遞歸的往下找恨闪。
  5. 有問題（1,2,3當(dāng)前格子填的數(shù)字沖突了倘感，或者4當(dāng)前格子的填數(shù)導(dǎo)致后面遞歸的填數(shù)失敗了）就把這個位置換回'.'（這就是一個回溯的過程，因為這樣一來之前遞歸的失敗路徑就全都回退了）咙咽，然后改成填2老玛，再繼續(xù)遍歷
• 如果1-9都遍歷完，還是沒有合適的钧敞，就返回false給上層蜡豹。

代碼實現(xiàn)

總之就是一個DFS搜索，注意下1溉苛，2镜廉，3條件的判斷，然后想清楚什么時候遞歸（當(dāng)前填數(shù)沒問題愚战，要確認(rèn)下面層次的問題）以及遞歸的出口（當(dāng)前位置1-9都遍歷完還是沒有合適的就返回false娇唯，如果9*9的格子全遍歷完了中間沒有返回false就說明數(shù)組中沒有'.'了齐遵，填滿了）就行了。

public class Solution {

    /**
     * 6 / 6 test cases passed.
     *  Status: Accepted
     *  Runtime: 17 ms
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; k++) {
                        board[i][j] = (char) ('1' + k);
                        if (isValid(board, i, j) && solve(board)) {
                            return true;
                        } else {
                            // backtracking to '.'
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int x, int y) {
        for (int i = 0; i < board.length; i++) {
            if (board[i][y] == board[x][y] || board[x][i] == board[x][y]) {
                return false;
            }
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int pos_x = x - x % 3 + i;
                int pos_y = y - y % 3 + j;
                if (x != pos_x && y != pos_y && board[x][y] == board[pos_x][pos_y]) {
                    return false;
                }
            }
        }

        return true;

    }
}