## Wednesday, May 25, 2005

### Complexity and Sudoku

A Chicago undergrad Amanda Redlich gave a presentation and used the shorthand ity (Complex-ity). Clever. Of course this should never be confused with ity.

Today's Chicago Tribune has an AP article on the British craze of a Japanese number game Sudoku. In this puzzle you have a 9x9 grid subdivided into 9 3x3 grids. The goal is to fill the full grid with numbers 1 through 9 such that each number appears exactly once on each row, column and subgrid given some initial partial setting.

As a computational complexity theorist, I immediately wondered how hard is the generalized game on an n2xn2 grid. A little googling shows the problem is NP-complete, shown in a 2003 Master's thesis of Takayuki Yato at the University of Tokyo. His proof uses a simple reduction from the Latin Squares problem proved NP-complete by Charles Colbourn.

1. A natural combinatorial question on Sudoku: In how many ways can an empty
n^2 x n^2 board be filled? I have been thinking about it for the past one week, without any success :-(