This work is licensed under a
Creative Commons License.
|
Wednesday, May 25, 2005
Complexity and Sudoku
Posted by Lance
A Chicago undergrad Amanda Redlich gave a presentation and used the shorthandity (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:35 PM
# 7 comments
-
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 :-(
-
-
Hello, my name is Lucy, and I am a student journalist at a high school in Maryland. I am writing an article on sudoku and I was curious to see if I could ask you a few questions or you could refer me to sources. My email is Lufromyer@gmail.com. Thank you so much.
-
Wikipedia's Mathematics of Sudoku article seems to be concerned mainly with questions of counting and classifying sudoku problems.
The work on counting contingency tables may also be relevant, although the problem differs in some important respects. It is: How many ways are there to fill in a matrix with natural numbers to achieve prescribed row and column sums? One approach is MCMC sampling. If I remember, there is even an exact solution in the case of 2-dimensional tables. Diaconis and Efron are among the people who have worked on this.
-
Whatever the complexity, a good strategy gives the solution. For example, search on Google "Computer aided sudoku"
-
"Computer Aided Sudoku" free helper solver excel game. Download http://perso.wanadoo.fr/sudoku.laviron/
-
What's wrong with most Sudoku games on the Internet?
Download Sudoku Arena - multimedia Sudoku with correct algorithm. Or read more about what's wrong with most Sudoku games on the internet.
Links to this post:
Weblog Home
Archives
