Daily bit(e) of C++ | Sudoku solver
Daily bit(e) of C++ #161, Common interview problem: Sudoku Solver.
Today we will look at a common C++ interview problem: Sudoku solver.
Given a Sudoku puzzle as std::vector<std::vector<char>>, where unfilled spaces are represented as a space, solve the puzzle.
Sudoku rules:
each of the nine rows, columns and 3x3 boxes must contain all digits 1..9
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a compiler explorer linked with a couple of test cases: https://compiler-explorer.com/z/MnG9EG1jf.
Solution
While it is possible to implement a Sudoku solver that doesn’t guess, that is a project for many weekends (speaking from experience), not something to do during a coding interview. However, at the same time, we do not want to implement a straightforward guessing solver that brute-forces the puzzle.
A nice middle ground is applying the Sudoku constraint; each number can only appear once in each row, column and box. This means there is no point in guessing a number already present in the corresponding row, column or box. On top of that, if we arrive at a situation where we have no options to guess, we know this particular guessing path is invalid.
We do not have to keep re-checking which numbers are already present in a row/column/box. Instead, we can keep track of the used numbers for each row/column/box as we explore the puzzle, adding the numbers as we guess and removing them when backtracking from a bad solution.
