Javascript 实现的数独解题算法网页实例_javascript技巧

1）当我们拿到一个题目时，首先会根据已经知道的条件，进行数据的初步整理和分析。

相当于填写出9宫格里，所有的“确定项”，以及标记“可能选项”。

function refreshStat()

2）此后，思考会进入 猜测/验证 的循环阶段。

在9宫格中，可以对于“可能选项”进行尝试，验证是否违背现有条件。

每一个新的分支，最后的结果无非是两种，答案/出错。

复制代码 代码如下:

                while(true){
                    var a=setOne();
                    var b=refreshStat();
                    if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环
                        break;
                    }
                }

实际人脑思考的过程，也是要先遍历选项较少的分支。

所以，程序实现上也是 确定点/2叉分支/3叉分支/....

3）当所有的路径搜索下来，答案不是唯一的情况，是和数独游戏的宗旨相悖的。

以下部分是全部代码，为方便阅读，调试信息未删除。

复制代码 代码如下:

 
 

  <script><br>   function keygo(evt,obj){<br>       key = window .event?evt.keyCode:evt.which;<br>       var next=obj.tabIndex ;<br>       var inputs=document.getElementsByTagName("input");<br>       if (key==38){//↑<br>           if (next -9>=0 ) {<br>               inputs[next-9].select()<br>           }<br>       }<br>       if (key==40){//↓<br>           if (next +9<81 ) {<BR> inputs[next+9].select()<BR> }<BR> }<BR> if (key==37){//←<BR> if (next -1>=0 ) {<br>               inputs[next-1].select()<br>           }<br>       }<br>       if (key==39){//→<br>           if(next+1<81)inputs[next+1].select();<BR> }<BR> }<BR> </script>
 

004502006<br>000000005<br>002014007<br>008000012<br>070080050<br>930020700<br>600190200<br>020000000<br>300208500
可以文本拷贝到下框中后点粘贴，从左到右从上往下的81个数字序列，未填为0，中间非数字字符将忽略



  <script><br>   var maxRow =9;<br>   var maxCol = 9;<br>   var strTbody = ["<table id='sodukuTable' border='0'><tbody>"];<br>   for(var i = 0; i < maxRow; i++){<BR> strTbody.push("<tr>");<br>     for(var j = 0; j < maxCol; j++){<BR> strTbody.push("<td style='border-left:"+(j%3==0?1:0)<BR> +"px solid black ;border-right:"+(j%3==2?1:0)<BR> +"px solid black;border-top:"+(i%3==0?1:0)<BR> +"px solid black;border-bottom:"+(i%3==2?1:0)+"px solid black;' ><input style='width:20px;' tabindex='"+(i*9+j)<BR> +"'onclick='check(this);' onKeyUp='return keygo(event,this)'type='text' id='input"+(i*9+j)+"'name='n"+(i*9+j)+"'value='"+i+j+"' ></td>");<br>     }<br>    strTbody.push("</tr>"); <br>   }<br>   strTbody.push("</tbody></table>"); <br>   var sTbody = ["<table border='1'><tbody>"];<br>   for(var i = 0; i < maxRow; i++){<BR> sTbody.push("<tr>");<br>     for(var j = 0; j < maxCol; j++){<BR> sTbody.push("<td style='border-left:"+(j%3==0?1:0)<BR> +"px solid black ;border-right:"+(j%3==2?1:0)<BR> +"px solid black;border-top:"+(i%3==0?1:0)<BR> +"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>");<br>     }<br>    sTbody.push("</tr>"); <br>   }<br>   sTbody.push("</tbody></table>"); <br>   var obj = document.getElementById("sodukuTable");<br>   obj.innerHTML = strTbody.join("");<br>   var obj2 = document.getElementById("statusDiv");<br>   var grid=[    <br>    [5, 7, 0, 1, 2, 0, 0, 0, 0],<br>    [0, 0, 0, 0, 0, 0, 0, 0, 0],<br>    [0, 0, 6, 7, 0, 0, 0, 8, 0],<br>    [3, 0, 4, 0, 0, 9, 0, 7, 0],<br>    [0, 2, 0, 0, 7, 0, 0, 5, 0],<br>    [0, 1, 0, 3, 0, 0, 9, 0, 2],<br>    [0, 8, 0, 0, 0, 2, 1, 0, 0],<br>    [0, 0, 0, 0, 0, 0, 0, 0, 0],<br>    [0, 0, 0, 0, 5, 4, 0, 6, 3]];<br>   var candidatNum=[];<br>   var columns=[];<br>   var rows=[];<br>   var blook=[];<br>   var papers=0;<br>   var discards=0;<br>   var success=false;<br>   var steps = new Array();<br>   var log1 = document.getElementById("statusDiv"); <p>function Step(current1,arrys){<br>        this.temp1=new Array();<br>        this.step=[arrys[0],arrys[1],arrys[2]];<br>        for (var i = 0; i < 9; i++)<BR> {<BR> this.temp1[i]=new Array();<BR> for (var j = 0; j < 9; j++)<BR> {<BR> this.temp1[i][j]=current1[i][j];<BR> }<BR> }<BR>}<BR>out(grid);<BR>init();</P> <P>function push( current1, i, j, n) {<BR> var s = new Step(current1, [ i, j, n ]);<BR> steps.push(s);<BR>}<BR>function pop(){<BR> var step = steps.pop();<BR> discards ++;<BR> grid=step.temp1;<BR> grid[step.step[0]][step.step[1]] = step.step[2];<BR> var timeline = document.getElementById('PaperList');<BR> timeline.value += ('discard: ['+discards+']:['+papers+']\n');<BR> timeline.scrollTop = timeline.scrollHeight;<BR> return step;<BR>}<br><br>function check(obj){<BR> if(obj.value==0)return;<BR> for(var i=0;i<9;i++){<BR> for(var j=0;j<9;j++){<BR> var text = document.getElementById("input"+(i*9+j));<BR> if(text.value==obj.value){<BR> text.style.background="green";<BR> }else{<BR> text.style.background="";<BR> }<BR> }</P> <P> }</P> <P>}<BR>function CheckNumInput(array,num, x, y) {<BR> // 目标:<BR> // 冲突检查 参数 array:矩阵 num:检测值 x/y:检测位置<BR> // 行列宫均无冲突,return true;<BR> // 发现冲突,return false;<BR> if (((rows[x] & (1 << num)) == 0) && (columns[y] & (1 << num)) == 0<BR> && (blook[parseInt(x / 3) * 3 + parseInt(y / 3)] & (1 << num)) == 0) {<BR> return true;<BR> }<BR> return false;<BR>}</P><P>function out(array){<BR>    var result=true;<BR>    for (var i = 0; i < 9; i )<BR>        {<BR>            for (var j = 0; j < 9; j )<BR>            {<BR>        document.getElementById("input" (i*9 j)).value=array[i][j];<BR>                if(array[i][j]==0)result=false;<BR>            }<BR>        }<BR>        return result;<BR>}<BR>function setOne(){<BR>    var result = false;<BR>    //目标:<BR>    //    遍历矩阵,当前是否可以简单刷新,或者已经可以发现出错.<BR>    for (var i = 0; i < 9; i ) {<BR>        for (var j = 0; j < 9; j ) {<BR>            //目标:<BR>            // (grid[i][j] == 0 && candidatNum[i][j][0] == 0)  >> 没有候选数字,出错了<br>            // (candidatNum[i][j][0] == 1)                     >> 候选数字唯一<br>            // CheckNumInput(grid,candidatNum[i][j][10],i,j)   >> 检查此数字是否符合逻辑<br>            // 判断 没有候选数字||最后一个候选数字不符合逻辑的条件,  从这里回退或者返回出错<br>            if (grid[i][j] == 0 && candidatNum[i][j][0] == 0||<br>               (candidatNum[i][j][0] == 1&&!CheckNumInput(grid,candidatNum[i][j][10],i,j))) {<br>                    if (grid[i][j] == 0) {<br>                       result = false;<br>                    }<br>                    if (steps.length>0) {// 回退<br>                        pop();           // 当前标签已经被证明逻辑错误,废弃<br>                        return true;<br>                    } else {<br>                        if (!success) {<br>                            alert("栈为空 结束！");    //题目出错,结束<br>                            }<br>                        return false;<br>                    }<br>            }<br>            if (candidatNum[i][j][0] == 1) {              //唯一选择<br>                grid[i][j] = candidatNum[i][j][10];       //  更新矩阵<br>                refreshStat3(candidatNum[i][j][10],i,j);  //  更新行列宫<br>                candidatNum[i][j][0] = 0;                 //  标记已选<br>                result = true;<br>                continue;<br>            }<br><br>        }<br>    }<br>    if (result == false) { //对于(candidatNum[i][j][0] != 1)的情况,进行筛选<br>        return choose();<br>    }<br>    return result;<br>}<br>function refreshStat3( num, x, y) {   //  更新行列宫<br>        rows[x] |= 1<<num;<BR> columns[y] |= 1<<num;<BR> blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num ;</P> <P>}<BR>/*********************<BR> * 矩阵 数据分析<BR> * 统计 剩余可选项<BR> *********************/<BR>function refreshStat(){<BR> var over = true;<BR> // 目标:<BR> // 分解行/列/宫<BR> for (var i = 0; i < 9; i++) {<BR> rows[i] = 0; //行<BR> columns[i] = 0; //列<BR> blook[i] = 0; //宫<BR> for (var j = 0; j < 9; j++) {<BR> if (grid[i][j] != 0) {<BR> rows[i] |= 1 << grid[i][j];<BR> } else {<BR> rows[i] &= ~(1 << grid[i][j]);<BR> }<BR> if (grid[j][i] != 0) {<BR> columns[i] |= 1 << grid[j][i];<BR> } else {<BR> columns[i] &= ~(1 << grid[j][i]);<BR> }<BR> if (grid[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3] != 0) {<BR> blook[i] |= 1 << grid[parseInt(i / 3 )* 3 + parseInt(j / 3)][i % 3 * 3 + j % 3];<BR> }<BR> }<BR> }<BR> // 目标:<BR> // 遍历矩阵,进行候选标记candidatNum[i][j][0]<BR> // candidatNum[i][j][0] = 0; >>>>    已有确定值<br>    //      candidatNum[i][j][0] = k;    >>>>    可能值数目<br>    //      candidatNum[i][j][1] = 987654321x    2进制数位表示的可选数字<br>    for (var i = 0; i < 9; i++) {<BR> for (var j = 0; j < 9; j++) {<BR> if (grid[i][j] != 0) {<BR> candidatNum[i][j][0] = 0;<BR> continue;<BR> }<BR> var size = 0;<BR> over = false;<BR> for (var k = 1; k < 10; k++) {<BR> if (CheckNumInput(grid, k, i, j)) {<BR> candidatNum[i][j][1] |= 1 << k;<BR> candidatNum[i][j][10] = k;<BR> over = false;<BR> size++;<BR> } else {<BR> candidatNum[i][j][1] &= ~(1 << k);<BR> }<BR> }<BR> candidatNum[i][j][0] = size; //标记剩余选项数目<BR> }<BR> }<BR> return over;<BR>}</P><P>function calculate(){  //功能入口<BR>    //读取数据<BR>    var start=new Date();<BR>    for (var i = 0; i < 9; i )<BR>        {    <BR>            for (var j = 0; j < 9; j )<BR>            {<BR>                var text = document.getElementById("input" (i*9 j));<BR>                grid[i][j]=parseInt(text.value);<BR>        }<BR>    }<br><br>    //刷新网格    <BR>    refreshStat();<BR>    out(grid);<BR>    //计算矩阵<BR>    while(true){<BR>        var a=setOne();<BR>        var b=refreshStat();<BR>        if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环<BR>            break;<BR>        }<BR>    }<BR>    out(grid);    //答案<BR>    alert("用时：" (new Date()-start) "ms");<BR>    success = true;<BR>    //计算结束<br><br>    //验证答案是否唯一<BR>    if (papers != discards){<BR>            if (steps.length>0) {// 回退<br>                pop();           // 当前标签废弃<br>                //计算矩阵<br>                while(true){<br>                    var a=setOne();<br>                    var b=refreshStat();<br>                    if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环<br>                        break;<br>                    }<br>                }<br>                if (b) {<br>                    alert("答案不唯一！记录！");<br>                    out(grid);    //答案<br>                    }<br>                else {<br>                    alert("答案唯一！！");    //答案唯一<br>                }<br>            } else {<br>                alert("出错 结束！");<br>                return false;<br>            }<br>    }<br>}<br>function clearGrid(){<br>    for (var i = 0; i < 9; i++){<BR> for (var j = 0; j < 9; j++){<BR> grid[i][j]=0;<BR> document.getElementById("input"+(i*9+j)).value=grid[i][j];<BR> }<BR> }<BR> out(grid);<BR>}<BR>function init(){<BR> for (var i = 0; i < 9; i++)<BR> { candidatNum[i]=new Array();<br><br> for (var j = 0; j < 9; j++)<BR> { candidatNum[i][j]=new Array();</P><P>        for (var k = 0; k < 11; k )<BR>                {    candidatNum[i][j][k]=0;<BR>        }<BR>        }<BR>    }<BR>}<BR>function choose() {<BR>    //目标:<BR>    //    遍历矩阵,从当前位置建立搜索分支.<BR>    var binarynode = false;<BR>    for (var i = 0; i < 9; i ) {<BR>        for (var j = 0; j < 9; j ) {<BR>    //      2叉树分支:<BR>    //      如果在某位置有两种可能,选项1/选项2<BR>    //      则假设是选项1,并进行验算,同时按选项2生成一个新的标签<BR>            if (candidatNum[i][j][0] == 2) {// 有2种选择<BR>                binarynode = true;<BR>                var found = -1;<BR>                for (var k = 1; k < 10; k ) {<BR>                    if  ((candidatNum[i][j][1] & (1 << k)) > 0) {<br>                        if (found > 0) {<br>                            papers ;<br>                            var timeline = document.getElementById('PaperList');<br>                            timeline.value = ('add papers:' papers ':' i ' ' j ' ' k 'n');<br>                            timeline.scrollTop = timeline.scrollHeight;<br>                            push(grid, i, j, k);<br>                        }else{<br>                            found = k;<br>                        }<br>                    }<br>                }<br>                grid[i][j] = found;<br>                candidatNum[i][j][0] = 0; // 在当前标签上标记已选<br>                            var timeline = document.getElementById('PaperList');<br>                            timeline.value = ('TRY CURRENT:' i ' ' j ' ' found 'n');<br>                            timeline.scrollTop = timeline.scrollHeight;<br>                return true;<br>            }<br>        }<br>    }<br>    if (!binarynode) {<br>    var timeline = document.getElementById('PaperList');<br>    timeline.value = ('2叉分支未找到!n');<br>    timeline.scrollTop = timeline.scrollHeight;<br>        for (var i = 0; i < 9; i ) {<BR>            for (var j = 0; j < 9; j ) {<BR>        // 2叉树查找失败时，启动3叉树分支，作为扩充，还可以启动3叉树分支：<BR>        //      如果在某位置有三种可能,选项1/选项2/选项3<BR>        //      则假设是选项1,并进行验算,同时按选项2生成一个新的标签<BR>                if (candidatNum[i][j][0] == 3) {// 有3种选择<BR>                            var timeline = document.getElementById('PaperList');<BR>                            timeline.value = ('发现3叉分支!n');<BR>                            timeline.scrollTop = timeline.scrollHeight;<BR>                    binarynode = true;<BR>                    var found = -1;<BR>                    for (var k = 1; k < 10; k ) {<BR>                        if  ((candidatNum[i][j][1] & (1 << k)) > 0) {<br>                            if (found > 0) {<br>                                papers ;<br>                            var timeline = document.getElementById('PaperList');<br>                            timeline.value = ('add papers:' papers ':' i ' ' j ' ' k 'n');<br>                            timeline.scrollTop = timeline.scrollHeight;<br>                                push(grid, i, j, k);<br>                            }else{<br>                                found = k;<br>                            }<br>                        }<br>                    }<br>                    grid[i][j] = found;<br>                    candidatNum[i][j][0] = 0; // 在当前标签上标记已选<br>                            var timeline = document.getElementById('PaperList');<br>                            timeline.value = ('TRY CURRENT:' i ' ' j ' ' found 'n');<br>                            timeline.scrollTop = timeline.scrollHeight;<br>                    return true;<br>                }<br>            }<br>        }<br>    }<br>    return false;<br>}<br>function paste(){<br>    var gridstr= document.getElementById("gtxt").value;<br>    var a = gridstr.replace(/[^0-9]/g,'');<br>    if(a.length!=81){<br>       alert("数据格式不正确:n" gridstr);<br>       return;<br>    }<br>    for (var i = 0; i < 9; i )<BR>        {<BR>            for (var j = 0; j < 9; j ){<BR>                grid[i][j]=a.charAt(i*9 j);<BR>                document.getElementById("input" (i*9 j)).value=grid[i][j];<BR>        }<BR>    }<BR>    out(grid);<BR>    papers = 0;<BR>    discards = 0;<BR>    success = false;<BR>    steps = new Array();<BR>}<BR>  </script>
  建议使用IE浏览器,F12开启调试模式