Rumah  >  Artikel  >  hujung hadapan web  >  Javascript melaksanakan kemahiran Sudoku solution_javascript

Javascript melaksanakan kemahiran Sudoku solution_javascript

WBOY
WBOYasal
2016-05-16 16:09:391302semak imbas

Shengsheng menukar versi java yang saya tulis kepada versi javascript Ini adalah kali pertama saya menulis, ia sangat tidak profesional, maaf untuk itu. Oh, betapa bebasnya saya.

Salin kod Kod adalah seperti berikut:

var Sudoku = {
    init: fungsi (str) {
        this.blank = [];
        this.fixed = [];
        this.cell = [];
        this.trials=[];
        untuk (i = 0; i < 81; i ) {
            var chr = str.charCodeAt(i);
            jika (chr == 48) {
                this.cell[i] = 511;
                this.blank.push(i);
            } lain {
                ini.sel[i] = 1 << chr - 49;
                this.fixed.push(i);
            }
        }
    },
    papan pameran: fungsi () {
        var board = "";
        untuk (var i = 0; i < 81; i ) {
            jika (i % 9 == 0) {
                papan = papan.concat("n");
            }
            papan = papan.concat("[");
            untuk (var j = 0; j < 9; j ) {
                jika ((this.cell[i] >> j & 1) == 1) {
                    papan = board.concat(String.fromCharCode(j 49));
                }
            }
            papan = papan.concat("]");
        }
        papan pulangan;
    },
    semak: fungsi () {
        var checkpoint = [0, 12, 24, 28, 40, 52, 56, 68, 80];
        untuk (var i di pusat pemeriksaan) {
            var r, b, c;
            r = b = c = this.cell[checkpoint[i]];
            untuk (j = 0; j < 8; 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]];
            }
            jika ((r & b & c) != 0x1FF) {
                pulangkan palsu;
            }
        }
        kembali benar;
    },
    bitCount: fungsi (i) {
        var n = 0;
        untuk (var j = 0; j < 9; j ) {
            jika ((i >> j & 1) == 1)
                n ;
        }
        pulangkan n;
    },
    numberOfTrailingZeros: fungsi(i){
        var n = 0;
        untuk (var j = 0; j < 9; j ) {
            jika ((i >> j & 1) ==0)
                n ;
            lain{
                rehat;
            }
        }
        kembali n;       
    },
    kemas kiniCalon: fungsi () {
        untuk (var i dalam ini.tetap) {
            var opt = 0x1FF ^ this.cell[this.fixed[i]];
            untuk (var j = 0; j < 24; j ) {
                this.cell[this.getX(this.fixed[i])[j]] &= opt;
                //!perasan
                if (this.cell[this.getX(this.fixed[i])[j]] == 0) {
                    //console.log("Ralat-0 calon:" x[this.fixed[i]][j]);
                    pulangkan palsu;
                }
            }
        }
        kembali benar;
    },
    seekUniqueCandidate: fungsi () {
        untuk (var bidx dalam this.blank) {
            baris var = 0, kol = 0, kotak = 0;
            untuk (i = 0; i < 8; i ) {
                baris |= this.cell[this.getX(this.blank[bidx])[i]];
                kotak |= 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;
                teruskan;
            }
            if (this.bitCount(this.cell[this.blank[bidx]] & ~col) == 1) {
                this.cell[this.blank[bidx]] &= ~col;
                teruskan;
            }
            if (this.bitCount(this.cell[this.blank[bidx]] & ~box) == 1) {
                this.cell[this.blank[bidx]] &= ~box;
            }
        }
    },
    seekFilledable: fungsi () {
        this.fixed = [];
  var _del=[];
        untuk (var i dalam ini.kosong) {
            if (this.bitCount(this.cell[this.blank[i]]) == 1) {
                this.fixed.push(this.blank[i]);
                //console.log("fixed:" this.blank[i] "=>" this.cell[this.blank[i]]);
                //this.blank.splice(i, 1);//untuk memadamkannya dalam gelung akan menyebabkan pepijat
    _del.push(i);
            }
        }
  while(_del.length>0){
   this.blank.splice(_del.pop(), 1);
  }
    },
    seekMutexCell: fungsi () {
        var dua = [];
        untuk (var n dalam ini.kosong) {
            if (this.bitCount(this.cell[this.blank[n]]) == 2) {
                dua.tolak(ini.kosong[n]);
            }
        }
        untuk (var i = 0; i < dua.panjang; i ) {
            untuk (var j = i 1; j < dua.panjang; j ) {
                jika (this.cell[dua[i]] == this.cell[dua[j]]) {
                    var opt = ~this.cell[dua[i]];
                    if (parseInt(dua[i] / 9) ==parseInt(dua[j] / 9)) {
                        untuk (n = 0; n < 8; n ) {
                            this.cell[this.getX(dua[i])[n]] &= opt;
                        }
                    }
                    jika ((dua[i] - dua[j]) % 9 == 0) {                       
                        untuk (n = 8; n < 16; n ) {
                            this.cell[this.getX(dua[i])[n]] &= opt;
                        }
                    }
                    jika ((parseInt(dua[i] / 27) * 3 parseInt(dua[i] % 9 / 3)) == (parseInt(dua[j] / 27) * 3 parseInt(dua[j] % 9 / 3 ))) {
                        untuk (n = 16; n < 24; n ) {
                            this.cell[this.getX(dua[i])[n]] &= opt;
                        }
                    }
                    this.cell[two[j]] = ~opt;
                }
            }
        }
    },
    basicSelesai: fungsi () {
        lakukan {
            jika (!ini.kemaskiniCalon(ini.tetap)) {
                this.backForward();
            }
            this.seekUniqueCandidate();
            this.seekMutexCell();
            this.seekFilledable();
        } manakala (this.fixed.length != 0);
        kembalikan this.blank.length == 0;
    },   
    setTrialCell: function() {
        untuk (var i dalam ini.kosong) {
            if (this.bitCount(this.cell[this.blank[i]]) == 2) {
                var trialValue = 1 << this.numberOfTrailingZeros(this.cell[this.blank[i]]);
                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.trials.push(this.createTrialPoint(this.blank[i], waitingValue, this.cell));
                kembali benar;
            }
        }
        pulangkan palsu;
    },
    backForward: function() {
        jika (ini.percubaan.panjang==0) {
            console.log("Mungkin tiada penyelesaian!");
            kembali;
        }
        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));
    },
    set semula: fungsi(data) {
        this.blank=[];
        this.fixed=[];
        this.cell=data.concat();
        untuk (var i = 0; i < 81; i ) {
            jika (this.bitCount(this.cell[i]) != 1) {
                this.blank.push(i);
            } lain {
                this.fixed.push(i);
            }
        }
    },
    trialSolve: function() {
        manakala (ini.kosong.panjang!=0) {
            jika (this.setTrialCell()) {
                this.basicSolve();
            } lain {
                jika (ini.percubaan.panjang==0) {
                    //console.log("Tidak boleh ke belakang! Mungkin tiada penyelesaian!");
                    rehat;
                } lain {
                    this.backForward();
                    this.basicSolve();
                }
            }
        }
    },
    mainkan: function() {
        console.log(this.showBoard());
        var start = new Date().getMilliseconds();
        jika (!this.basicSolve()) {
            this.trialSolve();
        }
        var end = new Date().getMilliseconds();
        console.log(this.showBoard());
        jika (this.check()) {
            console.log("[" (akhir - mula) "ms OK!]");
        } lain {
            console.log("[" (akhir - mula) "ms, tidak dapat menyelesaikannya?");
        }
  //kembali this.showBoard();
    },
    getX:function(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;
        untuk(var n=0;n<9;n ){
            jika(n==c)teruskan;
            jiran[i ]=r*9 n;
        }
        untuk(var n=0;n<9;n ){
            jika(n==r)teruskan;
            jiran[i ]=c n*9;
        }
        untuk(var n=0;n<9;n ){
            var t=kotak xs[n];
            jika(t==idx)teruskan;
            jiran[i ]=t;
        }
          pulangkan jiran;
    },
 createTrialPoint:function(idx, val, board) {
        var tp = {};
        tp.idx = idx;
        tp.val = val;
        tp.data = board.concat();
        balik tp;
 }
};
//Sudoku.init("000000500000008300600100000080093000000000020700000000058000000000200017090000060");
//Sudoku.init("530070000600195000098000060800060003400803001700020006060000280000419005000080079");
Sudoku.init("80000000003600000070090200050007000000045700000100030001000068008500010090000400");
Sudoku.play();

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

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn