I’ve done a quite small (47 LOC) Haskell solution for this a couple of years ago. Turns out solving Sudokus is quite simple. Blogpost/Code. The basis is just going over the whole grid, pruning possibilities per field, filling in the ones with just one possible solution. Rinse and repeat until you’re done. Very fun exercise to learn a new language as well.
Depends on the level of inference one is willing to implement.
Full inference for each row/column/square individually plus something called shaving/singleton arc consistency/several other names which means to do the hypothesis test for each square/value pair “If this square was assigned this value, would that lead to an inconsistency?” is enough to solve all 9x9 Sudokus without search empirically. For details, see Sudoku as a Constraint Problem by Helmut Simonis.
Nice write-up of a basic Sudoku solver.
For more interesting instances to try (since 9x9 Sudoku is trivial to solve for a computer), see the list of examples included starting here: https://github.com/Gecode/gecode/blob/master/examples/sudoku.cpp#L672
A 25x25 Sudoku is surprisingly hard to solve actually.
I’ve done a quite small (47 LOC) Haskell solution for this a couple of years ago. Turns out solving Sudokus is quite simple. Blogpost/Code. The basis is just going over the whole grid, pruning possibilities per field, filling in the ones with just one possible solution. Rinse and repeat until you’re done. Very fun exercise to learn a new language as well.
Um, resolving single candidates is not enough to solve most Sudoku puzzles.
Yeah generally on “hard” boards you’ll have to randomly pick a value for a couple, then do a DFS on that choice and subsequent choices.
Depends on the level of inference one is willing to implement.
Full inference for each row/column/square individually plus something called shaving/singleton arc consistency/several other names which means to do the hypothesis test for each square/value pair “If this square was assigned this value, would that lead to an inconsistency?” is enough to solve all 9x9 Sudokus without search empirically. For details, see Sudoku as a Constraint Problem by Helmut Simonis.
That just sounds hugely frustrating. I usually just solve them by elimination, but I don’t really do super hard ones.