Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
Personally I think,
time complexity = O((n^2)!), n is the number of rows(cols) of the board.
C++
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
// Input validation.
if (board.size() == 0 ||
board.size() != board[0].size() ||
board.size() % 3 != 0) return;
helper(board);
}
bool helper(vector<vector<char>>& board) {
// Base case.
// ... ...
for (int row = 0; row < board.size(); row ++) {
for (int col = 0; col < board[0].size(); col ++) {
if (board[row][col] != '.') continue;
for (char num = '1'; num <= '9'; num ++) {
if (isValid(board, num, row, col)) {
// Have a try.
board[row][col] = num;
// Do recursion.
if (helper(board)) return true;;
// Roll back.
board[row][col] = '.';
}
}
// Can not find a suitable number[1-9].
return false;
}
}
return true;
}
bool isValid(const vector<vector<char>>& board, char num, int row, int col) {
// Check row.
for (int tmp_col = 0; tmp_col < board[0].size(); tmp_col ++) {
if (board[row][tmp_col] == num) return false;
}
// Check col.
for (int tmp_row = 0; tmp_row < board.size(); tmp_row ++) {
if (board[tmp_row][col] == num) return false;
}
// Check sub square.
int start_row = (row / 3) * 3;
int start_col = (col / 3) * 3;
for (int row = start_row; row < start_row + 3; row ++) {
for (int col = start_col; col < start_col + 3; col ++) {
if (board[row][col] == num) return false;
}
}
return true;
}
};
