首页 > web前端 > js教程 > 正文

javascript实现数独解法_javascript技巧

WBOY
发布: 2016-05-16 16:09:39
原创
1304 人浏览过

生生把写过的java版改成javascript版,第一次写,很不专业,见谅。唉,我是有多闲。

复制代码 代码如下:

var 数独 = {
    初始化:函数(str){
        this.blank = [];
        this.fixed = [];
        this.cell = [];
        this.Trials=[];
        for (i = 0; i             var chr = str.charCodeAt(i);
            if (chr == 48) {
                this.cell[i] = 511;
                this.blank.push(i);
            } 其他 {
                this.cell[i] = 1                 this.fixed.push(i);
            }
        }
    },
    显示板:函数 () {
        var board = "";
        for (var i = 0; i             if (i % 9 == 0) {
                board = board.concat("n");
            }
            board = board.concat("[");
            for (var j = 0; j                 if ((this.cell[i] >> j & 1) == 1) {
                    board = board.concat(String.fromCharCode(j 49));
                }
            }
            board = board.concat("]");
        }
        返回板;
    },
    检查:函数 () {
        var 检查点 = [0, 12, 24, 28, 40, 52, 56, 68, 80];
        for (检查点中的 var i) {
            var r, b, c;
            r = b = c = this.cell[检查点[i]];
            for (j = 0; j                 c ^= this.cell[this.getX(checkpoint[i])[j]];
                b ^= this.cell[this.getX(checkpoint[i])[8 j]];
                r ^= this.cell[this.getX(checkpoint[i])[16 j]];
            }
            if ((r & b & c) != 0x1FF) {
                返回错误;
            }
        }
        返回真;
    },
    位计数:函数 (i) {
        var n = 0;
        for (var j = 0; j             if ((i >> j & 1) == 1)
                n ;
        }
        返回 n;
    },
    numberOfTrailingZeros: 函数(i){
        var n = 0;
        for (var j = 0; j             if ((i >> j & 1) ==0)
                n ;
            其他{
                休息;
            }
        }
        返回n;       
    },
    updateCandidates: function () {
        for (var i in this.fixed) {
            var opt = 0x1FF ^ this.cell[this.fixed[i]];
            for (var j = 0; j                 this.cell[this.getX(this.fixed[i])[j]] &= opt;
                //!注意
                if (this.cell[this.getX(this.fixed[i])[j]] == 0) {
                    //console.log("Error-0候选:" x[this.fixed[i]][j]);
                    返回错误;
                }
            }
        }
        返回真;
    },
    eekUniqueCandidate: 函数 () {
        for (var bidx in this.blank) {
            var 行 = 0,列 = 0,框 = 0;
            for (i = 0; i                 row |= this.cell[this.getX(this.blank[bidx])[i]];
                框 |= this.cell[this.getX(this.blank[bidx])[8 i]];
                col |= this.cell[this.getX(this.blank[bidx])[16 i]];
            }
            if (this.bitCount(this.cell[this.blank[bidx]] & ~row) == 1) {
                this.cell[this.blank[bidx]] &= ~row;
                继续;
            }
            if (this.bitCount(this.cell[this.blank[bidx]] & ~col) == 1) {
                this.cell[this.blank[bidx]] &= ~col;
                继续;
            }
            if (this.bitCount(this.cell[this.blank[bidx]] & ~box) == 1) {
                this.cell[this.blank[bidx]] &= ~box;
            }
        }
    },
    eekFilledable: 函数 () {
        this.fixed = [];
  var _del=[];
        for (var i in this.blank) {
            if (this.bitCount(this.cell[this.blank[i]]) == 1) {
                this.fixed.push(this.blank[i]);
                //console.log("已修复:" this.blank[i] "=>" this.cell[this.blank[i]]);
                //this.blank.splice(i, 1);//在循环中删除它会导致bug
    _del.push(i);
            }
        }
  while(_del.length>0){
   this.blank.splice(_del.pop(), 1);
  }
    },
    eekMutexCell: 函数 () {
        var 二 = [];
        for (var n in this.blank) {
            if (this.bitCount(this.cell[this.blank[n]]) == 2) {
                Two.push(this.blank[n]);
            }
        }
        for (var i = 0; i             for (var j = i 1; j                 if (this.cell[two[i]] == this.cell[two[j]]) {
                    var opt = ~this.cell[two[i]];
                    if (parseInt(two[i] / 9) ==parseInt(two[j] / 9)) {
                        对于 (n = 0; n                             this.cell[this.getX(two[i])[n]] &= opt;
                        }
                    }
                    if ((二[i] - 二[j]) % 9 == 0) {                       
                        对于 (n = 8; n                             this.cell[this.getX(two[i])[n]] &= opt;
                        }
                    }
                    if ((parseInt(two[i] / 27) * 3 parseInt(two[i] % 9 / 3)) == (parseInt(two[j] / 27) * 3 parseInt(two[j] % 9 / 3) ))){
                        对于 (n = 16; n                             this.cell[this.getX(two[i])[n]] &= opt;
                        }
                    }
                    this.cell[two[j]] = ~opt;
                }
            }
        }
    },
    basicSolve: 函数 () {
        做{
            if (!this.updateCandidates(this.fixed)) {
                this.backForward();
            }
            this.seekUniqueCandidate();
            this.seekMutexCell();
            this.seekFilledable();
        } while (this.fixed.length != 0);
        return this.blank.length == 0;
    },   
    setTrialCell: function() {
        for (var i in this.blank) {
            if (this.bitCount(this.cell[this.blank[i]]) == 2) {
                var 试验值 = 1                 var waitingValue = this.cell[this.blank[i]] ^ TrialValue;
                //console.log("try:[" this.blank[i] "]->" (this.numberOfTrailingZeros(TrialValue) 1) "#" (this.numberOfTrailingZeros(waitingValue) 1));
                this.cell[this.blank[i]] = TrialValue;               
                this.trys.push(this.createTrialPoint(this.blank[i], waitingValue, this.cell));
                返回真;
            }
        }
        返回错误;
    },
    向后:函数(){
        if (this.Trials.length==0) {
            console.log("也许没有解决办法!");
            返回;
        }
        var back = this.Trials.pop();
        this.reset(back.data);
        this.cell[back.idx] = back.val;
        this.fixed.push(back.idx);
        //console.log("back:[" back.idx "]->" (this.numberOfTrailingZeros(back.val) 1));
    },
    重置:函数(数据){
        this.blank=[];
        this.fixed=[];
        this.cell=data.concat();
        for (var i = 0; i             if (this.bitCount(this.cell[i]) != 1) {
                this.blank.push(i);
            } 其他 {
                this.fixed.push(i);
            }
        }
    },
    TrialSolve: 函数() {
        while (this.blank.length!=0) {
            if (this.setTrialCell()) {
                this.basicSolve();
            } 其他 {
                if (this.Trials.length==0) {
                    //console.log("无法后退!可能没有解决办法!");
                    休息;
                } 其他 {
                    this.backForward();
                    this.basicSolve();
                }
            }
        }
    },
    播放:函数(){
        console.log(this.showBoard());
        var start = new Date().getMilliseconds();
        if (!this.basicSolve()) {
            this.TrialSolve();
        }
        var end = new Date().getMilliseconds();
        console.log(this.showBoard());
        if (this.check()) {
            console.log("[" (end - start) "ms OK!]");
        } 其他 {
            console.log("[" (end - start) "ms,无法解决?");
        }
  //返回this.showBoard();
    },
    getX:函数(idx){
        var Neighbors=new Array(24);
        var box=new Array(0,1,2,9,10,11,18,19,20);
        var r=parseInt(idx/9);
  var c=idx%9;
  var xs=parseInt(idx/27)*27 parseInt(idx%9/3)*3;
        var i=0;
        for(var n=0;n             if(n==c)继续;
            邻居[i]=r*9 n;
        }
        for(var n=0;n             if(n==r)继续;
            邻居[i]=c n*9;
        }
        for(var n=0;n             var t=xs box[n];
            if(t==idx)继续;
            邻居[i]=t;
        }
          返回邻居;
    },
 createTrialPoint:function(idx, val, board) {
        var tp = {};
        tp.idx = idx;
        tp.val = val;
        tp.data = board.concat();
        返回 tp;
 }
};
//数独.init("000000500000008300600100000080093000000000020700000000058000000000200017090000060");
//数独.init("530070000600195000098000060800060003400803001700020006060000280000419005000080079");
数独.init("800000000003600000070090200050007000000045700000100030001000068008500010090000400");
数独.play();

以上就是关于使用javascript实现数独解法的全部代码了,希望大家能够喜欢。

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板