3 ms·
You have a 9x9 grid, subdivided into 3x3 blocks. The goal is to ensure that every row, column, and block has the numbers 1-9, so that no row, column or block ha
by Cthulhu_ 5y ago
You have a 9x9 grid, subdivided into 3x3 blocks. The goal is to ensure that every row, column, and block has the numbers 1-9, so that no row, column or block has a duplicate number. The puzzle will have some numbers filled in, the rest is up to the person filling it in.
I wrote a solver for it back in school, it... wasn't the best? But it worked. The one solution I built solved it like I did - go through every row, column and block, then every number, and ask "is this number possible here" - look for conflicts. The next iteration was "is there only one number possible in this space".
Of course, the teachers were expecting a more brute force approach; I forgot the name, but basically it involved iterating over every space, then every number; if the number fits, move on to the next square; if no numbers fit, backtrack to the previous space and iterate on that number. It solved everything within a second or so, but it was really brute force.
- xxs 5y agoconstant propagation is the standard way to solve soduku.
- mannykannot 5y agoSudoku is a nice little 'hello world' problem for constraint modeling languages, such as MiniZinc. https://www.minizinc.org/ https://www.minizinc.org/
- mynameisash 5y agoI tried writing a sudoku solver using what I figured were standard algorithmic approaches. It was a mess and didn't really work. Then I wrote one with SAT. I think it was 60 LOC, super easy to understand, and ran in about 0.4 sec.
- pdonis 5y agoSome puzzles cannot be solved with constraint propagation alone, but require trial and error at some point.