菜雞每日一題系列打卡37天

每天一道算法題目?

小伙伴們一起留言打卡

堅持就是勝利，我們一起努力！

題目描述(引自LeetCode)

編寫一個程序，通過已填充的空格來解決數獨問題。一個數獨的解法需遵循如下規則：

• 數字1-9在每一行只能出現一次。

• 數字1-9在每一列只能出現一次。

• 數字1-9在每一個以粗實線分隔的3x3宮內只能出現一次。

空白格用'.'表示。

一個數獨

答案被標成紅色

說明：

• 給定的數獨序列只包含數字1-9和字符'.'。

• 你可以假設給定的數獨只有唯一解。

• 給定數獨永遠是9x9形式的。

題目分析

本題是一道二維數組的題目，與上一道題目不同的是，這道題目是求解數獨。有經驗的小伙伴會第一時間想到回溯法。數獨求解問題，同經典的八皇后問題、迷宮問題一樣，都是回溯法的典型應用場景。所謂回溯法，說白了其實就是一種試探，通過試探的方式達到剪枝求解的目的。回溯法的流程就是按照某一順序進行試探，在可行的時候繼續向下試探，在不可行的時候返回試探前的狀態。這其實交代了回溯法所必須的一些要素，起始位置，結束位置，狀態存儲，可行性判斷及處理等。接下來，就在求解數獨的過程中感受一下回溯法的魅力吧。

代碼實現

class?Solution?{//?存儲當前行、列、宮的狀態private boolean[][] rows = new boolean[9][10];private boolean[][] columns = new boolean[9][10];private boolean[][] boxes = new boolean[9][10];public void solveSudoku(char[][] board) {//?根據輸入的board數組初始化行、列、宮的狀態for (int row = 0; row < 9; row++)for (int column = 0; column < 9; column++)if (board[row][column] != '.') {int num = board[row][column] - '0';rows[row][num] = true;columns[column][num] = true;boxes[(row / 3) * 3 + column / 3][num] = true;}//?從board數組的左上角開始回溯backTrace(board, 0, 0);}private boolean backTrace(char[][] board, int row, int column) {//?回溯至右下角則返回結果if (row == 9) return true;//?若當前位置有數字，則移動到下一個位置if (board[row][column] != '.') return backTrace(board, column == 8 ? row + 1 : row, column == 8 ? 0 : column + 1);else {//?當前宮的索引int index = (row / 3) * 3 + column / 3;for (int i = 1; i < 10; i++) {//?當前情況下符合條件if (!rows[row][i] && !columns[column][i] && !boxes[index][i]) {rows[row][i] = true;columns[column][i] = true;boxes[index][i] = true;board[row][column] = (char)(i + '0');// 后續情況符合條件if (backTrace(board, column == 8 ? row + 1 : row, column == 8 ? 0 : column + 1)) return true;//?否則狀態回溯至本次操作之前rows[row][i] = false;columns[column][i] = false;boxes[index][i] = false;board[row][column] = '.';}}}// 回溯結束，未找到結果return false;} }

代碼分析

對代碼進行分析，由于題目給出的是9x9的數獨，因此，每行需要填寫的數字不超過9個。在僅僅考慮行約束的情況下可以計算得最多有(9!)^9種情況，因此可以粗略估計出其時間復雜度，而就空間而言，在數獨大小固定的情況下，所使用的額外空間也是固定的。

執行結果

學習 | 工作 |?分享

????長按關注“有理想的菜雞”

只有你想不到，沒有你學不到

總結

以上是生活随笔為你收集整理的每日一题——解数独的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。