需要满足的条件——
- 每行/每列数字不能重复
- 划分为9个九宫格区域后,每个区域内数字不能重复
如何判断每个九宫格内数字不重复呢?以第一个和第二个九宫格为例:
(0,0), (0,1), (0,2)
|||(0,3), (0,4), (0,5)
(1,0), (1,1), (1,2)
|||(1,3), (1,4), (1,5)
(2,0), (2,1), (2,2)
|||(2,3), (2,4), (2,5)
设当前坐标为(x,y)
,那么当前九宫格内任意一个位置的坐标为:
- 横坐标——
(x/3)*3 + i/3
- 纵坐标——
(y/3)*3 + i%3
- 其中i的范围为
0..8
另外注意到,解法唯一,我们需要设置提前退出条件,以降低算法的时间复杂度。
完整代码如下:
// // Created by jt on 2020/9/1. // #include <vector> using namespace std; class Solution { public: void solveSudoku(vector<vector<char> > &board) { dfs(board, 0, 0); } bool dfs(vector<vector<char> > &board, int x, int y) { if (x == 9) { return true; } if (y == 9) { return dfs(board, x+1, 0); } // 跳转到下一行 if (board[x][y] != '.') { return dfs(board, x, y+1); } for (char c = '1'; c <= '9'; ++c) { if (!isValid(board, x, y, c)) continue; board[x][y] = c; if (dfs(board, x, y+1)) return true; board[x][y] = '.'; } return false; } bool isValid(vector<vector<char> > &board, int x, int y, char ch) { for (int i = 0; i < 9; ++i) { if (board[x][i] == ch) return false; if (board[i][y] == ch) return false; if (board[(x/3)*3 + i/3][(y/3)*3 + i%3] == ch) return false; } return true; } };