Description Link to heading
Solution Link to heading
Compared with usual backtracking, we need for loop of two layers, one for row and another for column. A recursive process is used to determine exactly which number to fill in the space.
This return type of this function is bool, please pay attention to the role of return value in recursion.
Also a function to determine whether board is legal is required.
Code Link to heading
class Solution {
private:
bool isValid(int row, int col, char val, vector<vector<char>> &board) {
for (int i = 0; i < 9; i++) { // judge whether there are duplicates in a row
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // judge whether there are duplicates in a column
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
// judge whether there are duplicates in ninepin
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val) {
return false;
}
}
}
return true;
}
bool track_back(vector<vector<char>> &board) {
for (int i = 0; i < 9; i++) { // traverse in row
for (int j = 0; j < 9; j++) { // traverse in column
if (board[i][j] != '.')
continue;
for (char k = '1'; k <= '9'; k++) {
if (isValid(i, j, k, board)) {
board[i][j] = k;
if (track_back(board))
return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>> &board) {
track_back(board);
}
};