本文涉及知識點

回溯 狀態壓縮 深度優先

LeetCode37. 解數獨

編寫一個程序，通過填充空格來解決數獨問題。
數獨的解法需 遵循如下規則：
數字 1-9 在每一行只能出現一次。
數字 1-9 在每一列只能出現一次。
數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。（請參考示例圖）
數獨部分空格內已填入了數字，空白格用 ‘.’ 表示。

示例 1：
輸入：board = [[“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”]]

輸出：[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解釋：輸入的數獨如上圖所示，唯一有效的解決方案如下所示：
提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位數字或者 ‘.’
題目數據 保證 輸入數獨僅有一個解

回溯

vRow[i] 記錄第i行可以選擇那些數，vCol[i]和vCell類型。
vRow[i] & ( 1 << j) 表示第i行，可以選擇數組j。
直接將選擇結果修改到board上。
vector<tuple<int,int,int>> vSel。 i1,記錄可以選擇的數量,i2記錄行號，i3記錄列號。注意：只需要記錄能修改的數組。 初始化結束后，對vSel排序。理論上：只有一種選擇的先選快點。實際上幾乎無影響。
用深度優先實現。Fill 函數填寫某行某列，UnFill 恢復某行某列原裝。
時間復雜度：不好計算。

代碼

核心代碼

class CBitCounts
{
public:CBitCounts(int iMaskCount){for (int i = 0; i < iMaskCount; i++){m_vCnt.emplace_back(bitcount(i));}}template<class T>static int bitcount(T x) {int countx = 0;while (x) {countx++;x &= (x - 1);}return countx;}vector<int> m_vCnt;
};class Solution {
public:void solveSudoku(vector<vector<char>>& board) {m_board = board;int mask = 0;for (int i = 1; i <= 9; i++) {mask |= (1 << i);}for (int i = 0; i < 9; i++) {m_rows[i] = m_cols[i] = m_cells[i] = mask;}for (int r = 0; r < 9; r++) {for (int c = 0; c < 9; c++) {if ('.' == board[r][c]) { continue; }Fill(r, c, board[r][c] - '0');}}vector<tuple<int, int, int,int>> vSel;for (int r = 0; r < 9; r++) {for (int c = 0; c < 9; c++) {if ('.' != board[r][c]) { continue; }int iCell = r / 3 * 3 + c / 3;int mask = m_rows[r] & m_cols[c] & m_cells[iCell];vSel.emplace_back(CBitCounts::bitcount(mask), r, c,iCell);}}sort(vSel.begin(), vSel.end());DFS(vSel, 0);board = m_board;}bool DFS(const vector<tuple<int, int, int,int>> vSel, int leve) {if (vSel.size() == leve) { return true; }const auto& [tmp, r, c, iCell] = vSel[leve];int mask = m_rows[r] & m_cols[c] & m_cells[iCell];for (int i = 1; i <= 9; i++) {if (mask & (1 << i)) {Fill(r, c, i);if (DFS(vSel, leve + 1)) { return true; }UnFill(r, c, i);}}return false;}void Fill (int r, int c, int val) {m_board[r][c] = val + '0';m_rows[r] &= ~(1 << val);m_cols[c] &= ~(1 << val);int iCell = r / 3 * 3 + c / 3;m_cells[iCell] &= ~(1 << val);};void UnFill(int r, int c, int val) {m_board[r][c] = '.';m_rows[r] |= (1 << val);m_cols[c] |= (1 << val);int iCell = r / 3 * 3 + c / 3;m_cells[iCell] |= (1 << val);};vector<vector<char>> m_board;int m_rows[9], m_cols[9], m_cells[9];
};

測試用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<vector<char>> board;{Solution slu;board ={ {'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' }};slu.solveSudoku(board);vector<vector<char>> board1={ {'5', '3', '4', '6', '7', '8', '9', '1', '2'}, { '6','7','2','1','9','5','3','4','8' }, { '1','9','8','3','4','2','5','6','7' }, { '8','5','9','7','6','1','4','2','3' }, { '4','2','6','8','5','3','7','9','1' }, { '7','1','3','9','2','4','8','5','6' }, { '9','6','1','5','3','7','2','8','4' }, { '2','8','7','4','1','9','6','3','5' }, { '3','4','5','2','8','6','1','7','9' }};Assert(board1, board);}	
}

2023年5月代碼

記錄已經選擇的數，這樣初始化簡單。用二維數組記錄3$\times$ 3 網格的情況，減少計算網格號。

class Solution {
public:void solveSudoku(vector<vector<char>>& board) {memset(m_aRows, 0, sizeof(m_aRows));memset(m_aCols, 0, sizeof(m_aCols));memset(m_aBlock, 0, sizeof(m_aBlock));for (int r = 0; r < 9; r++){for (int c = 0; c < 9; c++){const char& ch = board[r][c];if ('.' == ch){m_vNeedDoRowCols.emplace_back(r, c);continue;}Add(r, c, ch - '1');}}dfs(board, 0);}bool dfs(vector<vector<char>>& board,int iLeve){if (m_vNeedDoRowCols.size() == iLeve){return true;}const int r = m_vNeedDoRowCols[iLeve].first;const int c = m_vNeedDoRowCols[iLeve].second;int iMask = m_aRows[r] | m_aCols[c] | m_aBlock[r/3][c/3];for (int i = 0; i < 9; i++){if (iMask & (1 << i)){continue;}Add(r, c, i);board[r][c] = '1' + i;if (dfs(board, iLeve + 1)){return true;}board[r][c] = '.';Erase(r, c, i);}return false;}void Add(int r, int c, int iNum){const int iMask = 1 << iNum;m_aRows[r] |= iMask;m_aCols[c] |= iMask;m_aBlock[r / 3][c / 3] |= iMask;}void Erase(int r, int c, int iNum){const int iMask = 1 << iNum;m_aRows[r] -= iMask;m_aCols[c] -= iMask;m_aBlock[r / 3][c / 3] -= iMask;}int m_aRows[9],m_aCols[9];int m_aBlock[3][3];vector<std::pair<int, int>> m_vNeedDoRowCols;
};