Hi Dan, There's a partial consensus on evaluating sudoku difficulty. People typically order logic techniques by perceived difficulty, then rate a puzzle by the most difficult technique it requires. Some sets of techniques have an obvious ranking, but disparate techniques have no universal consensus on difficulty. Many basic logic techniques are equivalent to a 9 rooks problem on one of four subgrids: a single value in rows/columns, or the set of all values in a row, a column, or a box. Finding a unique value in a cell or in a row/column/box is a rank 1 rooks deduction. Inferences requiring pairs are rank 2 deductions. Sudoku-ans give names like naked pair, hidden pair, or X-wing to rank 2 deductions. Any rank k rooks deduction has a dual rank 9-k deduction, so rank 4 deductions exhaust this set for standard sudokus. The set of basic sudoku deductions is generally agreed to consist of some N-rook deductions plus deductions based on box/row or box/column interactions. Most people exclude rank 4 rook deductions from the basic set, and some even exclude certain rank 3 deductions. The next addition to "advanced" deductions is "forcing chains". These are deductions of candidate exclusion or inclusion in the transitive closure of basic pairwise candidate implications. Sudoku-ans give names to subsets of forcing chains (e.g., bivalue or bilocation chains) and techniques that handle forcing chain subsets (e.g., simple coloring). The techniques above are not universal, but there's not much understanding of difficulty refinement beyond forcing chains. And from forcing chains and above there's little consensus on difficulty rating. I think the question of sudoku difficulty gives some interesting math questions to investigate. Best, - Scott
Thanks, Scott.
From the link you provided I see that another interesting question is, What is the smallest number n such that *every* sudoku solution can be reduced to n entries having that solution as its unique completion?
Also: Is there a consensus about how to evaluate the "difficulty" of a given sudoku puzzle? (I was suprised to read at that URL that some feel that a large proportion of puzzles of least known size -- 17 -- are "easy".)
--Dan --------------------------------------------------------------------------------
<<
What is the smallest number of filled squares that can uniquely determine an extension filling all 81 squares?
--Dan
There are many 17-clue sudokus known. The jury is still out whether a 16-clue sudoku exists. Specific sudoku grids which require 17+ clues are known.
If you require rotational symmetry of initial clue positions I think 18-clues in the minumum known.
Most of the 17-clue sudokus are not very difficult, so globally minimal clue count doesn't seem to correlate with difficulty.
See http://www.sudoku.com/forums/viewtopic.php?t=605 for an extensive discussion.