?

前幾天在玩數(shù)獨(dú)游戲的時(shí)候，產(chǎn)生了一個(gè)大膽的想法：

數(shù)獨(dú)app上的題目都是現(xiàn)成的，干脆自己寫一個(gè)可以隨機(jī)生成數(shù)獨(dú)的程序算了

?

?

一、需求提出：

1.隨機(jī)生成數(shù)獨(dú)題目，要求該題目有解（有一個(gè)解最好）；

2.當(dāng)填數(shù)違反數(shù)獨(dú)操作（填到題目原本的數(shù)字去了，填數(shù)違規(guī)等）時(shí)，禁止操作，彈出提示;

3.當(dāng)81格都填滿時(shí)，判斷對(duì)錯(cuò);

?

二、需求分析

總：

需求2,3相對(duì)簡(jiǎn)單，尤其是需求3，都禁止違規(guī)操作了，填滿81格不就贏了嗎？也許是當(dāng)初沒有給自己再次組織語言的機(jī)會(huì)，提出了這么傻缺的需求，核心問題就是需求1。

?

需求1

首先得到一個(gè)9*9，符合數(shù)獨(dú)規(guī)則的矩陣，然后隨機(jī)挖空不就行了嗎？所以需求1的問題轉(zhuǎn)化為如何得到一個(gè)隨機(jī)9*9數(shù)獨(dú)矩陣。

?

第一個(gè)想出來的方法是用搜索算法，在每一個(gè)格子隨機(jī)生成1-9的數(shù)字，然后判斷符不符合規(guī)則，再下一個(gè)。

這個(gè)算法的缺點(diǎn)是效率感人，81個(gè)格子，每個(gè)格子的數(shù)字都要判斷，每個(gè)格子的數(shù)字還都是隨機(jī)生成的，效率能不感人嗎？

優(yōu)點(diǎn)是還沒付諸行動(dòng)就被否定了，給程序編寫省下了不少時(shí)間

?

第二個(gè)想法就相對(duì)可靠了，先在隨機(jī)在若干個(gè)格子上生成隨機(jī)數(shù)（這些隨機(jī)數(shù)也要符合數(shù)獨(dú)規(guī)則），這樣就變成了一道題目，然后讓電腦用搜索算法求解，只要能解出一種，就停止解題，并且選取這種解答作為隨機(jī)9*9數(shù)獨(dú)矩陣以及本題的答案（標(biāo)準(zhǔn)答案)。解不出也沒有關(guān)系重新生成隨機(jī)數(shù)再重新解過就得了。

這個(gè)方法可行度很高，優(yōu)點(diǎn)很多，其中最重要的優(yōu)點(diǎn)是我在刷藍(lán)橋杯時(shí)曾經(jīng)寫過一個(gè)解數(shù)獨(dú)的程序

經(jīng)過調(diào)試，我把隨機(jī)數(shù)個(gè)數(shù)設(shè)置在了15，既不會(huì)因?yàn)樘俣沟秒S機(jī)數(shù)在矩陣上分布不均勻，又保證不會(huì)因?yàn)閿?shù)字太多，答案太少而影響生成效率。

?

得到這個(gè)矩陣（終盤）后，經(jīng)過簡(jiǎn)單的隨機(jī)挖空，一道數(shù)獨(dú)題目就隨機(jī)生成了。

?

但是這樣的話并不能保證數(shù)獨(dú)有唯一解啊，怎么辦呢？

后來發(fā)現(xiàn)，雖然求出了很多的解，但是那些不同的解和標(biāo)準(zhǔn)答案前面總是從某個(gè)格子后開始跑偏，開始和標(biāo)準(zhǔn)答案不一樣的

舉個(gè)栗子，對(duì)于數(shù)獨(dú)數(shù)組Array（二維數(shù)組，橫縱下標(biāo)都是從0~8)，有好幾個(gè)解都是從Array[5][5]開始和答案不一樣的。

以Array[5][5]為分界

Array[0][0]~Array[5][4]和標(biāo)準(zhǔn)答案一樣，而Array[5][5]~Array[8][8]就開始跑偏，和標(biāo)準(zhǔn)答案不一樣了。

好，問題就出現(xiàn)在Array[5][5]上，說明我挖了Array[5][5]這個(gè)空，導(dǎo)致了答案不唯一。這個(gè)空挖不得，趕緊補(bǔ)回去。

當(dāng)然。把Array[5][5]補(bǔ)回去不一定答案就變得唯一了，不過這時(shí)候問題不是出在Array[5][5]上。

補(bǔ)回Array[5][5]后還有多個(gè)答案，那這些答案的Array[5][5]肯定是一樣的，說明這些答案不是從Array[5][5]開始跑偏的，而是在Array[5][5]后。即這些答案第一個(gè)和標(biāo)準(zhǔn)答案不同的空不是Array[5][5]，

把那個(gè)不一樣的空Array[m][n]補(bǔ)回（令Array[m][n]=標(biāo)準(zhǔn)答案[m][n]）就行了

所以，題目解唯一的算法呼之欲出了：

求出所有可能的解，從Array[0][0]~Aarry[8][8]逐個(gè)和答案進(jìn)行對(duì)比，令第一個(gè)與答案不同的空Array[m][n]=標(biāo)準(zhǔn)答案[m][n]即可

?

經(jīng)本人驗(yàn)證，確實(shí)達(dá)到了唯一解的效果，挖空能達(dá)到40~50個(gè)，我覺得海星。有時(shí)候有點(diǎn)慢，少數(shù)情況下甚至?xí)ㄋ?#xff0c;排除了算法的問題，我也不知道怎么回事。。。

下面演示一個(gè)，后面附上解數(shù)獨(dú)器，你們也可以試一試：

題目：

求解，只求出了一種情況：

做個(gè)對(duì)比：

?

說了這么多，該貼出代碼了。除了對(duì)算法的改進(jìn)外，我用Java重寫了游戲，從此支持鍵鼠操作，擺脫小黑框啦！

--背景圖：Grid.jpg 362*362。在src下創(chuàng)建img文件夾，然后把圖片丟進(jìn)去就行了

--代碼：為了方便使用，我把所有類放在了一個(gè)java文件下。src下創(chuàng)建Main包，然后放進(jìn)去就行了

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;/*生成隨機(jī)數(shù)獨(dú)* 流程：* 1.生成9*9空白數(shù)獨(dú)數(shù)組* 2.隨機(jī)往數(shù)獨(dú)數(shù)組填數(shù)* 3.DFS生成數(shù)獨(dú)標(biāo)準(zhǔn)解（即數(shù)獨(dú)數(shù)組81個(gè)格子都填滿數(shù)字）* 4.先挖n個(gè)空，對(duì)挖完空的數(shù)獨(dú)進(jìn)行求解（全部）* 5.將所有解與標(biāo)準(zhǔn)解進(jìn)行對(duì)比，將不一樣的地方記錄下。這些地方不允許被被挖空*/ class SudokuMaker {private int[][] Arr;//臨時(shí)數(shù)組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;//先往數(shù)組里面隨機(jī)丟t個(gè)數(shù)while(t<15){//t不宜多，否則運(yùn)行起來耗費(fèi)時(shí)間；t也不宜少，否則生成的游戲看起來一點(diǎn)也不隨機(jī)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;}}}}//判斷該數(shù)字填寫的地方是否符合數(shù)獨(dú)規(guī)則public static boolean isTrue(int arr[][],int x,int y,int num){//數(shù)字橫坐標(biāo)；數(shù)字縱坐標(biāo)；數(shù)字?jǐn)?shù)值//判斷中單元格（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;}//深度優(yōu)先搜索尋找//絕對(duì)有很多種解法，但是我們只需要第一個(gè)解出來的private boolean flag=false;//判斷是否不再求解int total=0;private void DFS(int arr[][],int n,boolean all){//arr是數(shù)獨(dú)數(shù)組，n是探索深度（一共81個(gè)格子，深度為81,n為0~80），是否要求全部解//n/9為格子的縱坐標(biāo)，n%9為格子的橫坐標(biāo)if(n<81){//如果已經(jīng)求出了一種解，終止遞歸就行了，不用繼續(xù)求下去了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;}}}}}}//給數(shù)獨(dú)挖空//保證僅有一解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);}//獲取最終數(shù)獨(dú)public int[][] getArr(){return this.Game;}//獲取數(shù)獨(dú)答案public int[][] getAnswer(){return this.Answer;} }//游戲界面 class UI{private JFrame gameUI;private JLabel gameGrid;//數(shù)獨(dú)81宮格private SudokuMaker game;//數(shù)獨(dú)private JLabel[][] smallGrid;//數(shù)獨(dú)小格子private UserEvents [][] mouseListen;//監(jiān)聽器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("生成新數(shù)獨(dú)");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 {//測(cè)試方法public static void main(String arg[]){new UI();} }//開發(fā)工具包 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("挖空數(shù)："+total);} }

?

--解數(shù)獨(dú)器：可以用來驗(yàn)證一下是不是唯一解：

#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請(qǐng)輸入數(shù)獨(dú)題：\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; }

?

總結(jié)

以上是生活随笔為你收集整理的1.数独游戏（生成题目解唯一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。