王茂的博客

最近迷上了数独，手机上下了个Gameloft做的一款数独游戏，整日绞尽脑汁在那做。

先说下数独：数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。

■数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。儒家典籍《易经》中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。
■你知道是最先发明数独的吗？
1783年，瑞士数学家莱昂哈德·欧拉发明了一种当时称作“拉丁方块”的游戏，这个游戏是一个n×n的数字方阵，每一行和每一列都是由不重复的n个数字或者字母组成的。
■你知道是哪一本杂志最先推广数独的吗？
19世纪70年代，美国的一家数学逻辑游戏杂志《戴尔铅笔字谜和词语游戏》（Dell Puzzle Mαgαzines）开始刊登现在称为“数独”的这种游戏，当时人们称之为“数字拼图”，在这个时候，9×9的81格数字游戏才开始成型。
■你知道“数独”这个游戏名称是怎么来的吗？
1984年4月，在日本游戏杂志《字谜通讯Nikoil》上出现了“数独”游戏，提出了“独立的数字”的概念，意思就是“这个数字只能出现一次”或者“这个数字必须是惟一的”，并将这个游戏命名为“数独”（SU DOKU），从此，这个游戏开始风靡全球。

推荐个在线玩的地方： http://www.sudoku.name/index-cn.php

好了，大家开始玩的时候再推荐一个有关数独的分布式计算项目：

 http://dist2.ist.tugraz.at/sudoku/

使用的是BOINC平台，所以想做这个项目先下载安装一个BOINC的平台软件。来看看这个项目的介绍：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.

 关于BOINC和其他分布式计算请访问:中国分布式计算总站论坛