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.]
How hard, on average, is the resulting Sudoku?
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.
----
A challenge for numerical topology:
Most materials -- cloth, paper, tape, plastic sheet, wood,
metal, can stretch or shrink a bit in order to fit together.
Even glass is slightly flexible. People who work with these
materials for a living -- tailors, carpenters, ... -- have
an intuitive feeling for how much their medium can stretch,
bend, or twist, and what manipulations are required to make
the pieces fit. Here's the challenge: Come up with a theory
of making things fit -- a theory of wrinkles, shims, pleats,
and all the other myriad tricks, fiddles, and adjustments
that the subject experts know.
Rich
