3 ms·
> but it is faster if you start with the square that has the minimum number of choices available Alternatively, find the digit that, in its row/column/square/w
by Someone 1y ago
> but it is faster if you start with the square that has the minimum number of choices available
Alternatively, find the digit that, in its row/column/square/whatever, has the minimum number of choices available, and try each of them.
Ideally, combine the two and use Knuth’s dancing links algorithm (https://en.wikipedia.org/wiki/Dancing_Links https://en.wikipedia.org/wiki/Dancing_Links). It, at every step, picks the one of those two approaches that has the lower number of possibilities, typically getting a lower branching factor, without spending much more time at each step.
- Symmetry 1y agoIn Sudoku I usually find it's easier to just keep track of guesses on the stack, by `solve` recursively when you make a guess. That leads to nice memory re-use characteristics and without the overhead of link pairs that might end up blowing out your level 1 data cache. But you certainly want to be guessing on the most constrained spot you can. Also, bitfields are a nice compact way of representing the possible values of a space and your cpu can and or or all the possible values in parallel, plus determine the number of possibilities with a modern CPU's popcount instruction.
- uecker 1y agoThis is how I implemented it: https://codeberg.org/uecker/toys/src/branch/main/sudoku.c https://codeberg.org/uecker/toys/src/branch/main/sudoku.c