AVG谜题探索（08）------南茜·朱尔23水边の影中数独（Sudoku）解谜

ssfve

  
谜题：数独
) p( A% l0 v2 J/ x) l
数独是一种源自18世纪末的瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。
　　
" N) L) k& Y: a7 R2 }0 \) S1 A数独的基础是数字魔方，它的解也一定是数字魔方。制作一个数独，便是使用一个一般的数字魔方，盖住部分数字，成为一个拥有唯一解的数独。

数独前身为“九宫格”，最早起源于中国。数千年前，我们的祖先就发明了洛书，其特点较之现在的数独更为复杂，要求纵向、横向、斜向上的三个数字之和等于15，而非简单的九个数字不能重复。中国古籍《易经》中的“九宫图”也源于此，故称“洛书九宫图”。而“九宫”之名也因《易经》在中华文化发展史上的重要地位而保存、沿用至今。 现在已有多种手机装有数独游戏。
9 r! C, @2 I( |) _1 f) r  b/ p! Q
下面是我自己用C编写的一个解数独程序，这个程序只实现了一些简单的算法，因为我对数独的研究也只是皮毛，
程序的流程基本上是这样的，首先对9个数字建立9个9*9的数组，对9个宫格建立9个3*3的数组，对9行建立一个9*9的数组，对9列建立一个9*9的数组，
: R8 h0 `/ U. k& x5 V0 `我使用非常基础的方法读入用户输入的数据，然后进行各种排除，当得到一个数字后进行一次循环，进一步排除。
4 w: F9 g/ _% k( w. _
$ M  [; M' t. e5 V3 U# K: |该程序只能解决一些简单数独，多解的数独无法求解，复杂数独只会给出接近终解的解，原码就不发给大家了，程序是下面这个，欢迎大家讨论
$ x1 o! m8 O3 D" v' \1 I. F

ssfve

版主好心的话，可以像以前帖子一样帮我搞一张标题图片

deducemath

支持原创，尽管关于数独的算法已经很成熟了。
        虽然有些人不同意使用计算机程序破解那些精巧的谜题（见《计算机程序设计艺术（第4卷）（第0分册）》P9  “George Brewster, writing to Martin Gardner in 1963, expressed a widely held view as follows: ‘Feeding a recreational puzzle into a computer is no more than a step above dynamiting a trout stream. Succumbing to instant recreation.’  ”），然而，美妙的小谜题和谜题背后的一般化理论及算法都同样吸引人。
       有人说数独和华容道的前身15 puzzle都起源于洛书，其实它们没什么关系。与数独最相近的一个较早的谜题是36军官问题。15 puzzle则是十九世纪末发明的，并且发明人不是Sam Loyd。（见《The 15 Puzzle》 Jerry Slocum 著）
       提到洛书，我想到一件有趣的事。83版射雕华山论剑第5集中，郭靖黄蓉闯入瑛姑那所典雅的小宅子，正赶上神算子在解九宫图，嘴里念念有词，叹气连连。见他俩进来，神算子就让他们解题，说解不了就别想活着出去（有点像斯芬克斯的故事）。黄蓉说此题容易，神算子则一脸惊讶：“丫头，我研究那幅图研究了十几年，你真的那么有把握？……”看到这里我不禁失笑。
       数独近期被凯•摩根用来创作推理小说：《夺命数独》《密码数独》《杀手数独》《邪恶数独》。（都是比较低劣的作品。）

ssfve

Feeding a recreational puzzle into a computer is no more than a step above dynamiting a trout stream. Succumbing to instant recreation.
0 T; n2 E+ Y$ R3 S, U% Q其实我也觉得是这样的，数独只能算是一个特例，
计算机固然能够解决特例，
& x8 ^3 ^; `* F) s" S2 d但是用计算机解决一些一般化的理论更加重要一些