The Chaos Within Sudoku 2012

The mathematical structure of sudoku is like "hard constraint satisfaction problems".

• constraint satiscaction problems are defined as sets of objects whose state must satisfy a number of limitations
  • very broad, but the eight queens puzzle is another example, the map 4-colouring problem from Math 239 is another example
• Sudoku is one of Karp's 21 NP-complete problems for N x N grids
  • it is called an exact cover type problem
  • exact cover in math just means that for a set S of subsets of set X, we want to find a subset of S, S * that contains every element in X exactly once
  • exact cover problem is a decision problem and is NP-complete
• Boolean Satisfiability Problem (SAT) tries to find out whether a boolean expression is satisifiable (some possible combination of variables s.t. the expression is TRUE)
  • first proven NP-complete problem

TODO