[原创][网页游戏]数独生成算法及实例

[

程序修正 2015/02/23

补充及订正方法：iphone上的Safari会自动对看起来像是电话号码的数字串（包括已经加入连字符或括号格式化过的）添加电话链接，点击之后会询问用户是否想要拨打该号码。

关闭方法：

<meta name="format-detection" content="telephone=no" />

单独开放方法：

<a href="tel:13800138000">13800138000</a>

]

1.完整数独生成算法（规律性低，非随机，不保证全可能性）

2.非唯一解挖坑

3.正确性判断

4.使用localStorage，制作继续游戏功能

5.简单使用jquery mobile

6.在某日早上，在地铁时代报上看到数独游戏，就想在网页上做一个试试

百度google了下生成算法，没有发现有效的生成算法，很多是随机回滚类型[还有错误的算法。。。]

在纸上随意写写，排排，发现还有个简单的生成数独的方法，但没有论证是否可以生成所有数独

在线：

http://wangxinsheng.herokuapp.com/sudoku

截图：

1.完整数独生成算法（规律性低，非随机，不保证全可能性）

1-1.

简单列出排列：

1-2.

扩展到X，会发现个规律，如下图：

1-3.

可以像1-2一样，以行为路径，由小到大或由大到小

也可以以列为路径，由小到大或由大到小

随后，在1-3，4-6，7-9（不打乱小方块1-9排列的前提下），进行列交换[红色]（或行交换[蓝色]）

1-4.

1-3行或列交换后，

由于是9*9的格子，他自己有着一定规律，进行单元格的交换[3对]，能使得生成的数独可能性更多

下图以[行为路径，由小到大]为例，进行单元格的交换

1-5.

js代码实例：

  1 /*generate init data list*/  2 var startNum = Math.round(1+Math.random()*8) // the start number  3 ,type = Math.round(1+Math.random()*3)  4 ,goOnNum = startNum  5 ,bolckStartNum = startNum; //1:leftToRight,somallToBig;2:leftToRight,bigToSmall;3:topToBottom,somallToBig;4:topToBottom,bigToSmall  6 /* 1-1,1-2. generate init data list */  7 for(var i = 0;i<9;i++){  8     for(var j = 0;j<9;j++){  9         if(type<=2){ 10             this.genSudoArr[i][j] = goOnNum; 11         }else{ 12             this.genSudoArr[j][i] = goOnNum; 13         } 14         if((j+1)%9!=0){ 15             if(type==1 || type==3){ 16                 goOnNum=(goOnNum+1)>9?1:(goOnNum+1); 17             }else{ 18                 goOnNum=(goOnNum-1)<1?9:(goOnNum-1); 19             } 20         }else{ 21             if(type==1 || type==3){ 22                 if((i+1)%3!=0){ 23                     goOnNum=(startNum+3)>9?(startNum-6):(startNum+3); 24                     startNum = goOnNum; 25                 }else{ 26                     goOnNum=(bolckStartNum+1)>9?(bolckStartNum-8):(bolckStartNum+1); 27                     bolckStartNum = goOnNum; 28                     startNum = goOnNum; 29                 } 30             }else{ 31                 if((i+1)%3!=0){ 32                     goOnNum=(startNum-3)<1?(startNum+6):(startNum-3); 33                     startNum = goOnNum; 34                 }else{ 35                     goOnNum=(bolckStartNum-1)<1?(bolckStartNum+8):(bolckStartNum-1); 36                     bolckStartNum = goOnNum; 37                     startNum = goOnNum; 38                 } 39             } 40         } 41     } 42 } 43 /* 1-4. change the data list by cell AND repeat 3 times is better*/ 44 var changeType01 = 0,from01,to01; 45 for(var i = 0;i<3;i++){ 46     for(var m = 0;m<3;m++){ 47         // change No 48         changeType01 = Math.round(Math.random()*2); 49         switch(changeType01){ 50             case 1: from01 = 0;to01 = 1;break; 51             case 2: from01 = 1;to01 = 2;break; 52             default: from01 = 0; to01 = 2; 53         } 54         // do change, do not use tmp var 55         for(var h = 0; h<3; h++){ 56             var x1 = parseInt(from01)+parseInt(i)*3; 57             var x2 = parseInt(to01)+parseInt(i)*3; 58             var y = parseInt(m)+parseInt(h)*3; 59             if(type<=2){ 60                 // change col 61                 this.genSudoArr[x1][y]+=this.genSudoArr[x2][y]; 62                 this.genSudoArr[x2][y]=this.genSudoArr[x1][y]-this.genSudoArr[x2][y]; 63                 this.genSudoArr[x1][y]-=this.genSudoArr[x2][y]; 64             }else{ 65                 // change row 66                 this.genSudoArr[y][x1]+=this.genSudoArr[y][x2]; 67                 this.genSudoArr[y][x2]=this.genSudoArr[y][x1]-this.genSudoArr[y][x2]; 68                 this.genSudoArr[y][x1]-=this.genSudoArr[y][x2]; 69             } 70         } 71     } 72 } 73 /* 1-3. change the data list by line and column*/ 74 var changeType = 0,from,to; 75 //line 76 for(var i = 0;i<3;i++){ 77     changeType = Math.round(Math.random()*2); 78     switch(changeType){ 79         case 1: from = 0+i*3;to = 1+i*3;break; 80         case 2: from = 1+i*3;to = 2+i*3;break; 81         default: from = 0+i*3; to = 2+i*3; 82     } 83     // do change, do not use tmp var 84     for(var j = 0; j<9; j++) 85     { 86         this.genSudoArr[from][j]+=this.genSudoArr[to][j]; 87         this.genSudoArr[to][j]=this.genSudoArr[from][j]-this.genSudoArr[to][j]; 88         this.genSudoArr[from][j]-=this.genSudoArr[to][j]; 89     } 90 } 91 //column 92 for(var i = 0;i<3;i++){ 93     changeType = Math.round(Math.random()*2); 94     switch(changeType){ 95         case 1: from = 0+i*3;to = 1+i*3;break; 96         case 2: from = 1+i*3;to = 2+i*3;break; 97         default: from = 0+i*3; to = 2+i*3; 98     } 99     // do change, do not use tmp var100     for(var j = 0; j<9; j++)101     {102         this.genSudoArr[j][from]+=this.genSudoArr[j][to];103         this.genSudoArr[j][to]=this.genSudoArr[j][from]-this.genSudoArr[j][to];104         this.genSudoArr[j][from]-=this.genSudoArr[j][to];105     }106 }

2.非唯一解挖坑

简单的随机非重复挖坑

 1     // 1.copy all data 2     var me = this; 3     for(var i = 0;i<me.genSudoArr.length;i++){ 4         for(var j = 0;j<me.genSudoArr[i].length;j++){ 5             me.questionData[i][j] = me.genSudoArr[i][j]; 6         } 7     } 8     // 2.cut data to answerLst 9     var x,y;10     for(var i = 0;i<me.randomCount;i++){11         x = Math.round(Math.random()*8);12         y = Math.round(Math.random()*8);13         var key = x+'-'+y;14         if(!hasKey()){15             me.answerData.push({"key":key,"val":"","r":x,"c":y});16             me.questionData[x][y] = "";17         }else{18             i--;19         }20     }21 22     function hasKey(key){23         for(var i = 0;i<me.answerData.length;i++){24             if(me.answerData[i].key == key){25                 return true;26             }27         }28         return false29     }

3.正确性判断

行，列，块判断即可

 1     var hasString = ""; 2     /*check row*/ 3     for(var i = 0;i<tmp.length;i++){ 4         hasString = ""; 5         for(var j = 0;j<tmp[i].length;j++){ 6             if(tmp[i][j]=="" || hasString.indexOf(tmp[i][j]+'')<0) 7                 hasString += tmp[i][j]+''; 8             else{                         9                 //console.log(hasString,tmp[i][j],"error:"+(i+1)+","+(j+1));10                 alert("error:"+(i+1)+","+(j+1));11                 return;12             }13         }14     }15     /*check col*/16     hasString = "";17     for(var i = 0;i<tmp.length;i++){18         hasString = "";19         for(var j = 0;j<tmp[i].length;j++){20             if(tmp[j][i]=="" || hasString.indexOf(tmp[j][i]+'')<0)21                 hasString += tmp[j][i]+'';22             else{23                 //console.log(hasString,tmp[j][i],"error:"+(j+1)+","+(i+1));24                 alert("error:"+(j+1)+","+(i+1));25                 return;26             }27         }28     }29     /*check block*/30     hasString = "";31     for(var c = 0;c<9;c++){32         var fromR,fromC;33         fromR = Math.floor(i/3) * 3;34         fromC = (i%3) * 3;35         for(var i = 0;j<fromR;i++){36             for(var j = 0;j<fromC;j++){37                 if(tmp[i][j]=="" || hasString.indexOf(tmp[i][j]+'')<0)38                     hasString += tmp[i][j]+'';39