You mean for Sudoku? My code does a brute force recursive search with one optimisation - at each step it picks the cell with the fewest possibilities. For the problem labelled as "hardest-ever" it required less than 20,000 recursive calls. Ordinary "hard" problems seem to require of the order of hundreds of calls. It takes 81 calls just to place numbers in a 9x9 grid so hundreds are almost nothing.
Follow
Ah, sorry, I wanted to ask whether "it's hard to guess how hard" applies to average or worst case or both.
