# Very simple solution accepted with 12ms in C, well-explained

• Let's just hit the road!

• move the pointer from left to right and the whole direction is from top-left to bottom-right;
• check each cell while moving;
• try each possible candidate from '1' to '9' while the checking cell is empty and if it's solvable from now on (recursive method) then just return it;
• if all possible candidates failed, return false to indicate un-solvable in this condition which means indirectly that we should try another path - typical DFS solution using recursion.

Bang! End of Story!

• space complexity O(1) -> nothing need to be recorded here just using constant space;
• time complexity O(9^k) but since we just are required to find only one viable solution, the cost will be dramatically reduced.

``````bool check(char** board, int r, int c, char a) //check it in row, column and the sub three-dimension cube;
{
for(int i = 0; i < 9; i++) if(board[r][i]==a || board[i][c]==a) return false;
int r0=r-r%3, c0=c-c%3; //get the start row and column of the sub cube;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
if(board[r0+i][c0+j] == a) return false;
return true;
}
bool solver(char** board, int r, int c) //check and try it from left to right and then downwards;
{
if(r == 9) return true; //now till the end and nothing wrong so far, so return true;
if(c == 9) return solver(board, r+1, 0); //till the end of the current row and then downwards;
if(board[r][c] != '.') return solver(board, r, c+1); //already taken just move to the next;
for(char a = '1'; a <= '9'; a++) //try each possible candidate;
{
if(check(board, r, c, a)) //check its validity;
{
board[r][c] = a; //set it then and just move to the next;
if(solver(board, r, c+1)) return true; //if it's solvable then just return true;
board[r][c] = '.'; //restore it for easier checking in the next round;
}
}
return false; //nothing works around then return false;
}
void solveSudoku(char** board, int rSize, int cSize)
{
solver(board, 0, 0); //start from the top-left position to the bottom right end;
}``````

• A more clean and efficient solution in C++.

``````class Solution {
private:
bool search(vector<vector<char>>& board, int r, int c, bool rTakens[][9], bool cTakens[][9], bool subTakens[][9])
{
if(r == 9) return true;
if(c == 9) return search(board, r+1, 0, rTakens, cTakens, subTakens);
if(board[r][c] != '.') return search(board, r, c+1, rTakens, cTakens, subTakens);
for(char a = '1'; a <= '9'; ++a)
{
int num = a -'0', k = r/3*3+c/3;
if(!(rTakens[r][num] || cTakens[c][num] || subTakens[k][num]))
{
rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
board[r][c] = a;
if(search(board, r, c+1, rTakens, cTakens, subTakens)) return true;
board[r][c] = '.';
rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = false;
}
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
bool rTakens[9][9]{{false}}, cTakens[9][9]{{false}}, subTakens[9][9]{{false}};
for(int r = 0; r < 9; ++r){
for(int c = 0; c < 9; ++c){
if(board[r][c] != '.') {
int num = board[r][c] -'0', k = r/3*3+c/3;
rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
}
}
}
search(board, 0, 0, rTakens, cTakens, subTakens);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.