前几天在玩数独游戏的时候，产生了一个大胆的想法：
数独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个，我觉得海星。有时候有点慢，少数情况下甚至会卡死，排除了算法的问题，我也不知道怎么回事。。。
下面演示一个，后面附上解数独器，你们也可以试一试：
题目：
求解，只求出了一种情况：
做个对比：
说了这么多，该贴出代码了。除了对算法的改进外，我用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;}//获取数独答案public int[][] getAnswer(){return this.Answer;}
}//游戏界面
class UI{private JFrame gameUI;private JLabel gameGrid;//数独81宫格private SudokuMaker game;//数独private JLabel[][] smallGrid;//数独小格子private UserEvents [][] mouseListen;//监听器public UI(){gameUI=new JFrame();gameUI.setVisible(true);gameUI.setLayout(null);gameUI.setSize(600,430);gameUI.setResizable(false);//不允许窗口最大化gameUI.setLocationRelativeTo(null);JButton bt1=new JButton("生成新数独");gameUI.add(bt1);bt1.setBounds(400,10,100,20);bt1.addActionListener(new OtherGameEvent());JButton bt2=new JButton("显示答案");gameUI.add(bt2);bt2.setBounds(400,110,100,20);bt2.addActionListener(new ShowAnswer());gameGrid=new JLabel();gameGrid.setBounds(10,10,365,365);gameUI.add(gameGrid);java.net.URL imgURL = Main.class.getResource("/img/Grid.jpg");gameGrid.setIcon(new ImageIcon(imgURL));gameGrid.setOpaque(true);Font font=new Font("宋体",Font.BOLD,25);smallGrid=new JLabel[9][9];mouseListen=new UserEvents[9][9];for(int i=0;i<9;++i){for(int j=0;j<9;++j){smallGrid[i][j]=new JLabel("",JLabel.CENTER);gameGrid.add(smallGrid[i][j]);mouseListen[i][j]=new UserEvents(smallGrid[i][j],i,j,false);smallGrid[i][j].setFont(font);smallGrid[i][j].setBounds(j*40+1,i*40+1,40,40);smallGrid[i][j].addMouseListener(mouseListen[i][j]);}}newGame();}//新游戏private void newGame(){game=new SudokuMaker();int [][]gameArr=game.getArr();for(int i=0;i<9;++i){for(int j=0;j<9;++j){if(gameArr[i][j]!=0){ smallGrid[i][j].setText(gameArr[i][j]+"");mouseListen[i][j].setUse(false);smallGrid[i][j].setForeground(Color.black);}else{smallGrid[i][j].setText(null);mouseListen[i][j].setUse(true);}}}}private class ShowAnswer implements ActionListener{@Overridepublic void actionPerformed(ActionEvent arg0) {// TODO Auto-generated method stubfor(int i=0;i<9;++i){for(int j=0;j<9;++j){if(mouseListen[i][j].getUse()==true){smallGrid[i][j].setText(game.getAnswer()[i][j]+"");smallGrid[i][j].setForeground(Color.BLUE);mouseListen[i][j].setUse(false);}}}}}private class OtherGameEvent implements ActionListener{@Overridepublic void actionPerformed(ActionEvent arg0) {// TODO Auto-generated method stubnewGame();}}private class UserEvents implements MouseListener{private JTextArea jta;private JLabel focus;//聚焦private int gridX;private int gridY;private boolean isUse;//是否开启事件public UserEvents(JLabel f,int y,int x,boolean u){focus=f;gridX=x;gridY=y;isUse=u;jta=new JTextArea();jta.setBounds(5,5,30,30);jta.setVisible(false);jta.setOpaque(false);jta.setFont(new Font("宋体",Font.BOLD,25));focus.add(jta);}@Overridepublic void mouseClicked(MouseEvent arg0) {// TODO Auto-generated method stubif(isUse==true){focus.setBorder(BorderFactory.createLineBorder(Color.red,5));jta.setVisible(true);focus.setText(null);}}@Overridepublic void mouseEntered(MouseEvent arg0) {// TODO Auto-generated method stub}@Overridepublic void mouseExited(MouseEvent arg0) {// TODO Auto-generated method stubint X=arg0.getX(),Y=arg0.getY();if(isUse==true){if(X<=0 || X>=40 || Y<=0 || Y>=40){focus.setBorder(BorderFactory.createLineBorder(Color.red,0));try{int t=new Integer(jta.getText());if(t>0 && t<10){game.getArr()[gridY][gridX]=0;if(SudokuMaker.isTrue(game.getArr(), gridX, gridY, t)==true){focus.setForeground(Color.green);}else{focus.setForeground(Color.red);}game.getArr()[gridY][gridX]=t;}focus.setText(jta.getText());}catch(Exception e){jta.setText(null);}jta.setVisible(false);}}}@Overridepublic void mousePressed(MouseEvent arg0) {// TODO Auto-generated method stubif(this.isUse==true){focus.setBorder(BorderFactory.createLineBorder(Color.red,5));}}@Overridepublic void mouseReleased(MouseEvent arg0) {// TODO Auto-generated method stub}public void setUse(boolean u){this.isUse=u;if(u==true){jta.setText(null);}else{focus.setBorder(BorderFactory.createLineBorder(Color.red,0));}}public boolean getUse(){return isUse;}}}public class Main {//测试方法public static void main(String arg[]){new UI();}
}//开发工具包
class DevTools{public static void showAnswer(int arr[][]){System.out.println("\n答案：");for(int i[]:arr){for(int j:i){System.out.print(j);}System.out.println();}System.out.println();}public static void showGame(int arr[][]){System.out.println("\n题目：");int total=0;for(int i[]:arr){for(int j:i){System.out.print(j);if(j==0){++total;}}System.out.println();}System.out.println("挖空数："+total);}
}
--解数独器：可以用来验证一下是不是唯一解：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<windows.h>
int a[9][9],total;int bfs(int x,int y,int num){int m,n,time=0;int dir[9][2]={{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1},{0,0}};for(int i=0;i<9;++i){m=x+dir[i][0],n=y+dir[i][1];if(num==a[n][m]){++time;}if(time>1){return 0;}}return 1;
}int judge(int x,int y,int n){int t=0;for(int i=0;i<9;++i){if(a[y][i]==n){++t;if(t>1){return 1;}}}t=0;for(int i1=0;i1<9;++i1){if(a[i1][x]==n){++t;if(t>1){return 1;}}}int nu,m;if(bfs(1+(x/3)*3,1+(y/3)*3,n)==0){return 1;}return 0;
}void sel(int x,int y){if(y<9){if(x<9){if(a[y][x]==0){for(int i=1;i<=9;++i){a[y][x]=i;if(judge(x,y,i)==0){sel(x+1,y);}a[y][x]=0;}}else{sel(x+1,y);}}else{sel(0,y+1);}}else{++total;printf("\n\n");for(int i=0;i<9;++i){for(int j=0;j<9;++j){printf("%d",a[i][j]);}printf("\n");}}
}int main(){printf("输入格式：\n");printf("005300000\n800000020\n070010500\n400005300\n010070006\n003200080\n060500009\n004000030\n000009700\n");printf("\n\n请输入数独题：\n");for(int i=0;i<9;++i){int line;scanf("%d",&line);for(int j=0;j<9;++j){a[i][8-j]=line%10;line/=10;}} sel(0,0);Sleep(100000);return 0;
}
