【回溯状态压缩深度优先】37. 解数独

本文涉及知识点

回溯状态压缩深度优先

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;
};