After writing a Nonogram solver, I decided to tackle a Sudoku solver to practice Rust. My goal wasn't just to support classic Sudoku rules, but also to handle variants like Thermometer, Arrow, and Cage etc. 1. Brute Force It is fairly easy to write a brute force or backtracking algorithm. This approach is sufficient for most classic Sudoku puzzles, but it becomes unbearably slow as soon as variant rules are introduced. I considered this step a warmup—a baseline to improve upon. 2. Constraint Propagation Here, I tried to introduce "logical thinking" to the algorithm. I used u16 as a bitmask to represent the possible values of a cell. Whenever a cell's state changes (due to guessing, backtracking, or propagation), the algorithm consults all constraints to eliminate impossible candidates. While Nonogram is technically an NP-Complete problem, in practice, my constraint-propagation solver (without guessing) can solve almost all puzzles found online. I’ve only seen one ex...
久病成医 | Prolonged Illness Makes the Patient a Good Doctor