My manager mentioned he was messing with some sudoku code so I thought I'd give it a go. I've pretty much ignored sudoku all my life and I've certainly never written code to solve one.
So I rolled my sleeves up and wrote some really crappy Python code expecting, at some future point, to have to introduce all kinds of fancy data structures to make things efficient in order to search the enormous space of possibilities. And what I found that there is almost no search required. The amount of backtracking is low, even for the puzzle labelled as "the hardest-ever sudoku".
Feeling very silly now. I thought everyone around me was solving these really hard combinatorial problems all day long.
Actually, there's a lesson here, one that I've met a few times. It's hard to guess how hard a combinatorial problem is. You can often immediately guess the log of the size of the problem space within an order of magnitude, but that means you can easily be off by a factor of trillions.
How hard it is on average (averaged over instances), at worst, or both?
