数独(sudoku)的生成与破解
一、 数独游戏的规则
数独(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
- 2
前往页