Sudoku, Latin squares, Geometry, and Hall's condition - Professor Peter Cameron

Professor Peter CAmeron

The second Dame Kathleen Ollerenshaw lecture took place on the 24th October 2007.

Solutions to Sudoku puzzles form a special case of a type of combinatorial designs called gerechte designs, invented in the 1950's for designing experiments in agricultural research. Finding such designs includes such problems as finding a Latin square orthogonal to a given Latin square. Also, the problem of completing such a design from partial information was developed in statistics.

The experience of solving Sudoku puzzles suggests that finding such designs (with some values given) is hard. It is known that completing a partial Latin square is NP-hard. Some similar problems about gerechte designs are unsolved. The problem can be formulated to look like Hall's marriage theorem, but it is not known whether there are conditions analogous to Hall's which are necessary and sufficient for a solution.

Further conditions can be imposed. One variant, due to Robert Connelly, has particularly close connections to several topics in finite geometry: spreads, resolutions, and perfect codes.

▲ Up to the top