Su Doku is one of the very few games that transcend culture and education. Unlike some cross-word puzzles popular in the U.S., Su Doku doesn't require a mastery of the English language and a large vocabulary. It works directly with logic and reasoning in their "purest" form possible. Although its rules are culturally independent, it is a hybrid of both Eastern and Western cultures, as the present game was shaped through a long trend of import/export among several developed countries.
I'm a little bit intrigued by this game and have a few questions I'm hoping some of the math gurus here may help me with.
1. Do all Su Doku puzzles have a unique solution? ( My guess is NO.)
2. For a Su Doku puzzle to have a unique solution, must it satisfy certain conditions (such as the minimal number of the Su Doku numbers used and the essential pattern--e.g. number distribution in the grids) ?
3. If so, what are these conditions?
4. Most importantly, can we answer the above questions without resorting to any fancy math toolkit (like the graph theory) so that even people like myself can appreciate such an answer?
- Re: Su Doku Questionsposted on 05/18/2006
A fair question. Mathematicians have asked it as well. I think it's been proved that either finding a solution to Sudoku or determining how many solutions there are is NP-complete, which means there is no polynomial time algorithm (not yet at least for any NP-complete problem). Don't know the details. You can always enumerate all the possible solutions though. - Re: Su Doku Questionsposted on 05/18/2006
浮生老师,您给我送一个email好吗?mayacafe@prodigy.net - posted on 05/19/2006
浮生 wrote:
A fair question. Mathematicians have asked it as well. I think it's been proved that either finding a solution to Sudoku or determining how many solutions there are is NP-complete, which means there is no polynomial time algorithm (not yet at least for any NP-complete problem). Don't know the details. You can always enumerate all the possible solutions though.
Thanks for the reply. Maybe it's just my personal bias or even ignorance. I somehow feel an analytical prove is always "superior" to, or at least more elegant than, a numerical solution. Discrete sets of solutions don't always tend to prove. Many times they merely show what solutions could or should be, given the initial conditions. But intuitively, one might expect to have a simpler approach to such a (perhaps deceptively) "simple" game. A 4x4 Su Doku might be a good place start for those tenured math professors who are no longer under the pressure to publish or secure research funds.:)
- posted on 05/24/2006
Fengzi wrote:
Su Doku is one of the very few games that transcend culture and education. Unlike some cross-word puzzles popular in the U.S., Su Doku doesn't require a mastery of the English language and a large vocabulary. It works directly with logic and reasoning in their "purest" form possible. Although its rules are culturally independent, it is a hybrid of both Eastern and Western cultures, as the present game was shaped through a long trend of import/export among several developed countries.
I'm a little bit intrigued by this game and have a few questions I'm hoping some of the math gurus here may help me with.
1. Do all Su Doku puzzles have a unique solution? ( My guess is NO.)
2. For a Su Doku puzzle to have a unique solution, must it satisfy certain conditions (such as the minimal number of the Su Doku numbers used and the essential pattern--e.g. number distribution in the grids) ?
3. If so, what are these conditions?
4. Most importantly, can we answer the above questions without resorting to any fancy math toolkit (like the graph theory) so that even people like myself can appreciate such an answer?
I am not expert, but here is my view.
1) No. For an exmaple, if there is only 1 number in a 9x9 su doku puzzle, surely you will have n solutions
2) Yes.
3) I do not know the minimal conditions required for the unique solution, but i do think it can be solved with some mathematic theories.
4) Not sure. Try to find an answer for a su doku might be easy, but try to find out these minimum conditions would be very tricky. - posted on 05/25/2006
ed wrote:
I am not expert, but here is my view.
1) No. For an exmaple, if there is only 1 number in a 9x9 su doku puzzle, surely you will have n solutions
2) Yes.
3) I do not know the minimal conditions required for the unique solution, but i do think it can be solved with some mathematic theories.
4) Not sure. Try to find an answer for a su doku might be easy, but try to find out these minimum conditions would be very tricky.
Thanks for your reply. With regard to your view on (1), I came to the same conclusion along the exact same vein of analysis. The problem with that approach, however, is that it really begs the question as to what is a Su Doku game. Clearly, no one would call it Su Doku something that only has the form or appearance of a Su DoKu game but in substance only has a single number, although in theory such an arrangement may be a possibility. Therefore, this gives rise to, or at least is now related to, the subsequent inquiries into the minimal conditions. Stated differently, we need to have a better, meaningful "definition" of the game...But I'm with you on the remaining issues. - posted on 05/25/2006
Fengzi wrote:
Thanks for your reply. With regard to your view on (1), I came to the same conclusion along the exact same vein of analysis. The problem with that approach, however, is that it really begs the question as to what is a Su Doku game. Clearly, no one would call it Su Doku something that only has the form or appearance of a Su DoKu game but in substance only has a single number, although in theory such an arrangement may be a possibility. Therefore, this gives rise to, or at least is now related to, the subsequent inquiries into the minimal conditions. Stated differently, we need to have a better, meaningful "definition" of the game...But I'm with you on the remaining issues.
I have done a search through google, and found some websites which may be interested for you. To summary up, the possible number of sudoku grid for 9x9 board is 5472730538, and the minimum number of initial numbers required to have a unique solution on 9X9 grid is 17 (but so far it is not confirmed the 17 is the lowest limit yet).
Here are some URLs for your reference
http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html http://www.sudoku.org.uk/discus/messages/5/13.html?1141670456 http://www.sudokutoday.com/sudoku-algorithm.html http://blogs.warwick.ac.uk/fangz/entry/unsolved_problems_in/
Hope that is useful for you.
cheers - posted on 05/26/2006
I have done a search through google, and found some websites which may be interested for you. To summary up, the possible number of sudoku grid for 9x9 board is 5472730538, and the minimum number of initial numbers required to have a unique solution on 9X9 grid is 17 (but so far it is not confirmed the 17 is the lowest limit yet).
Thanks a lot for the research, especially for the nice summary. 17 is an interesting number. It's a prime. So on average we need about 2 numbers for every 3x3 unit. That seems to be minimal, doesn't it? And it makes sense to me. Although each unit (or block) has 9 numbers with many possible permutations, since every unit interacts with other adjacent 6 rows/columns of numbers, somehow, that reduces the total degree of freedom. 9-6=3, which is very close to 2. This number (17) seems to make sense to me (although my math may not. :)
Please paste HTML code and press Enter.
(c) 2010 Maya Chilam Foundation