Here is the implementation:
function solveSudoku(board):
solve(board)
function solve(board):
for i from 0 to 8:
for j from 0 to 8:
if board[i][j] == '.':
for digit from '1' to '9':
if isValid(board, i, j, digit):
board[i][j] = digit
if solve(board):
return true
board[i][j] = '.'
return false // No valid digit, backtrack
return true // All cells filled
function isValid(board, row, col, digit):
// Check row, column, and 3x3 box
boxRow = (row / 3) * 3
boxCol = (col / 3) * 3
// Return true if digit not in row, col, or box
Worst case explores many branches, but pruning makes it fast in practice.