(See the sibling comment with a "10." in it for context.) 7. Seventeen Sudoku Clues. OK, this one is easy to describe :-). The question is how few clues a Sudo

(See the sibling comment with a "10." in it for context.) 7. Seventeen Sudoku Clues. OK, this one is easy to describe :-). The question is how few clues a Sudoku puzzle can have while still having a unique solution. The answer is 17. A bunch of 17-clue puzzles had already been found, so the "only" thing left to do was to prove that 16 clues never suffice. The proof was basically a big computer search, but with some clever innovations to make the search manageable. So the first step was to find all possible completed Sudoku grids. Someone else had already done that. It turns out that there are only about 5 billion "genuinely different" fully-solved Sudoku grids. So now all you have to do (ha!) is to check, for each fully-solved grid, every set of 16 clues, and verify that none leads to a unique solution. Of course this is ridiculously too big a search, and that's where the cleverness comes in. So, given a completed grid, you can identify some "unavoidable sets", sets of cells such that any solvable puzzle must include one clue from each such set. (They looked for unavoidable sets of size <=12.) And then you can find "hitting sets", sets of size 16 that intersect every one of these unavoidable sets that's been found. Any solvable 16-clue puzzle would need to have its clues form a hitting set. But something could be a hitting set and not a solvable puzzle, so once you've found all the hitting sets you have a bit of checking to do. And the cleverness lies in finding good ways of finding (enough) unavoidable sets, good heuristic ways of finding all the hitting sets (this problem is NP-complete in general), and efficient ways of testing each hitting set found to see whether it gives a puzzle with a unique solution. There are other mathematical tasks that can be formulated in terms of hitting sets (the paper by McGuire, Tugemann and Civario claims this is true for various problems in computational biology, software testing, databases, etc.); I don't know to what extent their ideas are actually applicable to any of those domains.