1. Problem Statement (Simple Explanation):
You are given a 9×9 Sudoku board, partially filled, with:
Digits '1'–'9' for filled cells.
'.' for empty cells.
You must:
Fill the empty cells so that the final board is a valid Sudoku solution:
Each digit 1–9 appears exactly once in each row.
Each digit 1–9 appears exactly once in each column.
Each digit 1–9 appears exactly once in each 3×3 sub-box.
The input is guaranteed to have exactly one solution.
You must modify the board in-place.
2. Example:
Input board:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output solved board:
[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]
3. Approach – Backtracking with Row/Col/Box Constraints:
This is a classic backtracking search problem:
Choose an empty cell.
Try placing digits '1'–'9' that do not violate Sudoku constraints.
Recursively solve the rest of the board.
If at some point no digit works, backtrack: undo last placement and try next digit.
To make it efficient, we track used digits in:
rows[9][9] – rows[r][d] is true if digit d+1 already used in row r.
cols[9][9] – cols[c][d] is true if digit d+1 already used in column c.
boxes[9][9] – boxes[b][d] is true if digit d+1 already used in box b.
Where:
d = digit - '1' gives index 0..8
b = (r / 3) * 3 + (c / 3) gives box index 0..8
We initialize these from the given board, then run DFS/backtracking.
Because the problem guarantees exactly one solution, we can stop as soon as the board is filled validly.
4. Detailed Algorithm:
Initialize constraint arrays:
For each cell (r, c):
If board[r][c] != '.':
Compute d = board[r][c] - '1'.
Compute boxIndex = (r / 3) * 3 + (c / 3).
Mark:
rows[r][d] = true
cols[c][d] = true
boxes[boxIndex][d] = true
Backtracking function: solve(r, c) or better: solve() that scans to find next empty cell.A common pattern:
Scan the board to find the next empty cell (r, c):
If none is found, puzzle is solved → return true.
For digit from '1' to '9':
Let d = digit - '1', b = (r / 3) * 3 + (c / 3).
If rows[r][d] == false and cols[c][d] == false and boxes[b][d] == false:
Place the digit:
board[r][c] = digit
rows[r][d] = cols[c][d] = boxes[b][d] = true
Recurse: if (solve()) return true;
Otherwise, backtrack:
board[r][c] = '.'
rows[r][d] = cols[c][d] = boxes[b][d] = false
If none of the digits work, return false.
Call solve() once after initialization.
Pseudo-code:
Worst-case, Sudoku solving is exponential in general.
But for typical boards and with constraints checking, it’s fast enough.
Space: O(1) (fixed size arrays).
5.Java code:
6. C code:
7. C++ code:
8. Python code:
9. JavaScript code:
Comments
Post a Comment