(Killer) Sudoku Solver
A solver for killer and/or regular sudokus! It's written in rust and compiled to web assembly. It supports fixed digits and constraints on the sum of different cells.
Enter digits into the grid, or add some sum-rules; a collection of cells which must sum to a given number. As in traditional killer sudoku rules, all cell values in a sum-rule must be unique. For more detailed instructions see below.
| Cell ixs | Sum To |
|---|
Fixed digits
- You can enter fixed digits by selecting the cell and entering a digit. You can enter more than one by click+draging or shift+clicking, and enter multiple digits at once.
Sum constraints
- Each cell has a corresponding index from \(0-81\). Constraints consist of any number of these indices and a sum they should make.
- To create a new constraint: select the desired cells and click the '+' button at the bottom. This will create a new row. You can then modify the sum value itself by clicking on it.
- Constraints can be edited by clicking on the corresponding `Cell ixs` entry, and reselecting squares.
- Unlike some other solvers, constraints can overlap arbitrarily.
Solving
Finally, when you have a board complete… Hit solve. The first solution found will be displayed, or a warning if no solution is possible.
The solver itself
The solver's been a learning exercise for rust and as such - the code isn't excellent. There are some neat tricks in it though!
It uses bitsets to improve performance, where possibilities for each cell are stored as a single binary number. If [1,3,5] were candidates for a square this is stored as \(000010101\) - where the least significant digit corresponding to 1 being a candidate etc. When a number is placed in a square it can be removed as a candidate from row/column/box efficiently using binary digits.
Sums constraints are calculated and cached in a hashset. If a constraint required us to make 8 in 3 squares there are only two ways to do it: [1,2,5] and [1,3,4]… And is similarly stored as a mask: \(000011111\) - corresponding to all numbers that could make up a solution. This can be used to quickly mask squares. The calculation of these constraints is done quickly and lazily with some dynamic programming tricks - i.e. knapsack.
When a digit is placed in a cell two things happen - its value is removed as a candidate from row/column/box, then sum constraints containing the cell are updated and the resulting new mask is reapplied to the remaining squares.
If those rules are enough to solve the puzzle - it's extremely fast. It can solve up to 2 million sudokus per second! Otherwise, it must guess a square and backtrack if it reaches a contradiction. It tries to guess the square with the fewest candidates.
It's lack of more complex solving techniques; hidden singles, naked pairs etc. means it struggles to compare with the fastest solvers of the day. For comparison it solves ~900/second of the 'puzzles5_forum_hardest' puzzles in the previous link (best=24,001/sec), while averaging a whopping 1456 guesses/puzzle (best=64 guesses). Not too bad for a weekend though… And it may in fact be the fastest killer sudoku solver!