力扣Java解数独_LeetCode 力扣 37. 解数独
題目描述(困難難度)
給定一個數獨棋盤，輸出它的一個解。
解法一 回溯法
從上到下，從左到右遍歷每個空位置。在第一個位置，隨便填一個可以填的數字，再在第二個位置填一個可以填的數字，一直執行下去直到最后一個位置。期間如果出現沒有數字可以填的話，就回退到上一個位置，換一下數字，再向后進行下去。
public void solveSudoku(char[][] board) {
solver(board);
}
private boolean solver(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
char count = '1';
while (count <= '9') {
if (isValid(i, j, board, count)) {
board[i][j] = count;
if (solver(board)) {
return true;
} else {
//下一個位置沒有數字，就還原，然后當前位置嘗試新的數
board[i][j] = '.';
}
}
count++;
}
return false;
}
}
}
return true;
}
private boolean isValid(int row, int col, char[][] board, char c) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == c) {
return false;
}
}
for (int i = 0; i < 9; i++) {
if (board[i][col] == c) {
return false;
}
}
int start_row = row / 3 * 3;
int start_col = col / 3 * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[start_row + i][start_col + j] == c) {
return false;
}
}
}
return true;
}
時間復雜度：
空間復雜度：O(1)。
總
回溯法一個很典型的應用了。
總結
以上是生活随笔為你收集整理的力扣Java解数独_LeetCode 力扣 37. 解数独的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【收藏推荐】Markdown常用LaTe
- 下一篇： 音创服务器系统手动加歌,音创ktv点歌系