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.
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实现数独解法的全部代码了,希望大家能够喜欢。