School Seminars and Colloquia

Sudoku: Strategy Versus Structure

Discrete Structures and Algorithms (Seminar)

by Professor Scott Provan


Institution: Department of Statistics and Operations Research, University of North Carolina
Date: Tue 15th June 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: Sudoku puzzles have become wildly popular in just the last few years, and quite a school has developed around classifying solution strategies for Sudoku puzzles. We give a simply-described set of strategies that solves about 90% of all Sudoku puzzles. This strategy class has two
interesting properties: one associated with the formulation of these puzzles as a set of interlocking assignment problems, and the other with their representation as the unique nonnegative solution to the associated set of assignment equations. We discuss this strategy, and indicate some interesting research problems in the area.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au