|
|
SUDOKU
http://dist2.ist.tugraz.at/sudoku/
Sudoku is a very popular puzzle, so just google for it to get a description, programs etc. An important thing about Sudoku is that there always exists a solution and that this solution has to be unique! Writing a program which finds this solution is not very difficult, and you can find many such programs on the web. Average Sudokus (from newspapers etc.) have about 25-30 given numbers. Usually a Sudoku becomes more involved, the less numbers are given. But be careful, this is not a universal rule: there are also hard Sudokus with many givens, and easy ones with only a few givens.
An interesting question is, how few givens are sufficient such that a Sudoku still has a unique solution. A trivial lower bound is 8: assume only 7 numbers are given. Then in any solution you can interchange all occurrences of two non given digits, and thus there are always at least two different solutions. Surprisingly so far no better lower bound has been obtained by mathematical reasoning. All known minimal Sudokus with a unique solution have 17 given numbers, see http://people.csse.uwa.edu.au/gordon/sudokumin.php for a collection of over 41000 such puzzles (still growing).
Thus the current range for the smallest number of clues (given numbers) that a Sudoku puzzle (with one unique solution) can have is 8 to 17. The goal of our project is to close this gap. To this end we start with 92248 sets with 8 primary givens (digits 1-8, representing all possibilities w.r.t. symmetry, relabeling etc.) and extend them by adding more givens, and checking for uniqueness. (A more detailed and mathematical description of our approach will follow.)
During a first evaluation phase of our program we have been able to show that at least 11 numbers have to be given. Thus the current range is 11..17. Using distributed computing our approach will step by step increase the lower bound, until one user either finds a new minimal example or we can show that no such examples exist for up to 16 givens.
 |
|
发表于 2007-9-1 10:47:59
发表于 2007-9-1 16:01:39
发表于 2007-9-1 18:59:27
发表于 2007-9-1 22:57:55
