填坑：数独解法算法

大家好，欢迎来到IT知识分享网。

引言

三年前给家里小朋友弄的小东西，存在偶发性的生成时间不稳定的情况，上篇文章中已经说了解决方案，这里小小实现了一下，目前生成游戏时间稳定可行。

顺便把解法完成了。

下图为测试结果（难度越高[挖空越多]，解出的结果越没有唯一性）：

算法说明

这种类似的问题绝大部分人第一想到的肯定是递归法，因为它简单，反正电脑干活咱自己不出汗，就让它去跑呗。但如果只是依赖算力的话，程序员的价值恐怕无法完全体现，因此花了点小时间，用拟人的方法来实现一下，实测三年前主流电脑6ms内稳定解出结果，可以实用。抛砖引玉。

算法其实很简单：

1.所有格子打标记（签）（像人一样去做）

2.根据小格和行列已有数值删除标记

3.如果标记被删到只有一个，那就是唯一解，填入

4.如果所有标记都打上了，但没有解开局面，那就找标记最少的一格开始猜测（填入猜测值继续执行标签法）

5.如果猜准了，继续，没猜准（后续执行结果发现重复数值）则回溯到上一状态，继续猜格子中的下一个值，如果一个格子的值都猜完了还不对（某中间状态猜测数值暂时正确，但后续会有错误的情况），那就继续回溯到上一个格子，猜测下一个值

6.直到所有空格都被填上值，执行结束

代码中注释到位，逻辑也并不复杂，应该不难看懂，就不再详细说代码了。

下图展示了打完标签后立即需要进入猜测阶段的情况：

这种属于难度较高的情况，打完标签后没有一个有唯一值，逻辑将进入回溯猜测

下图展示了在打标签过程中已经出现了一些唯一值，并填入游戏的情况：

三图中红色部分就是在打标签的过程中已经出现的唯一解析值

这里还有一个坑留给感兴趣的朋友自行解决（不处理也没关系，但较真不是坏事）

图中红圈所示的格式明显已经指示了此格必定是5，而不需要猜测，因为这一小九宫格内其它格的标记中都没有5，所以它是此格唯一解，可以在代码中标签法无法继续的情况下和回溯法的中间增加一段判断标记中是否存在小九宫和所在行列唯一标记值的判定。（：）可能代码写很多，但实际上一次执行中并无多少这样的情况，不过，做了可以降低时间复杂度，优于由回溯法去猜）

核心代码

检测数值是否重复

//标签法检查标记的数字是否重复 function checktagnum(i,j,num){ var k,idx,ix,jx; for(k=0;k<9;k++) { //本格内的数字 ix=parseInt(i / 3) * 3 + parseInt(k / 3); jx=parseInt(j / 3) * 3 + k % 3; if (isnum(game_cracked[ix][jx]) && ix!=i && jx!=j && game_cracked[ix][jx]==num) return false; if (isobj(game_cracked[ix][jx]) && game_cracked[ix][jx].length==0) return false; //本行内的数字 if (isnum(game_cracked[i][k]) && k!=j && game_cracked[i][k]==num) return false; if (isobj(game_cracked[i][k]) && game_cracked[i][k].length==0) return false; //本列内的数字 if (isnum(game_cracked[k][j]) && k!=i && game_cracked[k][j]==num) return false; if (isobj(game_cracked[k][j]) && game_cracked[k][j].length==0) return false; } return true; }

回溯中间状态

//回溯中间状态 function readCrackedTmp(){ crackcntb++;//统计回溯次数 var tmp=clone(game_crackedtmp[game_crackedtmp.length-1]); var tagstate=tmp[0];//读取临时标签选值状态 var tagvalueidx=tagstate[0];//值索引 var tagix=tagstate[1];//临时选值所在行 var tagjx=tagstate[2];//临时选值所在列 var arrstate=tmp[1];//中间状态数组 if (tagvalueidx<arrstate[tagix][tagjx].length-1){//如果此格内还有可试探的值 //继续试探下一个值 tagvalueidx++; tagstate[0]++; game_crackedtmp[game_crackedtmp.length-1]=clone([tagstate,arrstate]);//更新最后的中间状态数据库 arrstate[tagix][tagjx]=arrstate[tagix][tagjx][tagvalueidx];//试探值写入 game_cracked=clone(arrstate);//恢复状态到正式数组 delcnt=0;//重置标记次数 deltagnum(tagix,tagjx,arrstate[tagix][tagjx]);//删除标记 cracking(1);//继续递归 }else{ //回到上一回溯状态接着试探 game_crackedtmp.splice(game_crackedtmp.length-1,1); readCrackedTmp(); } }

删除标签并解析唯一值

/ * 标签法 根据行列表本格数值不能重复的数独规则，删除本格本行本列有的值标记，如能准确解析到唯一值，则删除其它单元中的标记值 * @param i 行 * @param j 列 * @param num 如果为0表示删除本格标记，否则表示删除其它单元标记 */ function deltagnum(i,j,num=0){ var k,l,idx,ix,jx; crackcnt1++;//统计标记判断次数 //判断是否重复，重复则回溯 if (num!=0 && !checktagnum(i,j,num)){ //console.log([i,j,num,game_cracked[i][j],game_cracked]); readCrackedTmp(); return; } for(k=0;k<9;k++) { ix=parseInt(i / 3) * 3 + parseInt(k / 3);//小格定位 jx=parseInt(j / 3) * 3 + k % 3; if (num==0) {//删除本单元标记 //本格内的数字 if (isnum(game_cracked[ix][jx])) { idx = game_cracked[i][j].indexOf(game_cracked[ix][jx]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } //本行内的数字 if (isnum(game_cracked[i][k])) { idx = game_cracked[i][j].indexOf(game_cracked[i][k]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } //本列内的数字 if (isnum(game_cracked[k][j])) { idx = game_cracked[i][j].indexOf(game_cracked[k][j]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } if (game_cracked[i][j].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; var num = game_cracked[i][j][0]; game_cracked[i][j] = game_cracked[i][j][0]; deltagnum(i, j, num);//本格本行本列中有标记此值的都去掉标记 } }else{//删除其它单元标记 //本格内的数字 if (isobj(game_cracked[ix][jx])) { idx = game_cracked[ix][jx].indexOf(num); if (idx > -1) { game_cracked[ix][jx].splice(idx, 1); if (game_cracked[ix][jx].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[ix][jx] = game_cracked[ix][jx][0] ; deltagnum(ix, jx, game_cracked[ix][jx]);//本格本行本列中有标记此值的都去掉标记 } } } //本行内的数字 if (isobj(game_cracked[i][k])) { idx = game_cracked[i][k].indexOf(num); if (idx > -1) { game_cracked[i][k].splice(idx, 1); if (game_cracked[i][k].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[i][k] = game_cracked[i][k][0] ; deltagnum(i, k, game_cracked[i][k]);//本格本行本列中有标记此值的都去掉标记 } } } //本列内的数字 if (isobj(game_cracked[k][j])) { idx = game_cracked[k][j].indexOf(num); if (idx > -1) { game_cracked[k][j].splice(idx, 1); if (game_cracked[k][j].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[k][j] = game_cracked[k][j][0] ; deltagnum(k, j, game_cracked[k][j]);//本格本行本列中有标记此值的都去掉标记 } } } } } }

完整代码

shudu.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>数独</title>
    <script language="javascript" src="shudu.js"></script>
</head>
<style>
    body{
        font-size: 30px;
    }
    table{
        border:1px solid #ddd;
        border-collapse: collapse;
    }
    td{
        border:1px solid #ddd;
        border-collapse: collapse;
 
    }
    .subtable td{
        width: 50px;
        height: 50px;
        vertical-align: middle;
        text-align: center;
    }
 
</style>
<body>
<script>
    //getGame();
    startGame();
    document.write(tb);
</script>
</body>
</html>

suhdu.js

//数独 var game=[];//生成的完整游戏数组 var game_init=[];//控空后的题目 var game_cracked=[];//解析结果数组，初始化为game_init var game_crackedtmp=[];//回溯状态数组，存储回溯临时结果 var delcnt=0;//删除标记次数,用于识别一次执行中是否有有效的步骤，如果没有有效步骤，则执行猜测（进入回溯业务流程） var crackcnt1=0; var crackcnt2=0; var crackcntb=0; var tagtest=1; var tb=""; var back=0; var backcnt=0; var stime=new Date().getTime(); function getGame(){ game=[]; back=0; backcnt=0; stime=new Date().getTime(); console.log('开始时间：'+stime); createGame(); var etime=new Date().getTime(); console.log('开始时间：'+stime+',结束时间：'+etime+' 耗时：'+(etime-stime)+"毫秒"); } //生成一局游戏 function createGame(){ var i,j; for(i=0;i<9;i++){ game[i]=[0,0,0,0,0,0,0,0,0]; for(j=0;j<9;j++){ //获取可以随机的数字列表 tmpnums=getTmpnums(i,j); if (tmpnums.length==0){ //不成立，回归 back++; backcnt++; //onsole.log('不成立回归：'+i+":"+j); if (back<10){//10次内回归单个九宫格的当前行 j=j=parseInt(j/3)*3-1; }else if (back<20){//20次内回归当前整行 j=-1; }else if (back<50){//50次回归上一整行 i-=2; if (i<-1) i=-1; j=10; //back=0; }else{//大于50次回归到上两整行 i-=3; if (i<-1) i=-1; j=10; back=0; } }else { idx = parseInt(Math.random() * tmpnums.length); game[i][j] = tmpnums[idx]; } } } //console.log(game); console.log('生成一局总回归次数：'+backcnt); } function getTmpnums(ci,rj) { var i, j; var tmp = [1, 2, 3, 4, 5, 6, 7, 8, 9]; //本九宫格内有的排除 for (i = parseInt(ci / 3) * 3; i < parseInt(ci / 3) * 3 + 3; i++) { for (j = parseInt(rj / 3) * 3; j < parseInt(rj / 3) * 3 + 3; j++) { if (game.length > i && game[i][j] != 0) { tmp[game[i][j] - 1] = 0; } } } //本行内有的排除 for (j = 0; j < rj; j++) tmp[game[ci][j] - 1] = 0; //本列内有的排除 for (i = 0; i < ci; i++) tmp[game[i][rj] - 1] = 0; var rlt = []; for (i = 0; i < 9; i++) { if (tmp[i] != 0) { rlt[rlt.length] = tmp[i]; } } return rlt; } //按难度开始游戏 function startGameByLevel(level){ var levels=1; var levele=4; switch(level){ case 2: levels=2; levele=5; break; case 3: levels=3; levele=6; break; case 4: levels=4; levele=7; break; default: levels=1; levele=4; break; } //挖空 game_init=clone(game); for(var i=0;i<9;i++) { //TODO:要控制整体难度不因完全随机而过于简单或过于复杂，可以在这里根据每次生成的空格数多少来人为增减剩余空位数 //这里采用的是每个小格挖空，也可改为每行挖空或每列挖空 var num=Math.floor(Math.random()*(levele-levels+1))+levels; var kgbox=[0,1,2,3,4,5,6,7,8]; //console.log('第'+(i+1)+'格挖空'+num+'个'); for(var j=0;j<num;j++) { var idx=Math.floor(Math.random()*kgbox.length); var cell=kgbox[idx]; game_init[parseInt(i/3)*3+ parseInt( cell/3)][i %3*3+ cell % 3]='N'; kgbox.splice(idx,1); } } } //解开游戏 标记法+回溯法 function crackGame(){ game_cracked=clone(game_init); cracking(); } //是否数字 判断格子是否已经解析到唯一值 function isnum(num){ return typeof num=='number'; } //是否对象 判断格子是否在标签状态 function isobj(obj){ return typeof obj=='object'; } //深度复制对象 function clone(obj){ return JSON.parse(JSON.stringify(obj)); } //标签法检查标记的数字是否重复 function checktagnum(i,j,num){ var k,idx,ix,jx; for(k=0;k<9;k++) { //本格内的数字 ix=parseInt(i / 3) * 3 + parseInt(k / 3); jx=parseInt(j / 3) * 3 + k % 3; if (isnum(game_cracked[ix][jx]) && ix!=i && jx!=j && game_cracked[ix][jx]==num) return false; if (isobj(game_cracked[ix][jx]) && game_cracked[ix][jx].length==0) return false; //本行内的数字 if (isnum(game_cracked[i][k]) && k!=j && game_cracked[i][k]==num) return false; if (isobj(game_cracked[i][k]) && game_cracked[i][k].length==0) return false; //本列内的数字 if (isnum(game_cracked[k][j]) && k!=i && game_cracked[k][j]==num) return false; if (isobj(game_cracked[k][j]) && game_cracked[k][j].length==0) return false; } return true; } / * 标签法 根据行列表本格数值不能重复的数独规则，删除本格本行本列有的值标记，如能准确解析到唯一值，则删除其它单元中的标记值 * @param i 行 * @param j 列 * @param num 如果为0表示删除本格标记，否则表示删除其它单元标记 */ function deltagnum(i,j,num=0){ var k,l,idx,ix,jx; crackcnt1++;//统计标记判断次数 //判断是否重复，重复则回溯 if (num!=0 && !checktagnum(i,j,num)){ //console.log([i,j,num,game_cracked[i][j],game_cracked]); readCrackedTmp(); return; } for(k=0;k<9;k++) { ix=parseInt(i / 3) * 3 + parseInt(k / 3);//小格定位 jx=parseInt(j / 3) * 3 + k % 3; if (num==0) {//删除本单元标记 //本格内的数字 if (isnum(game_cracked[ix][jx])) { idx = game_cracked[i][j].indexOf(game_cracked[ix][jx]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } //本行内的数字 if (isnum(game_cracked[i][k])) { idx = game_cracked[i][j].indexOf(game_cracked[i][k]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } //本列内的数字 if (isnum(game_cracked[k][j])) { idx = game_cracked[i][j].indexOf(game_cracked[k][j]); if (idx > -1) game_cracked[i][j].splice(idx, 1); } if (game_cracked[i][j].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; var num = game_cracked[i][j][0]; game_cracked[i][j] = game_cracked[i][j][0]; deltagnum(i, j, num);//本格本行本列中有标记此值的都去掉标记 } }else{//删除其它单元标记 //本格内的数字 if (isobj(game_cracked[ix][jx])) { idx = game_cracked[ix][jx].indexOf(num); if (idx > -1) { game_cracked[ix][jx].splice(idx, 1); if (game_cracked[ix][jx].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[ix][jx] = game_cracked[ix][jx][0] ; deltagnum(ix, jx, game_cracked[ix][jx]);//本格本行本列中有标记此值的都去掉标记 } } } //本行内的数字 if (isobj(game_cracked[i][k])) { idx = game_cracked[i][k].indexOf(num); if (idx > -1) { game_cracked[i][k].splice(idx, 1); if (game_cracked[i][k].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[i][k] = game_cracked[i][k][0] ; deltagnum(i, k, game_cracked[i][k]);//本格本行本列中有标记此值的都去掉标记 } } } //本列内的数字 if (isobj(game_cracked[k][j])) { idx = game_cracked[k][j].indexOf(num); if (idx > -1) { game_cracked[k][j].splice(idx, 1); if (game_cracked[k][j].length == 1) {//如果本格只剩一个标签，表示解析到唯一值，赋值后继续递归 delcnt++; game_cracked[k][j] = game_cracked[k][j][0] ; deltagnum(k, j, game_cracked[k][j]);//本格本行本列中有标记此值的都去掉标记 } } } } } } //回溯中间状态 function readCrackedTmp(){ crackcntb++;//统计回溯次数 var tmp=clone(game_crackedtmp[game_crackedtmp.length-1]); var tagstate=tmp[0];//读取临时标签选值状态 var tagvalueidx=tagstate[0];//值索引 var tagix=tagstate[1];//临时选值所在行 var tagjx=tagstate[2];//临时选值所在列 var arrstate=tmp[1];//中间状态数组 if (tagvalueidx<arrstate[tagix][tagjx].length-1){//如果此格内还有可试探的值 //继续试探下一个值 tagvalueidx++; tagstate[0]++; game_crackedtmp[game_crackedtmp.length-1]=clone([tagstate,arrstate]);//更新最后的中间状态数据库 arrstate[tagix][tagjx]=arrstate[tagix][tagjx][tagvalueidx];//试探值写入 game_cracked=clone(arrstate);//恢复状态到正式数组 delcnt=0;//重置标记次数 deltagnum(tagix,tagjx,arrstate[tagix][tagjx]);//删除标记 cracking(1);//继续递归 }else{ //回到上一回溯状态接着试探 game_crackedtmp.splice(game_crackedtmp.length-1,1); readCrackedTmp(); } } //递归解游戏 //type=1 标签法 type=2 回溯法 function cracking(type=1){ //console.log(game_cracked); //判断是否完成或者失败 var i,j,cnt=0; for(i=0;i<9;i++) { for (j = 0; j < 9; j++) { if (!isnum(game_cracked[i][j])) { /*if (game_cracked[i][j].length==0){ cnt=-1; break; }*/ cnt++; break; } } if (cnt>0) { break; } } if (cnt==0 ) {//成功 return; } cnt=0; if (type==1){ delcnt=0; for(i=0;i<9;i++) { for (j = 0; j < 9; j++) { if (!isnum(game_cracked[i][j])) { if (game_cracked[i][j] == 'N') { game_cracked[i][j] = [1, 2, 3, 4, 5, 6, 7, 8, 9];//初始化标签 } if (isobj(game_cracked[i][j])) { deltagnum(i, j);//删除标签 } } } } //console.log(delcnt); //console.log(game_cracked); //return; if (tagtest==1) return;//测试标签法第一次结果 if (delcnt==0) { cracking(2); }else{ cracking(1); } }else{ crackcnt2++;//统计中间状态保存次数 //回溯法 最少标签数的格式中的标签选定一个值（初始选择第一个） var idxi,idxj,taglen=10; for(i=0;i<9;i++) { for (j = 0; j < 9; j++) { if (isobj(game_cracked[i][j])) { if(game_cracked[i][j].length<taglen){ taglen=game_cracked[i][j].length; idxi=i; idxj=j; } } } } game_crackedtmp.push([ [0,idxi,idxj],//当前选择的标签 clone(game_cracked)//保存当前状态 ]); //console.log('保存状态：'+[idxi,idxj,0,'|',game_cracked[idxi][idxj]]); game_cracked[idxi][idxj]=game_cracked[idxi][idxj][0]; deltagnum(idxi,idxj,game_cracked[idxi][idxj]); cracking(1); } } //输出表格 function startGame(){ var i,j; getGame(); startGameByLevel(4); stime=new Date().getTime(); crackGame(); var crackedtest=clone(game_cracked); tagtest=0; console.log('解答开始时间：'+stime); crackGame(); var etime=new Date().getTime(); console.log('解答开始时间：'+stime+',解答结束时间：'+etime+' 耗时：'+(etime-stime)+"毫秒 "+"标签定位次数："+crackcnt1+" 中间状态保存次数："+crackcnt2+" 状态回溯次数："+crackcntb); for(i=0;i<9;i++){ if (i==0) tb+="<table>"; if (i % 3==0) tb+="<tr><td>"; for(j=0;j<9;j++){ if (j==0) tb+="<table class='subtable'>"; if (j%3==0) tb+="<tr><td>"; tb+=game[parseInt(i/3)*3+parseInt(j/3)][i%3*3+j%3]; if (j%3==2) tb+="</td></tr>"; else tb+="</td><td>"; if (j==8) tb+="</table>"; } if (i%3==2) tb+="</td></tr>"; else tb+="</td><td>" if (i==8) tb+="</table>"; } var tbi=''; for(i=0;i<9;i++){ if (i==0) tbi+="<table>"; if (i % 3==0) tbi+="<tr><td>"; for(j=0;j<9;j++){ if (j==0) tbi+="<table class='subtable'>"; if (j%3==0) tbi+="<tr><td>"; tbi+=game_init[parseInt(i/3)*3+parseInt(j/3)][i%3*3+j%3]=='N'?'':game_cracked[parseInt(i/3)*3+parseInt(j/3)][i%3*3+j%3]; if (j%3==2) tbi+="</td></tr>"; else tbi+="</td><td>"; if (j==8) tbi+="</table>"; } if (i%3==2) tbi+="</td></tr>"; else tbi+="</td><td>" if (i==8) tbi+="</table>"; } var tbc=''; for(i=0;i<9;i++){ if (i==0) tbc+="<table>"; if (i % 3==0) tbc+="<tr><td>"; for(j=0;j<9;j++){ if (j==0) tbc+="<table class='subtable'>"; if (j%3==0) tbc+="<tr><td>"; if (game_init[parseInt(i/3)*3+parseInt(j/3)][i%3*3+j%3]=='N'){ if(isobj(crackedtest[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3])){ tbc += '<span style="color:#;font-size: 30%;">'+crackedtest[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3]+'</span>'; }else { tbc += '<span style="color:red;">' + crackedtest[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3] + '</span>'; } }else { tbc += crackedtest[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3]; } if (j%3==2) tbc+="</td></tr>"; else tbc+="</td><td>"; if (j==8) tbc+="</table>"; } if (i%3==2) tbc+="</td></tr>"; else tbc+="</td><td>" if (i==8) tbc+="</table>"; } var tbd=''; for(i=0;i<9;i++){ if (i==0) tbd+="<table>"; if (i % 3==0) tbd+="<tr><td>"; for(j=0;j<9;j++){ if (j==0) tbd+="<table class='subtable'>"; if (j%3==0) tbd+="<tr><td>"; if (game_init[parseInt(i/3)*3+parseInt(j/3)][i%3*3+j%3]=='N'){ if(isobj(game_cracked[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3])){ tbd += '<span style="color:#;font-size: 70%;">'+game_cracked[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3]+'</span>'; }else { tbd += '<span style="color:red;">' + game_cracked[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3] + '</span>'; } }else { tbd += game_cracked[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3]; } if (j%3==2) tbd+="</td></tr>"; else tbd+="</td><td>"; if (j==8) tbd+="</table>"; } if (i%3==2) tbd+="</td></tr>"; else tbd+="</td><td>" if (i==8) tbd+="</table>"; } tb="<div><div style='float: left; margin-right: 30px;'>"+tb+"</div><div style='float: left;margin-right: 30px;'>"+tbi+"</div><div style='float: left;margin-right: 30px;'>"+tbc+"</div><div style='float: left;'>"+tbd+"</div></div>" }

关于难度的附言

哈哈，这又是一个坑！

这里的难度只是随机挖空，难度越高挖的空越多，因此实际上并不能严格保证难度匹配，有些情况下挖的空很多，但实际上难度却非常的小，从程序执行输出的中间状态保存次数和回溯次数可以看出，中间过程越多，难度越大，反之则越小。

因此，较真的朋友可以想想看如何处理挖空才能保证4级难度真的是4级！

提示：让被挖的空或是留下的数值重复的尽量多！

OVER