Javascript implementation of the sudoku algorithm web page example

  • 2020-03-26 21:31:36
  • OfStack

1) when we get a topic, we will first sort out and analyze the data according to the conditions we already know.

This is equivalent to filling out 9 boxes, all the "ok items", and marking "possible options".

The function refreshStat ()

2) after that, the thinking moves into a guessing/verification cycle.

In the box 9, you can try out the "possible options" to verify that an existing condition is violated.

For each new branch, the end result is nothing more than two answers/errors.


                while(true){
                    var a=setOne();
                    var b=refreshStat();
                    if(!a||b){ //If a==false or b== true, the loop can be broken
                        break;
                    }
                }

The actual process of human thinking also involves traversing the less selective branches first.

Therefore, the program implementation is also determined by the point /2 fork /3 fork /...

3) when all the paths are searched down, the answer is not the only case, is contrary to the purpose of sudoku.

The following part is the entire code. For easy reading, the debugging information has not been deleted.


<html>
 <head>
  <title> Sudoku program </title>
<meta http-equiv="Content-Type" content="text/html; charset=GBK" />
  <script>
   function keygo(evt,obj){
       key = window .event?evt.keyCode:evt.which;
       var next=obj.tabIndex ;
       var inputs=document.getElementsByTagName("input");
       if (key==38){// write 
           if (next -9>=0 ) {
               inputs[next-9].select()
           }
       }
       if (key==40){// left 
           if (next +9<81 ) {
               inputs[next+9].select()
           }
       }
       if (key==37){// please 
           if (next -1>=0 ) {
               inputs[next-1].select()
           }
       }
       if (key==39){// - 
           if(next+1<81)inputs[next+1].select();
       }
   }
  </script>
 </head>
<body onload="init();">
<div id="sodukuTable"></div><input type=button name="cal" onclick="calculate()" value=" To calculate ">
<input type=button name="clear" onclick="clearGrid()" value=" empty ">
<br><span><textarea id="gtxt" cols="19" rows="10">004502006
000000005
002014007
008000012
070080050
930020700
600190200
020000000
300208500</textarea></span>
<input type=button name="cal" onclick="paste()" value=" paste " > You can copy the text into the box below and then paste it, from left to right, from top to bottom 81 Sequence of Numbers, not filled in as 0 , intermediate non-numeric characters will be ignored <br>
<span></span><br><span id="statusDiv"></span><span id="log"></span>
  <script>
   var maxRow =9;
   var maxCol = 9;
   var strTbody = ["<table id='sodukuTable' border='0'><tbody>"];
   for(var i = 0; i < maxRow; i++){
    strTbody.push("<tr>");
     for(var j = 0; j < maxCol; j++){
      strTbody.push("<td style='border-left:"+(j%3==0?1:0)
            +"px solid black ;border-right:"+(j%3==2?1:0)
            +"px solid black;border-top:"+(i%3==0?1:0)
            +"px solid black;border-bottom:"+(i%3==2?1:0)+"px solid black;' ><input style='width:20px;' tabindex='"+(i*9+j)
        +"'onclick='check(this);' onKeyUp='return keygo(event,this)'type='text' id='input"+(i*9+j)+"'name='n"+(i*9+j)+"'value='"+i+j+"' ></td>");
     }
    strTbody.push("</tr>"); 
   }
   strTbody.push("</tbody></table>"); 
   var sTbody = ["<table border='1'><tbody>"];
   for(var i = 0; i < maxRow; i++){
    sTbody.push("<tr>");
     for(var j = 0; j < maxCol; j++){
      sTbody.push("<td style='border-left:"+(j%3==0?1:0)
            +"px solid black ;border-right:"+(j%3==2?1:0)
            +"px solid black;border-top:"+(i%3==0?1:0)
            +"px solid black;border-bottom:"+(i%3==2?1:0)+"px solid black;'><div style='width:25px;height:25px'  id='status"+(i*9+j)+"'name='div"+i+j+"'  ></div></td>");
     }
    sTbody.push("</tr>"); 
   }
   sTbody.push("</tbody></table>"); 
   var obj = document.getElementById("sodukuTable");
   obj.innerHTML = strTbody.join("");
   var obj2 = document.getElementById("statusDiv");
   var grid=[    
    [5, 7, 0, 1, 2, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 6, 7, 0, 0, 0, 8, 0],
    [3, 0, 4, 0, 0, 9, 0, 7, 0],
    [0, 2, 0, 0, 7, 0, 0, 5, 0],
    [0, 1, 0, 3, 0, 0, 9, 0, 2],
    [0, 8, 0, 0, 0, 2, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 5, 4, 0, 6, 3]];
   var candidatNum=[];
   var columns=[];
   var rows=[];
   var blook=[];
   var papers=0;
   var discards=0;
   var success=false;
   var steps = new Array();
   var log1 = document.getElementById("statusDiv");
function Step(current1,arrys){
        this.temp1=new Array();
        this.step=[arrys[0],arrys[1],arrys[2]];
        for (var i = 0; i < 9; i++)
            {
                this.temp1[i]=new Array();
                for (var j = 0; j < 9; j++)
                    {
                    this.temp1[i][j]=current1[i][j];
                    }
                }
}
out(grid);
init();
function push( current1,  i,  j,  n) {
        var s = new Step(current1, [ i, j, n ]);
        steps.push(s);
}
function pop(){
        var step = steps.pop();
        discards ++;
        grid=step.temp1;
        grid[step.step[0]][step.step[1]] = step.step[2];
                var timeline = document.getElementById('PaperList');
                timeline.value += ('discard: ['+discards+']:['+papers+']n');
                timeline.scrollTop = timeline.scrollHeight;
        return step;
}

function check(obj){
    if(obj.value==0)return;
    for(var i=0;i<9;i++){
        for(var j=0;j<9;j++){
            var text = document.getElementById("input"+(i*9+j));
            if(text.value==obj.value){
                text.style.background="green";
            }else{
                text.style.background="";
            }
        }
    }
}
function CheckNumInput(array,num,  x,  y)  {
    //  Goal:
    //          Conflict check & NBSP; Parameter array: matrix num: check value x/y: check position
    //          There is no conflict between rows and rows,return true;
    //                      Conflict detected,return false;
    if (((rows[x] & (1 << num)) == 0) && (columns[y] & (1 << num)) == 0
        && (blook[parseInt(x / 3) * 3 + parseInt(y / 3)] & (1 << num)) == 0) {
        return true;
        }
    return false;
}
function out(array){
    var result=true;
    for (var i = 0; i < 9; i++)
        {
            for (var j = 0; j < 9; j++)
            {
        document.getElementById("input"+(i*9+j)).value=array[i][j];
                if(array[i][j]==0)result=false;
            }
        }
        return result;
}
function setOne(){
    var result = false;
    //Goal:
    //      Traversing the matrix, whether it is currently easy to refresh, or can already detect errors.
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            //Goal:
            //(grid [I] [j] = = 0 && candidatNum [I] [j] [0] = = 0)  >> There are no candidate Numbers
            //(candidatNum [I] [j] [0] = = 1)                                        >> Candidate number unique
            //CheckNumInput (grid, candidatNum [I] [j] [10], I, j)    >> Check that this number is logical
            //Judge that there is no candidate number || the last candidate number is not a logical condition,& NBSP; There was a fallback or return error from here
            if (grid[i][j] == 0 && candidatNum[i][j][0] == 0||
               (candidatNum[i][j][0] == 1&&!CheckNumInput(grid,candidatNum[i][j][10],i,j))) {
                    if (grid[i][j] == 0) {
                       result = false;
                    }
                    if (steps.length>0) {//  The fallback 
                        pop();           //The current tag has been proven to be logically incorrect and deprecated
                        return true;
                    } else {
                        if (!success) {
                            alert(" The stack is empty   The end! ");    //They're wrong. End
                            }
                        return false;
                    }
            }
            if (candidatNum[i][j][0] == 1) {              //The only choice
                grid[i][j] = candidatNum[i][j][10];       //  Update matrix
                refreshStat3(candidatNum[i][j][10],i,j);  //  Palace of renewal
                candidatNum[i][j][0] = 0;                 //  Mark the selected
                result = true;
                continue;
            }

        }
    }
    if (result == false) { //For (candidatNum [I] [j] [0]! = 1), select
        return choose();
    }
    return result;
}
function refreshStat3( num, x, y) {   //  Palace of renewal
        rows[x] |= 1<<num;
        columns[y] |= 1<<num;
        blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num ;
}

function refreshStat(){
    var over = true;
    //  Goal:
    //          Break down the rows/columns/houses
    for (var i = 0; i < 9; i++) {
        rows[i] = 0;    // line 
        columns[i] = 0; // column 
        blook[i] = 0;   // palace 
        for (var j = 0; j < 9; j++) {
            if (grid[i][j] != 0) {
                rows[i] |= 1 << grid[i][j];
            } else {
                rows[i] &= ~(1 << grid[i][j]);
            }
            if (grid[j][i] != 0) {
                columns[i] |= 1 << grid[j][i];
            } else {
                columns[i] &= ~(1 << grid[j][i]);
            }
            if (grid[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3] != 0) {
                blook[i] |= 1 << grid[parseInt(i / 3 )* 3 + parseInt(j / 3)][i % 3 * 3 + j % 3];
            }
        }
    }
    //  Goal:
    //          Traversal matrix for candidate marker candidatNum[I][j][0]
    //          CandidatNum [I] [j] [0] = 0;      >>>>       Established value
    //          CandidatNum [I] [j] [0] = k;      >>>>       Number of possible values
    //          CandidatNum [I] [j] [1] = 987654321 x       An optional digit represented by a base 2 digit
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
        if (grid[i][j] != 0) {
            candidatNum[i][j][0] = 0;
            continue;
        }
        var size = 0;
        over = false;
        for (var k = 1; k < 10; k++) {
            if (CheckNumInput(grid, k, i, j)) {
                candidatNum[i][j][1] |= 1 << k;
                candidatNum[i][j][10] = k;
                over = false;
                size++;
            } else {
                candidatNum[i][j][1] &= ~(1 << k);
            }
        }
        candidatNum[i][j][0] = size;  //Mark the number of remaining options
    }
    }
    return over;
}
function calculate(){  //Function of entrance
    //Read the data
    var start=new Date();
    for (var i = 0; i < 9; i++)
        {    
            for (var j = 0; j < 9; j++)
            {
                var text = document.getElementById("input"+(i*9+j));
                grid[i][j]=parseInt(text.value);
        }
    }

    //Refresh the grid & cake;    
    refreshStat();
    out(grid);
    //Calculation of matrix
    while(true){
        var a=setOne();
        var b=refreshStat();
        if(!a||b){ //If a==false or b== true, the loop can be broken
            break;
        }
    }
    out(grid);    // The answer 
    alert(" Available: "+(new Date()-start)+"ms");
    success = true;
    //Calculate the end

    //Verify that the answer is unique
    if (papers != discards){
            if (steps.length>0) {//  The fallback 
                pop();           //Current label discard
                //Calculation of matrix
                while(true){
                    var a=setOne();
                    var b=refreshStat();
                    if(!a||b){ //If a==false or b== true, the loop can be broken
                        break;
                    }
                }
                if (b) {
                    alert(" Not the only answer! Record! ");
                    out(grid);    // The answer 
                    }
                else {
                    alert("The only answer !!!!! ");    //The only answer
                }
            } else {
                alert(" error   The end! ");
                return false;
            }
    }
}
function clearGrid(){
    for (var i = 0; i < 9; i++){
        for (var j = 0; j < 9; j++){
            grid[i][j]=0;
            document.getElementById("input"+(i*9+j)).value=grid[i][j];
        }
    }
    out(grid);
}
function init(){
     for (var i = 0; i < 9; i++)
        {    candidatNum[i]=new Array();

            for (var j = 0; j < 9; j++)
            {    candidatNum[i][j]=new Array();
        for (var k = 0; k < 11; k++)
                {    candidatNum[i][j][k]=0;
        }
        }
    }
}
function choose() {
    //Goal:
    //      Traverses the matrix, creating a search branch from the current location.
    var binarynode = false;
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
    //          2 branches:
    //          If there are two possibilities at a certain location, choice 1 over choice 2
    //          Then assume option 1 and check it. At the same time, generate a new label according to option 2
            if (candidatNum[i][j][0] == 2) {//There are two choices
                binarynode = true;
                var found = -1;
                for (var k = 1; k < 10; k++) {
                    if  ((candidatNum[i][j][1] & (1 << k)) > 0) {
                        if (found > 0) {
                            papers ++;
                            var timeline = document.getElementById('PaperList');
                            timeline.value += ('add papers:'+papers+':'+i+' '+j+' '+k+'n');
                            timeline.scrollTop = timeline.scrollHeight;
                            push(grid, i, j, k);
                        }else{
                            found = k;
                        }
                    }
                }
                grid[i][j] = found;
                candidatNum[i][j][0] = 0; //Mark selected on the current label
                            var timeline = document.getElementById('PaperList');
                            timeline.value += ('TRY CURRENT:'+i+' '+j+' '+found+'n');
                            timeline.scrollTop = timeline.scrollHeight;
                return true;
            }
        }
    }
    if (!binarynode) {
    var timeline = document.getElementById('PaperList');
    timeline.value += ('2 Fork branch not found !n');
    timeline.scrollTop = timeline.scrollHeight;
        for (var i = 0; i < 9; i++) {
            for (var j = 0; j < 9; j++) {
        //If the two-tree search fails, the three-tree branch can be started. As an extension, the three-tree branch can also be started:
        //          If there are three possibilities in a location, choice 1 over choice 2 over choice 3
        //          Then assume option 1 and check it. At the same time, generate a new label according to option 2
                if (candidatNum[i][j][0] == 3) {//There are three options
                            var timeline = document.getElementById('PaperList');
                            timeline.value += (' found 3 Fork branch !n');
                            timeline.scrollTop = timeline.scrollHeight;
                    binarynode = true;
                    var found = -1;
                    for (var k = 1; k < 10; k++) {
                        if  ((candidatNum[i][j][1] & (1 << k)) > 0) {
                            if (found > 0) {
                                papers ++;
                            var timeline = document.getElementById('PaperList');
                            timeline.value += ('add papers:'+papers+':'+i+' '+j+' '+k+'n');
                            timeline.scrollTop = timeline.scrollHeight;
                                push(grid, i, j, k);
                            }else{
                                found = k;
                            }
                        }
                    }
                    grid[i][j] = found;
                    candidatNum[i][j][0] = 0; //Mark selected on the current label
                            var timeline = document.getElementById('PaperList');
                            timeline.value += ('TRY CURRENT:'+i+' '+j+' '+found+'n');
                            timeline.scrollTop = timeline.scrollHeight;
                    return true;
                }
            }
        }
    }
    return false;
}
function paste(){
    var gridstr= document.getElementById("gtxt").value;
    var a = gridstr.replace(/[^0-9]/g,'');
    if(a.length!=81){
       alert(" The data format is incorrect :n"+gridstr);
       return;
    }
    for (var i = 0; i < 9; i++)
        {
            for (var j = 0; j < 9; j++){
                grid[i][j]=a.charAt(i*9+j);
                document.getElementById("input"+(i*9+j)).value=grid[i][j];
        }
    }
    out(grid);
    papers = 0;
    discards = 0;
    success = false;
    steps = new Array();
}
  </script>
   It is recommended to use IE The browser ,F12 Turn on debug mode <br>
<br><span>
<textarea id="PaperList" cols="30" rows="20" style="position:absolute;left:550px;"></textarea></span>
 </body> 
</html>


Related articles: