一、題目描述
編寫一個程式，通過填充空格來解決數獨問題。
數獨的解法需 遵循如下規則：
數字 1-9 在每一行隻能出現一次。
數字 1-9 在每一列隻能出現一次。
數字 1-9 在每一個以粗實線分隔的 3x3 宮内隻能出現一次。（請參考示例圖）
數獨部分空格内已填入了數字，空白格用 '.' 表示。
示例：
解釋：輸入的數獨如上圖所示，唯一有效的解決方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位數字或者 '.'
題目資料 保證 輸入數獨僅有一個解
二、解題思路
我們可以考慮按照「行優先」的順序依次枚舉每一個空白格中填的數字，通過遞歸 + 回溯的方法枚舉所有可能的填法。當遞歸到最後一個空白格後，如果仍然沒有沖突，說明我們找到了答案；在遞歸的過程中，如果目前的空白格不能填下任何一個數字，那麼就進行回溯。
算法步驟:
數獨首先行，列，還有 3*3 的方格内數字是 1~9 不能重複。
聲明布爾數組，表明行列中某個數字是否被使用了， 被用過視為 true，沒用過為 false。
初始化布爾數組，表明哪些數字已經被使用過了。
嘗試去填充數組，隻要行，列， 還有 3*3 的方格内 出現已經被使用過的數字，我們就不填充，否則嘗試填充。
如果填充失敗，那麼我們需要回溯。将原來嘗試填充的地方改回來。
遞歸直到數獨被填充完成。
三、代碼
class Solution {
public void solveSudoku(char[][] board) {
// 三個布爾數組 表明 行, 列, 還有 3*3 的方格的數字是否被使用過
boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][][] boxUsed = new boolean[3][3][10];
// 初始化
for(int row = 0; row < board.length; row++){
for(int col = 0; col < board[0].length; col++) {
int num = board[row][col] - '0';
if(1 <= num && num <= 9){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
}
}
}
// 遞歸嘗試填充數組
recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
}
private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
// 邊界校驗, 如果已經填充完成, 傳回true, 表示一切結束
if(col == board[0].length){
col = 0;
row++;
if(row == board.length){
return true;
}
}
// 是空則嘗試填充, 否則跳過繼續嘗試填充下一個位置
if(board[row][col] == '.') {
// 嘗試填充1~9
for(int num = 1; num <= 9; num++){
boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
if(canUsed){
rowUsed[row][num] = true;
colUsed[col][num] = true;
boxUsed[row/3][col/3][num] = true;
board[row][col] = (char)('0' + num);
if(recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)){
return true;
}
board[row][col] = '.';
rowUsed[row][num] = false;
colUsed[col][num] = false;
boxUsed[row/3][col/3][num] = false;
}
}
} else {
return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
}
return false;
}
} 複制
四、複雜度分析
時間複雜度：O(1)，隻對
81
個單元格進行了周遊。
空間複雜度：O(1)，隻需要常數空間存放若幹變量。