数独(su doku )的生成与破解 一、 数独游戏的规则 数独(sudoku)，起源于瑞士，于1970 年代由美国的一家数学逻辑游戏杂志首先发表，当时名为Number Place。及后在日本大力推广下得以发扬光大，于1984 年取名“数独”，即“独立的数字”的省略，在一个9×9 的方格中，有 81 个小方格组成，然后又分 9 个大块，每块由3x3 的方格组成，就是中国的九宫阵。 游戏规则：“九宫阵”是一个9×9 的方阵，它是由九个“九宫格”（图中黑色实线围住的3×3的方阵）构成的，每个九宫格又是由九个小格子构成的，在每个小格子里面填上 1～9 中的数字，使得每个数字在“九宫阵”的每行、每列、每个九宫格中均只出现一次。 游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字，当然你只能用 1～9 之间的9 个数字。如下图就是一个数独游戏。 题 目 答 案 二、 数独(sudoku)的生成 基本思路： 为了保证生成的数独一定有解，就要先得到了一个完整的数独（可以想象所有满足条件的组合是很多的），然后从格子里面随机挖掉一些数字就可以了。那么如何得到一个完整数独呢？我们可以这样想先给每一行（或列）填入一个不同的数，然后用“数独破解”的方法去完成，这就 OK 了。 步骤如下： 1．在第 i 行 (i=0~8)随机找个格子 map[i][j] (j=0~8)填入本行数i+1； 2．用“数独求解”（见数独(sudoku)的生成）的方法产生一个完整数独； 3．从 81 个格子里面随机挖去 n 个数字。 三、 数独(sudoku)的破解 我们可以想象每个格子可填入的数字是可以得知的，但这不是唯一的,应先填入哪个数字就是个问题，另外先填哪一个格子也是不确定的，那么如何开始填才最佳呢？ 这里我们需要引入一个概念——格子的不确定度，一个格子可以填的数字的个数称为它的不确定度。所以我们需要用递归下面的做法： １．我们去寻找不确定度最小的格子； ２．确定这个格子可以填的数字； ３．填入一个数字后，递归。 随着填上去数字增多，剩余空格上的不确定度也会降低，如果某个格子上的不确定度降到1，那这个格子可以先确定下来，如果降到了0，哦，非常遗憾，在前面的填数中一定是填错了，你不得不回退。 四、 唯一解的问题 这里有一问题，我们需要的是我们生成的数独是否具有唯一解？是的，按上面数独生成的过程是不能保证的。为了保证数独有唯一解，应该...
VIP
