Back to Research-Papers
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