1.数独游戏（⽣成题⽬解唯⼀）
前⼏天在玩数独游戏的时候，产⽣了⼀个⼤胆的想法：
数独app上的题⽬都是现成的，⼲脆⾃⼰写⼀个可以随机⽣成数独的程序算了
⼀、需求提出：
1.随机⽣成数独题⽬，要求该题⽬有解（有⼀个解最好）；
2.当填数违反数独操作（填到题⽬原本的数字去了，填数违规等）时，禁⽌操作，弹出提⽰;
3.当81格都填满时，判断对错;
⼆、需求分析
总：
需求2,3相对简单，尤其是需求3，都禁⽌违规操作了，填满81格不就赢了吗？也许是当初没有给⾃⼰再次组织语⾔的机会，提出了这么的需求，核⼼问题就是需求1。
需求1
⾸先得到⼀个9*9，符合数独规则的矩阵，然后随机挖空不就⾏了吗？所以需求1的问题转化为如何得到⼀个随机9*9数独矩阵。
第⼀个想出来的⽅法是⽤搜索算法，在每⼀个格⼦随机⽣成1-9的数字，然后判断符不符合规则，再下⼀个。
这个算法的缺点是效率感⼈，81个格⼦，每个格⼦的数字都要判断，每个格⼦的数字还都是随机⽣成的，效率能不感⼈吗？
优点是还没付诸⾏动就被否定了，给程序编写省下了不少时间
第⼆个想法就相对可靠了，先在随机在若⼲个格⼦上⽣成随机数（这些随机数也要符合数独规则），这样就变成了⼀道题⽬，然后让电脑⽤搜索算法求解，只要能解出⼀种，就停⽌解题，并且选取这种解答作为随机9*9数独矩阵以及本题的答案（标准答案)。解不出也没有关系重新⽣成随机数再重新解过就得了。
这个⽅法可⾏度很⾼，优点很多，其中最重要的优点是我在刷蓝桥杯时曾经写过⼀个解数独的程序
经过调试，我把随机数个数设置在了15，既不会因为太少⽽使得随机数在矩阵上分布不均匀，⼜保证不会因为数字太多，答案太少⽽影响⽣成效率。
得到这个矩阵（终盘）后，经过简单的随机挖空，⼀道数独题⽬就随机⽣成了。
但是这样的话并不能保证数独有唯⼀解啊，怎么办呢？
后来发现，虽然求出了很多的解，但是那些不同的解和标准答案前⾯总是从某个格⼦后开始跑偏，开始和标准答案不⼀样的
举个栗⼦，对于数独数组Array（⼆维数组，横纵下标都是从0~8)，有好⼏个解都是从Array[5][5]开始和答案不⼀样的。
以Array[5][5]为分界
Array[0][0]~Array[5][4]和标准答案⼀样，⽽Array[5][5]~Array[8][8]就开始跑偏，和标准答案不⼀样了。
好，问题就出现在Array[5][5]上，说明我挖了Array[5][5]这个空，导致了答案不唯⼀。这个空挖不得，赶紧补回去。
当然。把Array[5][5]补回去不⼀定答案就变得唯⼀了，不过这时候问题不是出在Array[5][5]上。
补回Array[5][5]后还有多个答案，那这些答案的Array[5][5]肯定是⼀样的，说明这些答案不是从Array[5]
[5]开始跑偏的，⽽是在Array[5][5]后。即这些答案第⼀个和标准答案不同的空不是Array[5][5]，
把那个不⼀样的空Array[m][n]补回（令Array[m][n]=标准答案[m][n]）就⾏了
所以，题⽬解唯⼀的算法呼之欲出了：
求出所有可能的解，从Array[0][0]~Aarry[8][8]逐个和答案进⾏对⽐，令第⼀个与答案不同的空Array[m][n]=标准答案[m][n]即可
经本⼈验证，确实达到了唯⼀解的效果，挖空能达到40~50个，我觉得海星。有时候有点慢，少数情况下甚⾄会卡死，排除了算法的问题，我也不知道怎么回事。。。
下⾯演⽰⼀个，后⾯附上解数独器，你们也可以试⼀试：
题⽬：
求解，只求出了⼀种情况：
htmlborder
做个对⽐：
说了这么多，该贴出代码了。除了对算法的改进外，我⽤Java重写了游戏，从此⽀持键⿏操作，摆脱⼩⿊框啦！--背景图：Grid.jpg 362*362。在src下创建img⽂件夹，然后把图⽚丢进去就⾏了
--代码：为了⽅便使⽤，我把所有类放在了⼀个java⽂件下。src下创建Main包，然后放进去就⾏了
package Main;
import java.awt.Color;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.Random;
import javax.swing.BorderFactory;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JTextArea;
/
*⽣成随机数独
* 流程：
* 1.⽣成9*9空⽩数独数组
* 2.随机往数独数组填数
* 3.DFS⽣成数独标准解（即数独数组81个格⼦都填满数字）
* 4.先挖n个空，对挖完空的数独进⾏求解（全部）
* 5.将所有解与标准解进⾏对⽐，将不⼀样的地⽅记录下。这些地⽅不允许被被挖空
*/
class SudokuMaker {
private int[][] Arr;//临时数组
private int [][]Sudoku;
private int [][]Answer;//答案
private int [][]Game;
public SudokuMaker(){
this.Arr=new int[9][9];
this.Sudoku=new int[9][9];
this.Answer=new int[9][9];
rand();
DFS(Arr,0,false);
diger();
DevTools.showGame(Game);
DevTools.showAnswer(Answer);
}
private void rand(){
int t=0;
int x,y,num;
//先往数组⾥⾯随机丢t个数
while(t<15){//t不宜多，否则运⾏起来耗费时间；t也不宜少，否则⽣成的游戏看起来⼀点也不随机
x=new Random().nextInt(9);
y=new Random().nextInt(9);
num=new Random().nextInt(9)+1;
if(Arr[y][x]==0){
if(isTrue(Arr,x,y,num)==true){
Arr[y][x]=num;++t;
}
}
}
}
//判断该数字填写的地⽅是否符合数独规则
public static boolean isTrue(int arr[][],int x,int y,int num){//数字横坐标；数字纵坐标；数字数值
//判断中单元格（3*3）
for(int i=(y/3)*3;i<(y/3+1)*3;++i){
for(int j=(x/3)*3;j<(x/3+1)*3;++j){
if(arr[i][j]==num ){return false;}
}
}
//判断横竖
for(int i=0;i<9;++i){
if((arr[i][x]==num || arr[y][i]==num)){return false;}
}
return true;
}
//深度优先搜索寻
//绝对有很多种解法，但是我们只需要第⼀个解出来的
private boolean flag=false;//判断是否不再求解
int total=0;
private void DFS(int arr[][],int n,boolean all){//arr是数独数组，n是探索深度（⼀共81个格⼦，深度为81,n为0~80），是否要求全部解  //n/9为格⼦的纵坐标，n%9为格⼦的横坐标
if(n<81){
//如果已经求出了⼀种解，终⽌递归就⾏了，不⽤继续求下去了
if(flag==true && all==false){return;}
if(arr[n/9][n%9]==0){
for(int i=1;i<10;++i){
if(isTrue(arr,n%9,n/9,i)==true){      arr[n/9][n%9]=i;
DFS(arr,n+1,all);
arr[n/9][n%9]=0;
}
}
}else{
DFS(arr,n+1,all);
}
}else{
if(all==false){
flag=true;
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
Sudoku[i][j]=arr[i][j];
Answer[i][j]=arr[i][j];
}
}
}else{
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
if(arr[i][j]!=Answer[i][j]){
Game[i][j]=Answer[i][j];
i=10;j=10;
break;
}
}
}
}
}
}
//给数独挖空
//保证仅有⼀解
private void diger(){
int t=55;
Game=new int[9][9];
while(t>0){
int x=new Random().nextInt(9);
int y=new Random().nextInt(9);
if(Sudoku[y][x]!=0){
Sudoku[y][x]=0;--t;
}
}
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
Game[i][j]=Sudoku[i][j];
}
}
DFS(Sudoku,0,true);
}
//获取最终数独
public int[][] getArr(){
return this.Game;
}
//获取数独答案

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。