Nick Baxter wrote:
Difficulty would be hard to determine by a brute force solver. I image that they are rated by human test solvers, or a program that uses a range of solving rules and rates the level of complexity reached during the heuristic search.
I researched this just a little bit not long ago, and found that at least some places have a list of solving rules, of increasing complexity, and the rating is based on the highest-complexity rule that you need to use to solve it. In particular, a puzzle is "easy" iff it can be solved by repeatedly filling in a box with the only number that can go there. But surely there's no agreed-upon standard for ratings, and I can't locate my source for that information, so it's just about useless. Donning my editor's cap, let me mention that I'd be happy to run an Intelligencer column on sudoku-related material -- gotta cache in on those hot fads, don'cha know -- if anyone has something interestingly mathematical to say about it. Noteworthy facts: just a month or so ago, Bertram Felgenhauer managed to enumerate solutions; there are 6,670,903,752,021,072,936,960 9x9 latin squares which obey the 3x3 subgrid constraint. I learned this from the very good Wikipedia article: http://en.wikipedia.org/wiki/Sudoku Oh, and the general solution problem on an n^2 x n^2 grid is NP-complete, as proved by Yato and Seta. --Michael -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.