I like playing sudoku, and I suppose a lot of you out there like it as well. Well, here are a few questions that I proposed when I first starting to play sudoku. However, I havn't find answers to any of them. If you have a proof, send it to me.
Before I start, let's have 1 definition in place. A sudoku solution is a sudoku with all the entries filled and valid.
1. Does there exist a 3D sudoku solution?! 3D solution meaning, a 9x9x9 cube, such that the 27 slices of 2D sudoku (9 slices of sudoku on each direction, and 3 direction) are all valid sudoku solution. My quess is no, since the restrictions seems too hard. but that's only a wild guess.
2. Given a sudoku solution, define the number min_entry_needed, to be the minimum number of entries needed to gaurantee that particular sudoku solution. Of course, if one knows all 81 entries, then he has the solution. So 81 can't be the min_entry_needed for any sudoku solution. And of course, knowing only 1 entry is not going to get a unique solution. So the sudoku you see on newspaper, the entries that was given, will gaurantee a unique solution. But it might not be set of the minimum entries for that particular solution. Even more interesting, I might use other entries to greatly reduce the number of entries needed to get that solution.
So if we look at the set of all sudoku solution, on average, what is this min_entry_needed?
3. This one is even harder to describe. Suppose we come up with a set of "contradiction rules". For any un-finished sudoku, can we always apply this set of rule, and get a new entry. (So we will apply this set of rules again, to the sudoku with the newly added entry. Eventually, we'll get the solution). I think an example is needed to make this clear.
Suppose the set of rule only contains the rule "given a 3x3 square, one can only have the number 1-9 exactly once". So if you apply this set of rule to a sudoku, that has 8 numbers in all 9 of the square, then eventually you'll have the solution. But of course, this one single rule is not going to solve any sudoku. So, can anyone come up with this set of rules?
Friday, August 7, 2009
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment