I like to read this solution as a small machine: keep the useful information, throw away the noise. For 37. Sudoku Solver, the solution in this repository is mainly a bit manipulation solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: bit manipulation, backtracking, greedy.
The notes already sitting in the source point us in the right direction:
- backtracking
- TLE
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are coord2gridIdx, isValidSudoku, backtrack, solveSudoku, isValidSudokuCell.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtracking
02//TLE
03struct pair_hash {
04 inline std::size_t operator()(const std::pair<int,int> & v) const {
05 return v.first*31+v.second;
06 }
07};
08
09class Solution {
10public:
11 bool ansFound;
12 vector<vector<char>> ans;
13 unordered_set<char> allchar = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
14
15 int coord2gridIdx(int i, int j){
16 /*
17 grid 0: i: [0-2], j:[0-2]
18 grid 1: i: [0-2], j:[3-5]
19 grid 2: i: [0-2], j:[6-8]
20 */
21
22 return i/3 * 3 + j/3;
23 };
24
25 bool isValidSudoku(vector<vector<char>>& board) {
26 vector<unordered_set<char>> rows(9), cols(9), grids(9);
27 pair<unordered_set<char>::iterator, bool> ret;
28
29 for(int i = 0; i < 9; ++i){
30 for(int j = 0; j < 9; ++j){
31 char c = board[i][j];
32 if(c == '.') continue;
33 int gridIdx = coord2gridIdx(i, j);
34 ret = rows[i].insert(c);
35 if(!ret.second) return false;
36 ret = cols[j].insert(c);
37 if(!ret.second) return false;
38 ret = grids[gridIdx].insert(c);
39 if(!ret.second) return false;
40 }
41 }
42
43 return true;
44 };
45
46 void backtrack(vector<vector<char>>& board,
47 unordered_set<pair<int, int>, pair_hash>& tovisit,
48 vector<unordered_set<char>>& rows,
49 vector<unordered_set<char>>& cols,
50 vector<unordered_set<char>>& grids){
51 // cout << "tovisit: " << tovisit.size() << endl;
52 if(tovisit.empty()){
53 for(int i = 0; i < 9; ++i){
54 for(int j = 0; j < 9; ++j){
55 cout << board[i][j] << " ";
56 }
57 cout << endl;
58 }
59 if(isValidSudoku(board)){
60 ansFound = true;
61 return;
62 }
63 }else{
64 for(auto it = tovisit.begin(); it != tovisit.end(); ++it){
65 int i = it->first, j = it->second;
66
67 // cout << "visit (" << i << ", " << j << "): " << tovisit.size() << endl;
68 // cout << "(" << i << ", " << j << ")" << endl;
69
70 unordered_set<char> union2, union3 = rows[i];
71 copy(cols[j].begin(), cols[j].end(),
72 inserter(union3, union3.end()));
73
74 int gridIdx = coord2gridIdx(i,j);
75 copy(grids[gridIdx].begin(), grids[gridIdx].end(),
76 inserter(union3, union3.end()));
77
78 unordered_set<char> choosable;
79 copy_if(allchar.begin(), allchar.end(),
80 inserter(choosable, choosable.begin()),
81 [&union3] (int needle) { return union3.find(needle) == union3.end(); });
82
83 // cout << "rows[i]: " << rows[i].size() << endl;
84 // for(const auto e : rows[i]){
85 // cout << e << " ";
86 // }
87 // cout << endl;
88 // cout << "cols[j]: " << cols[j].size() << endl;
89 // for(const auto e : cols[j]){
90 // cout << e << " ";
91 // }
92 // cout << endl;
93 // cout << "grids[gridIdx]: " << grids[gridIdx].size() << endl;
94 // for(const auto e : grids[gridIdx]){
95 // cout << e << " ";
96 // }
97 // cout << endl;
98 // cout << "union3: " << union3.size() << endl;
99 // for(const auto e : union3){
100 // cout << e << " ";
101 // }
102 // cout << endl;
103 // cout << "choosable: " << choosable.size() << endl;
104 // for(const auto e : choosable){
105 // cout << e << " ";
106 // }
107 // cout << endl;
108
109 // cout << "found choosable: " << choosable.size() << endl;
110 // cout << "tovisit erased one" << endl;
111 for(char d : choosable){
112 rows[i].insert(d);
113 cols[j].insert(d);
114 grids[gridIdx].insert(d);
115
116 // cout << "sets erased one" << endl;
117
118 board[i][j] = d;
119 unordered_set<pair<int, int>, pair_hash> newtovisit = tovisit;
120 newtovisit.erase({i, j});
121 backtrack(board, newtovisit, rows, cols, grids);
122 if(ansFound) return;
123 board[i][j] = '.';
124
125 rows[i].erase(d);
126 cols[j].erase(d);
127 grids[gridIdx].erase(d);
128 // cout << "sets inserted one" << endl;
129 }
130 // cout << "tovisit inserted one" << endl;
131 }
132 }
133 };
134
135 void solveSudoku(vector<vector<char>>& board) {
136 ansFound = false;
137 vector<unordered_set<char>> rows(9), cols(9), grids(9);
138 unordered_set<pair<int, int>, pair_hash> tovisit;
139
140 for(int i = 0; i < 9; ++i){
141 for(int j = 0; j < 9; ++j){
142 char d = board[i][j];
143 int gridIdx = coord2gridIdx(i, j);
144 if(d == '.'){
145 tovisit.insert({i, j});
146 }else{
147 rows[i].insert(d);
148 cols[j].insert(d);
149 grids[gridIdx].insert(d);
150 }
151 }
152 }
153
154 backtrack(board, tovisit, rows, cols, grids);
155 }
156};
157
158//backtracking
159//https://leetcode.com/problems/sudoku-solver/discuss/15752/Straight-Forward-Java-Solution-Using-Backtracking
160//Runtime: 28 ms, faster than 58.89% of C++ online submissions for Sudoku Solver.
161//Memory Usage: 6.5 MB, less than 82.12% of C++ online submissions for Sudoku Solver.
162class Solution {
163public:
164 int coord2gridIdx(int i, int j){
165 /*
166 grid 0: i: [0-2], j:[0-2]
167 grid 1: i: [0-2], j:[3-5]
168 grid 2: i: [0-2], j:[6-8]
169 */
170
171 return i/3 * 3 + j/3;
172 };
173
174 bool isValidSudokuCell(vector<vector<char>>& board, int row, int col, char d) {
175 /*
176 want to find board[row][col] with d,
177 check if it will be valid
178 */
179 for(int i = 0; i < 9; ++i){
180 //check row
181 if(board[i][col] == d) return false;
182 //check col
183 if(board[row][i] == d) return false;
184 //check 3*3 block
185 if(board[3 *(row/3)+i/3][3*(col/3)+i%3] == d) return false;
186 }
187
188 return true;
189 };
190
191 bool helper(vector<vector<char>>& board) {
192 for(int i = 0; i < 9; ++i){
193 for(int j = 0; j < 9; ++j){
194 if(board[i][j] != '.') continue;
195 for(char d = '1'; d <= '9'; ++d){
196 if(!isValidSudokuCell(board, i, j, d)) continue;
197 board[i][j] = d;
198 bool res = helper(board);
199 if(res) return true;
200 board[i][j] = '.';
201 }
202
203 //this cell cannot be filled with '1'-'9'
204 return false;
205 }
206 }
207
208 return true;
209 };
210
211 void solveSudoku(vector<vector<char>>& board) {
212 helper(board);
213 }
214};
215
216//backtracking, improved from above
217//https://leetcode.com/problems/sudoku-solver/discuss/15752/Straight-Forward-Java-Solution-Using-Backtracking/15800
218//Runtime: 20 ms, faster than 75.81% of C++ online submissions for Sudoku Solver.
219//Memory Usage: 6.6 MB, less than 69.50% of C++ online submissions for Sudoku Solver.
220class Solution {
221public:
222 bool isValidSudokuCell(vector<vector<char>>& board, int row, int col, char d) {
223 /*
224 want to find board[row][col] with d,
225 check if it will be valid
226 */
227 for(int i = 0; i < 9; ++i){
228 //check row
229 if(board[i][col] == d) return false;
230 //check col
231 if(board[row][i] == d) return false;
232 //check 3*3 block
233 if(board[3 *(row/3)+i/3][3*(col/3)+i%3] == d) return false;
234 }
235
236 return true;
237 };
238
239 bool helper(vector<vector<char>>& board, int start_row, int start_col) {
240 for(int i = start_row; i < 9; ++i, start_col = 0){
241 //at "start_row", we starts from "start_col"
242 //in later rows, we starts from 0
243 for(int j = start_col; j < 9; ++j){
244 if(board[i][j] != '.') continue;
245 for(char d = '1'; d <= '9'; ++d){
246 if(!isValidSudokuCell(board, i, j, d)) continue;
247 board[i][j] = d;
248 bool res = helper(board, i, j+1);
249 if(res) return true;
250 board[i][j] = '.';
251 }
252
253 //this cell cannot be filled with '1'-'9'
254 return false;
255 }
256 }
257
258 return true;
259 };
260
261 void solveSudoku(vector<vector<char>>& board) {
262 helper(board, 0, 0);
263 }
264};
265
266//reactive-network + backtracking
267//https://leetcode.com/problems/sudoku-solver/discuss/15748/Sharing-my-2ms-C%2B%2B-solution-with-comments-and-explanations.
268//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sudoku Solver.
269//Memory Usage: 6.7 MB, less than 48.20% of C++ online submissions for Sudoku Solver.
270struct cell{
271 uint8_t val;
272 uint8_t numPossibilities;
273 //if bitset[i] is 1, then current cell cannot be i
274 bitset<10> constraints;
275
276 cell(): val(0), numPossibilities(9), constraints() {};
277};
278
279class Solution {
280public:
281 array<array<cell, 9>, 9> cells;
282
283 vector<pair<int, int>> emptys;
284
285 bool updateConstraints(int i, int j, int excludedVal){
286 cell& c = cells[i][j];
287
288 //already excluded
289 if(c.constraints[excludedVal]) return true;
290 //found a conflict
291 if(c.val == excludedVal) return false;
292
293 c.constraints.set(excludedVal);
294 --c.numPossibilities;
295 if(c.numPossibilities > 1) return true;
296
297 //now c.numPossibilities == 1
298 //so cells[i][j] is determined
299 for(int v = 1; v <= 9; ++v){
300 if(!c.constraints[v]){
301 return setCell(i, j, v);
302 }
303 }
304
305 //can never reach here
306 // assert(false);
307 return false;
308 };
309
310 bool setCell(int i, int j, int v){
311 cell& c = cells[i][j];
312
313 //this cell has already been set
314 if(c.val == v) return true;
315
316 //found a conflict
317 if(c.constraints[v]) return false;
318
319 //1111111110
320 c.constraints = bitset<10>(0x3FE);
321 //because the value of current cell is determined
322 c.constraints.reset(v);
323 c.numPossibilities = 1;
324 c.val = v;
325
326 for(int k = 0; k < 9; ++k){
327 int gi = i/3*3+k/3, gj = j/3*3+k%3;
328 if(i != k && !updateConstraints(k, j, v)){
329 return false;
330 }
331 if(j != k && !updateConstraints(i, k, v)){
332 return false;
333 }
334 if(i != gi && j != gj && !updateConstraints(gi, gj, v)){
335 return false;
336 }
337 }
338
339 return true;
340 };
341
342 bool findValuesForEmptyCells(){
343 for(int i = 0; i < 9; ++i){
344 for(int j = 0; j < 9; ++j){
345 if(cells[i][j].val == 0){
346 emptys.push_back({i, j});
347 }
348 }
349 }
350
351 sort(emptys.begin(), emptys.end(),
352 [this](const pair<int, int>& a, const pair<int, int>& b){
353 return cells[a.first][a.second].numPossibilities < cells[b.first][b.second].numPossibilities;
354 });
355
356 //false for fail
357 return backtrack(0);
358 };
359
360 bool backtrack(int k){
361 //all cells set
362 if(k >= emptys.size()) return true;
363 auto p = emptys[k];
364 int i = p.first, j = p.second;
365
366 cell& c = cells[i][j];
367 //current cell already set, continue the next
368 if(c.val) return backtrack(k+1);
369
370 array<array<cell, 9>, 9> snapshot(cells);
371
372 //try 1-9 for current cell
373 for(int v = 1; v <= 9; ++v){
374 //cannot fill v into current cell
375 if(c.constraints[v]) continue;
376
377 if(setCell(i, j, v)){
378 bool res = backtrack(k+1);
379 if(res) return res;
380 }
381
382 cells = snapshot;
383 }
384
385 return false;
386 }
387
388 void solveSudoku(vector<vector<char>>& board) {
389 for(int i = 0; i < 9; ++i){
390 for(int j = 0; j < 9; ++j){
391 if(board[i][j] == '.') continue;
392 if(!setCell(i, j, board[i][j]-'0')){
393 //there is a conflict
394 return;
395 }
396 }
397 }
398
399 if(!findValuesForEmptyCells()){
400 //there is a conflict, the sudoku is unsolvable
401 return;
402 }
403
404 for(int i = 0; i < 9; ++i){
405 for(int j = 0; j < 9; ++j){
406 if(cells[i][j].val){
407 board[i][j] = cells[i][j].val + '0';
408 }
409 }
410 }
411 }
412};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.