The Shattered Urn

Tuesday, November 20, 2018 - 10:00 to 11:00

Thackeray 427

Speaker Information
John Burkardt
University of South Carolina, Columbia

Abstract or Additional Information

Sudoku, Instant Insanity, Tangrams, the Soma Cube, Pentomino Tiling and even 
logic puzzles like "Who Owns the Zebra" can all be thought of as tasks in which 
a "shattered" or disassembled object needs to be reconstructed from a 
collection of pieces.  

Whether you are fixing a broken Greek urn, or solving a puzzle, a standard 
technique involves backtracking, that is, making a series of guesses until 
you hit a dead end, and then backing up to the last choice you made and trying 
the next one.  This is a steady and sure procedure, but can be slow, and 
doesn't provide much insight into the problem.

Many of these problems can instead, almost magically, be turned into the task 
of solving an underdetermined linear system, something we know a lot about.  
I will concentrate on the particular case of tiling a region with polyominoes.