Defining sets in combinatorial arrays

Abstract:

A defining set for an array is a partially filled-in array with precisely one completion subject to some kind of combinatorial constraint. (For example, a Sudoku puzzle!) We examine what is known about the defining sets of two quite different arrays: Latin squares and (0,1)-matrices. Intriguingly, while these designs may superficially seem quite different, empirical evidence suggests that in certain cases they have the same minimum defining set size: exactly one quarter of the total size of the design. We call this ratio the surety of a type of design; thus Latin squares are conjectured to have a surety of 1/4. We show that a 2m x 2m (0,1)-matrix with constant row and column sum m has surety equal to 1/4 and explain why a problem which appears difficult to solve for Latin squares becomes tractable for (0,1)-matrices.