Sudoku
Sudoku owns my time. It’s a very simple puzzle. A 9×9 grid divided into 9 3×3 boxes. Each row, column, and box must have digits 1-9 meaning that no row, column, or box can have the same number in it.
Sounds simple right?
Some can be solved by simple logic, deduction and elimination. Other, more difficult problems require techniques named X-Wing (star wars?), Swordfish (computer hackering?) and 3-D Medusa. These advance sudoku problem solving techniques require things like disjoint sets, (graph) coloring, bipartite (graphs), strong and weak edges (and accompanying vertices). Sounds to me like graph theory.
The general problem of solving Sudoku puzzles on n^2 x n^2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
Solving Sudoku puzzles can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. Taken from wikipedia
NP-completeness – sounds like CS373/473 to me. I think people like these because anyone can solve the easy problems. The solution contains numbers which aren’t esoteric like some words found in crossword puzzles. I guess I like it because it appeals to my nerdiness and gives me a challenge that is solvable by logical and analytical thinking. Either way, I’m addicted.