Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Complexity and Sudoku

Expand Messages
  • Lance
    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.
    Message 1 of 1 , May 25, 2005
    • 0 Attachment
      A Chicago undergrad Amanda Redlich gave a presentation and used the shorthand Complexity (Complex-ity). Clever. Of course this should never be confused with Reality.

      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.

      --
      Posted by Lance to Computational Complexity at 5/25/2005 01:35:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.