IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Sudoku and Graphs: Critical Sets

  • March 7, 2014
  • 11 a.m.
  • LeConte 312

Abstract

A Sudoku board consists of a 9 by 9 grid of "cells", in which each column, row, and "block" (one of nine 3X3 subgrids that tile the board) has each of the numbers 1 through 9 exactly once. A Sudoku "puzzle" is a partially filled-in board, and a "fair" puzzle is one that can be completed in exactly one way. Strong evidence exists that the the fewest number of "givens" (filled-in cells) in a fair puzzle is 17, but there is not yet a rigorous proof of this claim. It turns out that the question of the size of the smallest fair puzzle can be translated into a natural question about so-called "critical sets" in general graphs about which a growing literature exists. In fact, critical sets have made an appearance in several areas of discrete mathematics, albeit under a few different names. We discuss some of what is known about critical sets, and present several unsolved problems about them.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC