数独(sudoku)的生成与破解

《数独(sudoku)的生成与破解》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数独(sudoku)的生成与破解一、数独游戏的规则数独(sudoku)，起源于瑞士，于1970年代由美国的一家数学逻辑游戏杂志首先发表，当时名为NumberPlace。及后在日本大力推广下得以发扬光大，于1984年取名“数独”，即“独立的数字”的省略，在一个9×9的方格中，有81个小方格组成，然后又分9个大块，每块由3x3的方格组成，就是中国的九宫阵。游戏规则：“九宫阵”是一个9×9的方阵，它是由九个“九宫格”（图中黑色实线围住的3×3的方阵）构成的，每个九宫格又是由九个小格子构成的，在每个小格子里面填上1～9中的数

2、字，使得每个数字在“九宫阵”的每行、每列、每个九宫格中均只出现一次。游戏开始前会有一些格子上写好了数，你需要在剩下的格子里填数，真到把所有格子填满，并且要求，任何一行或一列或者一个小九宫中没有相同的数字，当然你只能用1～9之间的9个数字。如下图就是一个数独游戏。题目答案二、数独(sudoku)的生成基本思路：为了保证生成的数独一定有解，就要先得到了一个完整的数独（可以想象所有满足条件的组合是很多的），然后从格子里面随机挖掉一些数字就可以了。那么如何得到一个完整数独呢？我们可以这样想先给每一行（或列）填入一个不同的数，

3、然后用“数独破解”的方法去完成，这就OK了。步骤如下：1．在第i行(i=0~8)随机找个格子map[i][j](j=0~8)填入本行数i+1；2．用“数独求解”（见数独(sudoku)的生成）的方法产生一个完整数独；3．从81个格子里面随机挖去n个数字。三、数独(sudoku)的破解我们可以想象每个格子可填入的数字是可以得知的，但这不是唯一的,应先填入哪个数字就是个问题，另外先填哪一个格子也是不确定的，那么如何开始填才最佳呢？这里我们需要引入一个概念——格子的不确定度，一个格子可以填的数字的个数称为它的不确定度。所以

4、我们需要用递归下面的做法：１．我们去寻找不确定度最小的格子；２．确定这个格子可以填的数字；３．填入一个数字后，递归。随着填上去数字增多，剩余空格上的不确定度也会降低，如果某个格子上的不确定度降到1，那这个格子可以先确定下来，如果降到了0，哦，非常遗憾，在前面的填数中一定是填错了，你不得不回退。一、唯一解的问题这里有一问题，我们需要的是我们生成的数独是否具有唯一解？是的，按上面数独生成的过程是不能保证的。为了保证数独有唯一解，应该从哪儿考虑呢？我的思路是：从完整数独中挖格子的过程中去分析。根据数独破解的方法，在破解过程

5、中每次要寻找的最小不确定度的那个格子，如果每次找到的这个格子可填的数字都仅为１个（最小不确定度为１）时，那么得到的解一定唯一。这样就给我们启发，我们在挖格子时，每挖一个格子，也去检测最小不确定度的格子的不确定度。如果这个不确定度大于１，则就要重新这次挖格子。另外也有可能挖遍所有的格子（程序中我设的上限是81次）也没有合适解时，那么要中止这次操作，这时就要从重新生成一个数独。二、游戏的难易程序这个问题我是这么考虑的，只要生成的数独中的空格数（blank）越多，那么就越难。所以在些程序中我设置三个级别：１　容易：　bla

6、nk=33~35；２　中等：　blank=36~38；３　困难：　blank=39~41；三、源程序#ifndefSUDOKU_RICK_0701_#defineSUDOKU_RICK_0701_classCSudoku{intmap[9][9];intblanks;intsmod;intsolves;intcheck(int,int,int*);voiddfs();public:enum{ANY=0,ALL=1};CSudoku(int);CSudoku::CSudoku(int*data);voidSudokuG

7、enerator(int);　//随机生成数独,n越大越难voidSudokuGenerator(int*data);　//人工指定数独//virtual~CSudoku();voiddisplay();　//显示数独intresolve(intmod=ALL);　//解数独voidanalyze();};#endif#include"stdio.h"#include"stdlib.h"#include"time.h"#include"iostream"#include"iomanip"//要用到格式控制符using

8、namespacestd;CSudoku::CSudoku(intn){intj;j=rand()%3;blanks=n+j;SudokuGenerator(blanks);cout<