数独(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)的破解 我们可以想象每个格子可填入的数字是可以得知的，但这不是唯一的,应先填入哪个数字就是个问题，另外先填哪一个格子也是不确定的，那么如何开始填才最佳呢
这里我们需要引入一个概念——
