前几天突然想写一个数独游戏。本来以为没什么难度。结果实现起来还是花了一点功夫。要做数据游戏,并不是随意地在九宫格里放一些数字让玩家来填写。一是你得保证你放的数字符合数独的规则。二是你得保证你的数独是有解的。

所以在开始一局数独游戏之前,你要生成一个完整的数独,然后从中扣掉一些数字。让用户来填写。

数独规则:

数独(すうどく,Sūdoku),是源自18世纪瑞士发明,流传到美国,再由日本发扬光大的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。 数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。

本文介绍生成数独的算法。

先来一个九宫格的图,方便看着它思考。

一共九九八十一个格子,算法主要思路。为每一个格子填上一个符合数独条件的值。

数组以左上角为圆点,横为x轴,竖为y轴 在数组中对应的下标为:

11 21 31 41 51 61 71 81 91 12 22 32 42 52 62 72 82 92 13 23 33 43 53 63 73 83 93 14 24 34 44 54 64 74 84 94 15 25 35 45 55 65 75 85 95 16 26 36 46 56 66 76 86 96 17 27 37 47 57 67 77 87 97 18 28 38 48 58 68 78 88 98 19 29 39 49 59 69 79 89 99

随机生成一个值填入数组。

随机生成下一个值。判断不在数组中其所在横、竖、三宫格对应的下标里。获取横、竖、三宫的的下标使用过的值,算其可用的数字。随机取可用数字中的一个。如果没有可用数字,本次循环失败,回到开始重新算。

循环生成下一个值

……

直到81个下标位置都有符合条件的值。数独数组就生成完毕了!

然后我做了一点优化:

其实对于最开始的一些值,可以不用判断那么多,只需要把1-9乱序,依次放入九个格子中去。 我的做法是先在对角线上的三宫乱序依次放入1-9。就可以只用很少的计算量得出来27个值。因为对角线上填的值,不会互相影响。没有横竖的影响。

生成了这27个值之后,再使用上面的算法来计算,计算量少了不少,计算效率和成功率就大了很多了。

随机测试了几次,看我console出来的结果:

数独生成完毕,耗时:0.972秒!

数独生成完毕,耗时:0.081秒!

数独生成完毕,耗时:1.305秒!

数独生成完毕,耗时:0.102秒!

数独生成完毕,耗时:0.065秒!

数独生成完毕,耗时:0.813秒!

……

还是不算慢吧。

核心代码,从完整的里面扣出来的:

createSdArr:function(){
    //生成数独数组。
    var that = this;
    try{
        this.sdArr = [];
        this.setThird(2,2);
        this.setThird(5,5);
        this.setThird(8,8);
        var allNum = [1,2,3,4,5,6,7,8,9];
        outerfor:
        for(var i=1;i<=9;i++){
            innerfor:
            for(var j=1;j<=9;j++){
                if(this.sdArr[parseInt(i+''+j)]){
                    continue innerfor;
                }
                var XArr = this.getXArr(j,this.sdArr);
                var YArr = this.getYArr(i,this.sdArr);
                var thArr = this.getThArr(i,j,this.sdArr);
                var arr = getConnect(getConnect(XArr,YArr),thArr);
                var ableArr = arrMinus(allNum,arr);

                if(ableArr.length == 0){
                    this.createSdArr();
                    return;
                    break outerfor;
                }

                var item;
                //如果生成的重复了就重新生成。
                do{
                    item = ableArr[getRandom(ableArr.length)-1];
                }while(($.inArray(item, arr)>-1));

                this.sdArr[parseInt(i+''+j)] = item;
            }
        }
        this.backupSdArr = this.sdArr.slice();
    }catch(e){
        //如果因为超出浏览器的栈限制出错,就重新运行。
        that.createSdArr();
    }
},
getXArr:function(j,sdArr){
    //获取所在行的值。
    var arr = [];
    for(var a =1;a<=9;a++){
        if(this.sdArr[parseInt(a+""+j)]){
            arr.push(sdArr[parseInt(a+""+j)])
        }
    }
    return arr;
},
getYArr:function(i,sdArr){
    //获取所在列的值。
    var arr = [];
    for(var a =1;a<=9;a++){
        if(sdArr[parseInt(i+''+a)]){
            arr.push(sdArr[parseInt(i+''+a)])
        }
    }
    return arr;
},
getThArr:function(i,j,sdArr){
    //获取所在三宫格的值。
    var arr = [];
    var cenNum = this.getTh(i,j);
    var thIndexArr = [cenNum-11,cenNum-1,cenNum+9,cenNum-10,cenNum,cenNum+10,cenNum-9,cenNum+1,cenNum+11];
    for(var a =0;a<9;a++){
        if(sdArr[thIndexArr[a]]){
            arr.push(sdArr[thIndexArr[a]]);
        }
    }
    return arr;
},
getTh:function(i,j){
    //获取所在三宫格的中间位坐标。
    var cenArr = [22,52,82,25,55,85,28,58,88];
    var index = (Math.ceil(j/3)-1) * 3 +Math.ceil(i/3) -1;
    var cenNum = cenArr[index];
    return cenNum;
},
setThird:function(i,j){
    //为对角线上的三个三宫格随机生成。
    var numArr = [1,2,3,4,5,6,7,8,9];
    var sortedNumArr= numArr.sort(function(){return Math.random()-0.5>0?-1:1});
    var cenNum = parseInt(i+''+j);
    var thIndexArr = [cenNum-11,cenNum-1,cenNum+9,cenNum-10,cenNum,cenNum+10,cenNum-9,cenNum+1,cenNum+11];
    for(var a=0;a<9;a++){
        this.sdArr[thIndexArr[a]] = sortedNumArr[a];
    }
}

生成的完整数独是这样:

这篇就介绍这么多。欢迎留言交流。

也可以自己去试玩下这个数独:

http://runningls.com/demos/2016/soduku/

看完整代码可以到我的github。

https://github.com/liusaint/games/tree/master/soduku

生成数独数组之后,后续工作是从中扣除一定数量的值,然后让用户填写。

然后检测用户输入是不是符合数独规则。(并不是直接和我们生成的数组对比,考虑到可能有不同的解法。)

另外解数独跟生成数独的方法也是差不多的。