[LeetCode] 037. Sudoku Solver (Hard) (C++)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

037. Sudoku Solver (Hard)链接：

题目：https://leetcode.com/problems/sudoku-solver/代码(github)：https://github.com/illuz/leetcode

题意：

求解一个数独。

分析：

DFS 暴力就行了。用二进制表示，位运算处理的话，会快很多的。

其实在一个 (n^2) * (n^2) 的格中放 n * n 数，这是个 NP 难问题，就 9×9 的方格，就有9^81 种组合，用 DFS 遍历一遍是不可想象的，，所以在解一个空一点的 9×9 时就要跑好久。有个比较常用的优化方法就是用 Dancing Links，不过这也只是个剪枝，它仍是个 NP 难问题。

Link:- Sudoku – Wikipedia- Dancing Links

代码：

C++:

class Solution {private:int row[9], col[9], sqr[3][3];bool check(int x, int y, int val) {return !((row[x]>>val)&1) && !((col[y]>>val)&1) && !((sqr[x/3][y/3]>>val)&1);}void mark(int x, int y, int val, vector<vector<char> > &board) {row[x] |= (1<<val);col[y] |= (1<<val);sqr[x/3][y/3] |= (1<<val);board[x][y] = val + '1';}void unmark(int x, int y, int val, vector<vector<char> > &board) {row[x] -= (1<<val);col[y] -= (1<<val);sqr[x/3][y/3] -= (1<<val);board[x][y] = '.';}bool dfs(int pos, vector<vector<char> > &board) {// x = pos / 9, y = pos % 9if (pos == 81)return true;if (board[pos/9][pos%9] != '.') {return dfs(pos + 1, board);} else {for (int i = 0; i < 9; i++)if (check(pos/9, pos%9, i)) {mark(pos/9, pos%9, i, board);if (dfs(pos + 1, board))return true;unmark(pos/9, pos%9, i, board);}}return false;}public:void solveSudoku(vector<vector<char> > &board) {memset(row, 0, sizeof(row));memset(col, 0, sizeof(col));memset(sqr, 0, sizeof(sqr));for (int i = 0; i < board.size(); i++)for (int j = 0; j < board[i].size(); j++)if (board[i][j] != '.') {mark(i, j, board[i][j] – '1', board);}dfs(0, board);}};

为何是一个人？也有善意的提醒：