Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

---

方法一：

这是最快的数独求解器之一。它足够紧凑 - 只有150行带注释的C ++代码。它结合了几种技术，如反应式网络更新传播和回溯以及非常积极的修剪。

该算法在线 - 它以空板开始，当你向它添加数字时，它开始解决数独。

与其他每行/每列/每平方有允许/不允许值位掩码的解决方案不同，此解决方案跟踪每个（！）单元的位掩码，为每个特定单元格的允许值形成一组约束。将值写入单元格后，新约束会立即传播到单元格的行，列和3x3平方。如果在此过程中可以明确推断出其他单元格的值 - 则设置该值，传播新约束，等等......您可以将其视为隐式的单元格反应网络。

如果我们幸运的话（我们将在杂志上发表的20个Sudokus中的19个中幸运），那么Sudoku将在输入的最后（甚至之前！）处理中得到解决。

否则，将有必须解析的空单元格。算法使用回溯来实现此目的。为了优化它，算法从具有最小模糊度的单元开始。通过使用优先级队列可以进一步改善这一点（但这里没有实现）。回溯或多或少是标准的，然而，在每一步我们猜测数字，反应更新传播重新发挥作用，它或者快速证明猜测是不可行的或显着修剪剩余的搜索空间。

值得注意的是，在这种情况下，获取和恢复状态的紧凑表示的快照比通过“撤消移动”进行回溯回滚更快.

class Solution {
	struct cell // encapsulates a single cell on a Sudoku board
	{
		uint8_t value; // cell value 1..9 or 0 if unset
					   // number of possible (unconstrained) values for the cell
		uint8_t numPossibilities;
		// if bitset[v] is 1 then value can't be v
		bitset<10> constraints;
		cell() : value(0), numPossibilities(9), constraints() {};
	};
	array<array<cell, 9>, 9> cells;

	// sets the value of the cell to [v]
	// the function also propagates constraints to other cells and deduce new values where possible
	bool set(int i, int j, int v)
	{
		// updating state of the cell
		cell& c = cells[i][j];
		if (c.value == v)
			return true;
		if (c.constraints[v])
			return false;
		c.constraints = bitset<10>(0x3FE); //11 1111 1110 最后一位为0是因为数独中不含有0
		c.constraints.reset(v);//将bitset从右向左的序号为v(即第v+1位)的元素置0
		c.numPossibilities = 1;
		c.value = v;

		// propagating constraints 传播约束
		for (int k = 0; k<9; k++) {
			// to the row: 
			if (i != k && !updateConstraints(k, j, v)) //判断除了第i行的其余行是否满足约束条件
				return false;
			// to the column:
			if (j != k && !updateConstraints(i, k, v)) //判断除了第j列的其余列是否满足约束条件
				return false;
			// to the 3x3 square:
			int ix = (i / 3) * 3 + k / 3;
			int jx = (j / 3) * 3 + k % 3;
			if (ix != i && jx != j && !updateConstraints(ix, jx, v))
				return false;
		}
		return true;
	}
	// update constraints of the cell i,j by excluding possibility of 'excludedValue'
	// once there's one possibility left the function recurses back into set()
	bool updateConstraints(int i, int j, int excludedValue)
	{
		cell& c = cells[i][j];
		if (c.constraints[excludedValue]) {
			return true;
		}
		if (c.value == excludedValue) {
			return false;
		}
		c.constraints.set(excludedValue);
		if (--c.numPossibilities > 1)
			return true;
		for (int v = 1; v <= 9; v++) {
			if (!c.constraints[v]) {
				return set(i, j, v);
			}
		}
		assert(false);
	}

	// backtracking state - list of empty cells
	vector<pair<int, int>> bt;

	// find values for empty cells
	bool findValuesForEmptyCells()
	{
		// collecting all empty cells
		bt.clear();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (!cells[i][j].value)
					bt.push_back(make_pair(i, j));
			}
		}
		// making backtracking efficient by pre-sorting empty cells by numPossibilities
		sort(bt.begin(), bt.end(), [this](const pair<int, int>&a, const pair<int, int>&b) {
			return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities; });
		return backtrack(0);
	}

	// Finds value for all empty cells with index >=k
	bool backtrack(int k)
	{
		if (k >= bt.size())
			return true;
		int i = bt[k].first;
		int j = bt[k].second;
		// fast path - only 1 possibility
		if (cells[i][j].value)
			return backtrack(k + 1);
		auto constraints = cells[i][j].constraints;
		// slow path >1 possibility.
		// making snapshot of the state
		array<array<cell, 9>, 9> snapshot(cells);
		for (int v = 1; v <= 9; v++) {
			if (!constraints[v]) {
				if (set(i, j, v)) {
					if (backtrack(k + 1))
						return true;
				}
				// restoring from snapshot,
				// note: computationally this is cheaper
				// than alternative implementation with undoing the changes
				cells = snapshot;
			}
		}
		return false;
	}
public:
	void solveSudoku(vector<vector<char>> &board) {
		cells = array<array<cell, 9>, 9>(); // clear array
											// Decoding input board into the internal cell matrix.
											// As we do it - constraints are propagated and even additional values are set as we go
											// (in the case if it is possible to unambiguously deduce them).
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.' && !set(i, j, board[i][j] - '0'))
					return; // sudoku is either incorrect or unsolvable
			}
		}
		// if we're lucky we've already got a solution,
		// however, if we have empty cells we need to use backtracking to fill them
		if (!findValuesForEmptyCells())
			return; // sudoku is unsolvable

					// copying the solution back to the board
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++) {
				if (cells[i][j].value)
					board[i][j] = cells[i][j].value + '0';
			}
		}
	}
};

 

---

方法二：

bool check(vector<vector<char>> &board, int i, int j, char val)
{
    int row = i - i%3, column = j - j%3;
    //对所有行的第j列进行判断
    for(int x=0; x<9; x++) if(board[x][j] == val) return false;
    //对所有列的第i行进行判断
    for(int y=0; y<9; y++) if(board[i][y] == val) return false;
    //对board[i][j]所属的3*3子块进行判断
    for(int x=0; x<3; x++)
    for(int y=0; y<3; y++)
        if(board[row+x][column+y] == val) return false;
    return true;
}
bool solveSudoku(vector<vector<char>> &board, int i, int j)
{
    if(i==9) return true;
    if(j==9) return solveSudoku(board, i+1, 0);
    if(board[i][j] != '.') return solveSudoku(board, i, j+1);

    for(char c='1'; c<='9'; c++)
    {
        if(check(board, i, j, c))
        {
            board[i][j] = c;
            if(solveSudoku(board, i, j+1)) return true;
            board[i][j] = '.';
        }
    }
        
    return false;
}

 void solveSudoku(vector<vector>& board) {
    solveSudoku(board, 0, 0);
 }