MiddleCodeOccasionalNot answered yet
Solve a Sudoku puzzle
Given a 9×9 Sudoku board where empty cells are 0, fill the board so that every row, column, and 3×3 box contains the digits 1–9 exactly once. Return true if the board is solvable (and leave it filled), false otherwise.
Requirements:
not the whole board.
- Validate only the affected row, column, and 3×3 box for each placement,
- On a dead end, undo the placement and try the next digit (backtracking).
#include <array>
using Board = std::array<std::array<int, 9>, 9>;
bool solve(Board& b) {
// your code here
}Write the implementation.
Use backtracking: find the first empty cell, try digits 1–9, check row/column/box constraints, recurse. If no digit works, backtrack. Time complexity is bounded by O(9^m) where m is the number of empty cells, but constraint propagation pruning makes it fast in practice.
- ✗Checking the full board at every step instead of only the affected row, column, and box
- ✗Not returning
truewhen a solution is found — the recursion must propagate success upward - ✗Using 1-indexed coordinates causing off-by-one errors in box calculation
- →How does constraint propagation (arc consistency) improve backtracking performance?
- →What is the 'most constrained variable' heuristic for choosing which cell to fill next?
Contents
Task
Solve a Sudoku puzzle using backtracking.
Key points
- Backtracking: place digit → recurse → undo on failure.
isValidchecks only the affected row, column, and 3×3 box.- Optimisation: pick the cell with the fewest candidates (MRV heuristic).
Contents
