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.
A natural combinatorial question on Sudoku: In how many ways can an empty
ReplyDeleten^2 x n^2 board be filled? I have been thinking about it for the past one week, without any success :-(
I have found some comments about this. Check out Just how many Sudoku combinations are there?
ReplyDeleteHello, 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.
ReplyDeleteWikipedia's Mathematics of Sudoku article seems to be concerned mainly with questions of counting and classifying sudoku problems.
ReplyDeleteThe 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"
ReplyDelete"Computer Aided Sudoku" free helper solver excel game. Download http://perso.wanadoo.fr/sudoku.laviron/
ReplyDeleteWhat's wrong with most Sudoku games on the Internet?
ReplyDeleteDownload Sudoku Arena - multimedia Sudoku with correct algorithm. Or read more about what's wrong with most Sudoku games on the internet.