打卡Leetcode每日一題 37. 解數獨，
題目
撰寫一個程式，通過已填充的空格來解決數獨問題，一個數獨的解法需要遵循如下規則：
- 數字
1-9在每一行只能出現一次； - 數字
1-9在每一列只能出現一次； - 數字
1-9在每一個以粗實線分隔的3×3宮內只能出現一次，
空白格用.表示，
思路
根據題干中給出的3條規則，容易想到采用狀態陣列記錄數字1-9在每行、每列以及每個九宮格內是否出現以及出現的位置，
-
采用
boolean[][] row表示列行狀態陣列，用row[i][num]表示數字num出現在第i行，比如row[0][4] = true表示數字5（實際數字范圍是1-9）出現在第0行， -
采用
boolean[][] col表示列狀態陣列，用col[j][num]表示數字num出現在第j行，比如col[0][5] = true表示數字6出現在第0列， -
采用
boolean[][] block表示九宮格狀態陣列，粗實線將整個數獨劃分成了9個3×3九宮格，因此按從左至右、從上至下的順序將每個九宮格編號為0-8，用block[blockIndex][num]表示數字num出現在第blockIndex九宮格，比如block[2][5]表示數字6出現在第2號九宮格，接下來的問題在于如何根據行下標i和列下標j計算出九宮格的標號blockIndex，給出如下計算公式：blockIndex = i / 3 * 3 + j / 3
根據初始狀態確定行、列和九宮格狀態陣列后，采用遞回和回溯思想解數獨，
-
找到需要填數字的位置，即
board[][] == '.'的位置； -
在每一個需要填數字的位置
(i,j)填入數字num，必須滿足該數字沒有在當前位置所在的行、列和九宮格中出現，即!row[i][num] && !col[j][num] && !block[blockIndex][num]為真； -
滿足條件后將數字
num填入，并更新該位置對應的狀態陣列中的值為true； -
更新行坐標
i和列坐標j，遞回求解下一個需要填數字的位置；-
如果求解成功，繼續遞回；
-
如果求解失敗，需要回溯，將當前位置的對應的狀態陣列的值均設定為
false，同時將數獨中該位置的值重新設定為.，
-
-
遞回結束條件：整個數獨遍歷完成，
Java實作
求解數獨類：
class Solution {
/**
* 解數獨
* @param board
*/
public void solveSudoku(char[][] board) {
// 行狀態陣列
boolean[][] row = new boolean[9][9];
// 列狀態陣列
boolean[][] col = new boolean[9][9];
// 九宮格狀態陣列
boolean[][] block = new boolean[9][9];
// 記錄數獨的初始狀態
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '1';
row[i][num] = true;
col[j][num] = true;
block[i / 3 * 3 + j / 3][num] = true;
}
}
}
// 解數獨
dfs(board, row, col, block, 0, 0);
}
/**
* 遞回+回溯
* @param board
* @param row
* @param col
* @param block
* @param i
* @param j
* @return
*/
private boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j) {
// 遍歷數獨每個需要填數字的位置
while (board[i][j] != '.') {
// 對數獨的每個位置進行遍歷
// 逐行遍歷：若列坐標j大于等于9表示一行到頭
if (++j >= 9) {
// 行坐標自增跳轉下一行
i++;
// 列坐標歸零從第一列開始
j = 0;
}
// 當行坐標i大于等于9表示數獨遍歷完畢
if (i >= 9) return true;
}
// 在需要填數字的位置填入數字
for (int num = 0; num < 9; num++) {
// 確定九宮格狀態陣列的位置坐標
int blockIndex = i / 3 * 3 + j / 3;
// 所填數字num未在該行、該列以及該九宮格出現時
if (!row[i][num] && !col[j][num] && !block[blockIndex][num]) {
// 將num填入board[i][j]
// 由于num從0開始因此需要在數值上加1并轉型位char型別
board[i][j] = (char) ('1' + num);
// 將row、col以及block狀態陣列對應得狀態設定為true
row[i][num] = true;
col[j][num] = true;
block[blockIndex][num] = true;
// 遞回解數獨
if (dfs(board, row, col, block, i, j)) return true;
else {
// 若填入數字失敗則回溯
row[i][num] = false;
col[j][num] = false;
block[blockIndex][num] = false;
board[i][j] = '.';
}
}
}
return false;
}
}
求解測驗類：
public class SudokuSolutionTest {
public static void main(String[] args) {
char[][] board = new char[][]{
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
printBoard(board);
Solution solution = new Solution();
solution.solveSudoku(board);
printBoard(board);
}
/**
* 列印數獨函式
* @param board
*/
private static void printBoard(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
測驗結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/50427.html
標籤：Java