I have been spending way too much time on sudoku. There are a few interesting questions around, but most have been solved. There is one remaining big open question: What is the fewest number of clues a sudoku can have? The current record is 17. Here is an example of a puzzle with 17 clues. . 9 8 . . . . . . . . . . 7 . . . . . . . . 1 5 . . . -------+-------+------- 1 . . . . . . . . . . . 2 . . . . 9 . . . 9 . 6 . 8 2 -------+-------+------- . . . . . . . 3 . 5 . 1 . . . . . . . . . 4 . . . 2 . (It is convention that a sudoku puzzle has a unique solution. If there are multiple solutions then the puzzle is not valid. An embarrassing such puzzle was carved into a hillside in England by Sky TV to promote their new sudoku tv show. See http://www.sudoku.org.uk/blunder.htm Also the 3rd puzzle printed by the Daily Telegraph had multiple solutions. Their setter had only just learned the puzzle and hadn't perfected his program yet.) Say you want to construct a sudoku with 16 clues. (This has been discussed on lots of internet chat sites.) Start with a given completed sudoku grid. Then you might look for sets like the following: 1 2 . ... ... . . . ... ... . . . ... ... 2 . 1 ... ... . . . ... ... . . . ... ... . 1 2 ... ... . . . ... ... . . . ... ... It's clear that 1 and 2 can be interchanged IN THESE 6 CELLS ONLY and we still have a valid completed grid. Conclusion: in any sudoku puzzle with this completed grid as the answer, one of these 6 numbers must be a clue. Call a set like this an unavoidable set, or a fated set, or something. The size of a fated set can vary, there are some obvious ones with 4 elements: 12. ... ... ... ... ... ... ... ... 21. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Of course not every grid has an unavoidable set like this one. If a set of clues does not intersect every fated set, it cannot be used as a set of clues for a sudoku puzzle. So, for a given grid, we want all its fated sets and then we want to search for a set of size 16 that intersects all the fated sets. If we find one, we may also need to check that the puzzle is solvable from these clues, I'm not sure about this bit. Clearly we would like to choose the grid so that it has relatively few fated sets. What types of grids have this property? Are there clever ways to search for the set of size 16? Is this approach feasible? This may be related to the automorphism groups of sudokus, and also to the matrix arising from the dancing links method. I will post a bit about these in other messages. This is already too long. Gary McGuire