Rich wrote:

A Sudoku question for the experts:

Suppose I generate a random Sudoku puzzle: Select a completed sudoku at random from the gazillion or so distinct sudokus. Then delete entries at random, stopping when nothing further can be removed without making the problem ambiguous. [This is a poor man's substitute for selecting a truly random minimal puzzle, which I suspect is much harder to do.]

this algo should generate a truly random minimal sudoku: (1) start with an empty grid (2) add a clue with random value 1..9 into one of the 81 cells chosen at random (3) if the resulting puzzle has no solution then goto (1) (4) if the resulting puzzle has more than one solution goto (2) (5) if the puzzle is not minimal then goto (1) (6) print the sudoku it's not so fast as your method.

How hard, on average, is the resulting Sudoku?

84 is the average number of placements = backtracking steps which my solver needs to process such a puzzle. Average number of clues is 24.4. 42% can be solved by the basic techniques "naked single,hidden single" , In that case 81-c placements are made, where c is the number of initially given clues.

Are there very difficult Sudokus? Everything I've seen can be solved with at worst "single guessing", where a branch is tried and one of the possibilities leads to a quick contradiction without sub-guessing, or both branches lead to a same-forced- value. I.e., if the correct "cell to branch on" is selected, one of the branches dies and no recursion is necessary.

Some rare sudokus require sub-guessing, but level-2-guessing is probably always sufficient. Probably all sudokus can be solved with 2 "magic cells", that is there exist 2 further clues which when added allow a solution with the basic techniques. Here are lists of hard sudokus: http://magictour.free.fr/top95 http://magictour.free.fr/top1234 http://magictour.free.fr/top44 the last one is for 16*16 sudokus. You can rate them by the number of solver-placements with http://magictour.free.fr/suexrate.exe -Guenter.