4 ms·
I don't even know how to play Sudoku.
by barbecue_sauce 5y ago
I don't even know how to play Sudoku.
- marginalia_nu 5y agowhile (!isSolved(sudoku)) { sudoku = generateNextPermutation(sudoku); } Solved (eventually).
- Cthulhu_ 5y agoA bogosolver is a valid approach. I mean it'll take forever, but it's valid.
- marginalia_nu 5y agoI plead the halting problem.
- wccrawford 5y agoThere are a limited number of permutations. Assuming it's not choosing them randomly, it'll finish eventually... If the hardware doesn't die first.
- tonyedgecombe 5y agoYou can solve it via brute force if you cut off branches that don't satisfy the rules: https://github.com/tonyedgecombe/Sudoku/blob/master/Sudoku/Program.cs https://github.com/tonyedgecombe/Sudoku/blob/master/Sudoku/P... It's not 1ms but it's not that slow either.
- Cthulhu_ 5y agoYou 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.
- wdb 5y agoDidn't know either till then ;) But asking something like this after four different interviews, though. I was already pretty tired from the other interviews