while (!isSolved(sudoku)) {
    sudoku = generateNextPermutation(sudoku);
  }

Solved (eventually).

A bogosolver is a valid approach. I mean it'll take forever, but it's valid.

You 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/P...

It's not 1ms but it's not that slow either.

I plead the halting problem.

There are a limited number of permutations. Assuming it's not choosing them randomly, it'll finish eventually... If the hardware doesn't die first.

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.

constant propagation is the standard way to solve soduku.

Sudoku is a nice little 'hello world' problem for constraint modeling languages, such as MiniZinc.

https://www.minizinc.org/

I 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.

Some puzzles cannot be solved with constraint propagation alone, but require trial and error at some point.

Didn't know either till then ;) But asking something like this after four different interviews, though. I was already pretty tired from the other interviews