Sudoku Solver fills a 9×9 grid so each row, column, and 3×3 box contains digits 1-9 exactly once. Backtracking finds the first empty cell, tries digits 1-9, checks validity (row/column/box constraints), and recurses. If no digit works, it backtracks to the previous cell and tries the next digit.
bool isValid(vector<vector<char>>& b, int r, int c, char d){
for(int i=0;i<9;i++){
if(b[r][i]==d||b[i][c]==d) return false;
if(b[3*(r/3)+i/3][3*(c/3)+i%3]==d) return false;
}
return true;
}
bool solve(vector<vector<char>>& b){
for(int r=0;r<9;r++) for(int c=0;c<9;c++) if(b[r][c]=='.'){
for(char d='1';d<='9';d++) if(isValid(b,r,c,d)){
b[r][c]=d;
if(solve(b)) return true;
b[r][c]='.';
}
return false;
}
return true;
}A digit d is valid at (r,c) if it does not appear in row r, column c, or the 3×3 box containing (r,c). The box check uses indices 3*(r//3)+i//3 and 3*(c//3)+i%3 to iterate over the box.
Find the first empty cell. Try each digit 1-9. If valid, place it and recurse. If the recursion returns true, propagate success. If no digit works or recursion fails, reset cell to empty and return false.
Choose the cell with the fewest valid options (MRV heuristic). This reduces the branching factor dramatically. Constraint propagation (arc consistency) can solve many easy Sudokus without backtracking at all.
Quiz coming soon for this algorithm.