Maison  >  Article  >  interface Web  >  Javascript implémente les compétences Sudoku solution_javascript

Javascript implémente les compétences Sudoku solution_javascript

WBOY
WBOYoriginal
2016-05-16 16:09:391286parcourir

Shengsheng a changé la version java que j'ai écrite en version javascript. C'est la première fois que j'écris, ce n'est pas très professionnel, désolé pour ça. Oh, comme je suis libre.

Copier le code Le code est le suivant :

var Sudoku = {
    init : fonction (str) {
        this.blank = [];
        this.fixed = [];
        this.cell = [];
        this.trials=[];
        pour (i = 0; i < 81; i ) {
            var chr = str.charCodeAt(i);
            si (chr == 48) {
                this.cell[i] = 511;
                this.blank.push(i);
            } autre {
                this.cell[i] = 1 << chr-49;
                this.fixed.push(i);
            >
        >
    },
    showBoard : fonction () {
        var tableau = "";
        pour (var je = 0; je < 81; je ) {
            si (je % 9 == 0) {
                board = board.concat("n");
            >
            board = board.concat("[");
            pour (var j = 0; j < 9; j ) {
                if ((this.cell[i] >> j & 1) == 1) {
                    board = board.concat(String.fromCharCode(j 49));
                >
            >
            board = board.concat("]");
        >
        tableau de retour ;
    },
    vérifier : fonction () {
        var point de contrôle = [0, 12, 24, 28, 40, 52, 56, 68, 80];
        pour (var i au point de contrôle) {
            var r, b, c;
            r = b = c = this.cell[checkpoint[i]];
            pour (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]];
            >
            si ((r & b & c) != 0x1FF) {
                retourner faux ;
            >
        >
        renvoie vrai ;
    },
    bitCount : fonction (i) {
        var n = 0;
        pour (var j = 0; j < 9; j ) {
            si ((i >> j & 1) == 1)
                n ;
        >
        retourner n;
    },
    numberOfTrailingZeros : fonction(i){
        var n = 0;
        pour (var j = 0; j < 9; j ) {
            si ((i >> j & 1) ==0)
                n ;
            autre{
                pause;
            >
        >
        retourner n ;       
    },
    updateCandidates : function () {
        pour (var i dans this.fixed) {
            var opt = 0x1FF ^ this.cell[this.fixed[i]];
            pour (var j = 0; j < 24; j ) {
                this.cell[this.getX(this.fixed[i])[j]] &= opt;
                //!avis
                if (this.cell[this.getX(this.fixed[i])[j]] == 0) {
                    //console.log("Erreur-0 candidat :" x[this.fixed[i]][j]);
                    retourner faux ;
                >
            >
        >
        renvoie vrai ;
    },
    seekUniqueCandidate : fonction () {
        pour (var bidx dans this.blank) {
            var ligne = 0, col = 0, boîte = 0;
            pour (i = 0; i < 8; i ) {
                rangée |= this.cell[this.getX(this.blank[bidx])[i]];
                box |= 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;
                continuer ;
            >
            if (this.bitCount(this.cell[this.blank[bidx]] & ~col) == 1) {
                this.cell[this.blank[bidx]] &= ~col;
                continuer ;
            >
            if (this.bitCount(this.cell[this.blank[bidx]] & ~box) == 1) {
                this.cell[this.blank[bidx]] &= ~box;
            >
        >
    },
    seekFilledable : fonction () {
        this.fixed = [];
  var _del=[];
        pour (var i dans this.blank) {
            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);//le supprimer dans la boucle provoquerait un bug
    _del.push(i);
            >
        >
  while(_del.length>0){
   this.blank.splice(_del.pop(), 1);
  >
    },
    seekMutexCell : fonction () {
        var deux = [];
        pour (var n dans this.blank) {
            if (this.bitCount(this.cell[this.blank[n]]) == 2) {
                two.push(this.blank[n]);
            >
        >
        pour (var i = 0; i < two.length; i ) {
            pour (var j = i 1; j < two.length; 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)) {
                        pour (n = 0; n < 8; n ) {
                            this.cell[this.getX(two[i])[n]] &= opt;
                        >
                    >
                    if ((two[i] - two[j]) % 9 == 0) {                       
                        pour (n = 8; n < 16; 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 ))) {
                        pour (n = 16; n < 24; n ) {
                            this.cell[this.getX(two[i])[n]] &= opt;
                        >
                    >
                    this.cell[two[j]] = ~opt;
                >
            >
        >
    },
    basicSolve : fonction () {
        faire {
            if (!this.updateCandidates(this.fixed)) {
                this.backForward();
            >
            this.seekUniqueCandidate();
            this.seekMutexCell();
            this.seekFilledable();
        } while (this.fixed.length != 0);
        renvoie this.blank.length == 0;
    },   
    setTrialCell : fonction() {
        pour (var i dans this.blank) {
            if (this.bitCount(this.cell[this.blank[i]]) == 2) {
                var valeur d'essai = 1 << this.numberOfTrailingZeros(this.cell[this.blank[i]]);
                var waitValue = 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], waitValue, this.cell));
                renvoie vrai ;
            >
        >
        retourner faux ;
    },
    backForward : function() {
        si (this.trials.length==0) {
            console.log("Peut-être pas de solution !");
            revenir ;
        >
        var retour = 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));
    },
    réinitialiser : fonction (données) {
        this.blank=[];
        this.fixed=[];
        this.cell=data.concat();
        pour (var je = 0; je < 81; je ) {
            if (this.bitCount(this.cell[i]) != 1) {
                this.blank.push(i);
            } autre {
                this.fixed.push(i);
            >
        >
    },
    trialSolve : fonction() {
        while (this.blank.length!=0) {
            si (this.setTrialCell()) {
                this.basicSolve();
            } autre {
                si (this.trials.length==0) {
                    //console.log("Impossible de revenir en arrière ! Peut-être pas de solution !");
                    pause;
                } autre {
                    this.backForward();
                    this.basicSolve();
                >
            >
        >
    },
    jouer : fonction() {
        console.log(this.showBoard());
        var start = new Date().getMilliseconds();
        si (!this.basicSolve()) {
            this.trialSolve();
        >
        var end = new Date().getMilliseconds();
        console.log(this.showBoard());
        si (this.check()) {
            console.log("[" (fin - début) "ms OK !]");
        } autre {
            console.log("[" (end - start) "ms, je ne peux pas le résoudre ?");
        >
  //retourne this.showBoard();
    },
    getX:fonction(idx){
        var voisins=new Array(24);
        var box=nouveau tableau(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 je=0;
        pour(var n=0;n<9;n ){
            if(n==c)continue;
            voisins[i ]=r*9 n;
        >
        pour(var n=0;n<9;n ){
            if(n==r)continue;
            voisins[i ]=c n*9;
        >
        pour(var n=0;n<9;n ){
            var t=xs boîte[n];
            if(t==idx)continue;
            voisins[i ]=t;
        >
          renvoyer les voisins ;
    },
 createTrialPoint:function(idx, val, board) {
        var tp = {};
        tp.idx = idx;
        tp.val = val;
        tp.data = board.concat();
        retour tp;
 >
};
//Sudoku.init("000000500000008300600100000080093000000000020700000000058000000000200017090000060");
//Sudoku.init("530070000600195000098000060800060003400803001700020006060000280000419005000080079");
Sudoku.init("800000000003600000070090200050007000000045700000100030001000068008500010090000400");
Sudoku.play();

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

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn