数独游戏题目
——————————————————————————
2019年6月15日
mark：给朋友玩了一下，评价是比较简单，难度不大，因为
挖空数量不够。暑假有时间就升级一下算法，多挖几个空
——————————————————————————
前几天在玩数独游戏的时候，产生了一个大胆的想法：
数独APP上的题目都是现成的，干脆自己写一个可以随机生成数独的程序算了
一、需求提出：
1.随机生成数独题目，要求该题目有解（有一个解最好）；
2.当填数违反数独操作（填到题目原本的数字去了，填数违规等）时，禁止操作，弹出提示;
3.当81格都填满时，判断对错;
二、需求分析
总：
需求2,3相对简单，尤其是需求3，都禁止违规操作了，填满81格不就赢了吗？也许是当初没有给自己再次组织语言的机会，提出了这么傻缺的需求，核心问题就是需求1。
需求1
首先得到一个9*9，符合数独规则的矩阵，然后随机挖空不就行了吗？所以需求1的问题转化为如何得到一个随机9*9数独矩阵。
第一个想出来的方法是用搜索算法，在每一个格子随机生成1-9的数字，然后判断符不符合规则，再下一个。
这个算法的缺点是效率感人，81个格子，每个格子的数字都要判断，每个格子的数字还都是随机生成的，效率能不感人吗？
优点是还没付诸行动就被否定了，给程序编写省下了不少时间
第二个想法就相对可靠了，先在随机在若干个格子上生成随机数（这些随机数也要符合数独规则），这样就变成了一道题目，然后让电脑用搜索算法求解，只要能解出一种，就停止解题，并且选取这种解答作为随机9*9数独矩阵以及本题的答案。解不出也没有关系重新生成随机数再重新解过就得了。
这个方法可行度很高，优点很多，其中最重要的优点是我在刷蓝桥杯时曾经写过一个解数独的程序
经过调试，我把随机数个数设置在了15，既不会因为太少而使得随机数在矩阵上分布不均匀，又保证不会因为数字太多，答案太少而影响生成效率。
得到这个矩阵（终盘）后，经过简单的随机挖空，一道数独题目就随机生成了。
但是这样的话并不能保证数独有唯一解啊，怎么办呢？
当时我没有想到，过了几个月后发现可以这样做：
挖完空后求解出所有情况，并与终盘对比（不用与第一个求解的对比，因为都是用DFS求解答案的，所以其实第一个答案就是终盘！），哪里不一样就不挖那里不就行了吗？
当然很明显有个缺陷：比如虽然与终盘有N处地方不一样，但是不一定要把N处全部填完啊，只填其中一部分就能保证与终盘一样了啊！而运用上面的做法显然不能挖更多的空。
所以下一步打算（打算而已！）这样改进：每次填1上一个不同的地方，然后再次求解，如果解还是不唯一就再填一个，反正用DFS求解快得一批！
经本人验证，确实达到了唯一解的效果，挖空能达到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{
@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub
for(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{
@Override
public void actionPerformed(ActionEvent arg0) {
// TODO Auto-generated method stub
newGame();
}
}
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);
}
@Override
public void mouseClicked(MouseEvent arg0) {
// TODO Auto-generated method stub
if(isUse==true){
focus.setBorder(BorderFactory.createLineBorder(Color.red,5));
jta.setVisible(true);
focus.setText(null);
}
}
@Override
public void mouseEntered(MouseEvent arg0) {
// TODO Auto-generated method stub
}
@Override
public void mouseExited(MouseEvent arg0) {
// TODO Auto-generated method stub
int 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);
}
}
}
@Override
public void mousePressed(MouseEvent arg0) {
// TODO Auto-generated method stub
if(this.isUse==true){
focus.setBorder(BorderFactory.createLineBorder(Color.red,5));
}
}
@Override
public 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;
}
相关阅读
真实的SSN资料获取器，亲切可用来注册 square刷卡器官方账号,美国POST机,国外网站 Lead,美国虚拟银行等！ 从国外某秘密网站VIP区下的
使用Java生成的ZIP压缩包解压时出现不可预料的压缩文件末端的解决方案 问题描述： 如下图所示，在解压Java程序生成的ZIP压缩包时出
Cupp是一款用Python语言写成的可交互性的字典生成脚本。尤其适合社会工程学，当你收集到目标的具体信息后，你就可以通过这个工具来智
logback 每天生成和大小生成 TimeBasedRollingPolicy
项目使用了logback，日志打印需要按照每天和大小生成日志，于是使用了TimeBasedRollingPolicy SizeBasedTriggeringPolicy[html] vie
matlab生成随机数的rand、randi和randn三种形式
matlab中关于随机数的产生有3种库函数，下面我们来看看它们的形式： 1、rand(…) 它是生成0~1之间（开环，不包含0和1两个数