DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> 關於JavaScript >> Javascript 實現的數獨解題算法網頁實例
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)當所有的路徑搜索下來,答案不是唯一的情況,是和數獨游戲的宗旨相悖的。

以下部分是全部代碼,為方便閱讀,調試信息未刪除。

復制代碼 代碼如下:
<html>
 <head>
  <title>數獨解題程序</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){//↑
           if (next -9>=0 ) {
               inputs[next-9].select()
           }
       }
       if (key==40){//↓
           if (next +9<81 ) {
               inputs[next+9].select()
           }
       }
       if (key==37){//←
           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="計算">
<input type=button name="clear" onclick="clearGrid()" value="清空">
<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="粘貼" >可以文本拷貝到下框中後點粘貼,從左到右從上往下的81個數字序列,未填為0,中間非數字字符將忽略<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)  {
    //  目標:
    //      沖突檢查  參數 array:矩陣 num:檢測值 x/y:檢測位置
    //      行列宮均無沖突,return true;
    //            發現沖突,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;
    //目標:
    //    遍歷矩陣,當前是否可以簡單刷新,或者已經可以發現出錯.
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            //目標:
            // (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 && 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) {// 回退
                        pop();           // 當前標簽已經被證明邏輯錯誤,廢棄
                        return true;
                    } else {
                        if (!success) {
                            alert("棧為空 結束!");    //題目出錯,結束
                            }
                        return false;
                    }
            }
            if (candidatNum[i][j][0] == 1) {              //唯一選擇
                grid[i][j] = candidatNum[i][j][10];       //  更新矩陣
                refreshStat3(candidatNum[i][j][10],i,j);  //  更新行列宮
                candidatNum[i][j][0] = 0;                 //  標記已選
                result = true;
                continue;
            }

        }
    }
    if (result == false) { //對於(candidatNum[i][j][0] != 1)的情況,進行篩選
        return choose();
    }
    return result;
}
function refreshStat3( num, x, y) {   //  更新行列宮
        rows[x] |= 1<<num;
        columns[y] |= 1<<num;
        blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num ;

}
/*********************
 * 矩陣 數據分析
 * 統計 剩余可選項
 *********************/
function refreshStat(){
    var over = true;
    //  目標:
    //      分解行/列/宮
    for (var i = 0; i < 9; i++) {
        rows[i] = 0;    //行
        columns[i] = 0; //列
        blook[i] = 0;   //宮
        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];
            }
        }
    }
    //  目標:
    //      遍歷矩陣,進行候選標記candidatNum[i][j][0]
    //      candidatNum[i][j][0] = 0;    >>>>    已有確定值
    //      candidatNum[i][j][0] = k;    >>>>    可能值數目
    //      candidatNum[i][j][1] = 987654321x    2進制數位表示的可選數字
    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;  //標記剩余選項數目
    }
    }
    return over;
}

function calculate(){  //功能入口
    //讀取數據
    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);
        }
    }

    //刷新網格   
    refreshStat();
    out(grid);
    //計算矩陣
    while(true){
        var a=setOne();
        var b=refreshStat();
        if(!a||b){ //如果 a==false 或者 b==ture,則可以跳出循環
            break;
        }
    }
    out(grid);    //答案
    alert("用時:"+(new Date()-start)+"ms");
    success = true;
    //計算結束

    //驗證答案是否唯一
    if (papers != discards){
            if (steps.length>0) {// 回退
                pop();           // 當前標簽廢棄
                //計算矩陣
                while(true){
                    var a=setOne();
                    var b=refreshStat();
                    if(!a||b){ //如果 a==false 或者 b==ture,則可以跳出循環
                        break;
                    }
                }
                if (b) {
                    alert("答案不唯一!記錄!");
                    out(grid);    //答案
                    }
                else {
                    alert("答案唯一!!");    //答案唯一
                }
            } else {
                alert("出錯 結束!");
                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() {
    //目標:
    //    遍歷矩陣,從當前位置建立搜索分支.
    var binarynode = false;
    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
    //      2叉樹分支:
    //      如果在某位置有兩種可能,選項1/選項2
    //      則假設是選項1,並進行驗算,同時按選項2生成一個新的標簽
            if (candidatNum[i][j][0] == 2) {// 有2種選擇
                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; // 在當前標簽上標記已選
                            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叉分支未找到!\n');
    timeline.scrollTop = timeline.scrollHeight;
        for (var i = 0; i < 9; i++) {
            for (var j = 0; j < 9; j++) {
        // 2叉樹查找失敗時,啟動3叉樹分支,作為擴充,還可以啟動3叉樹分支:
        //      如果在某位置有三種可能,選項1/選項2/選項3
        //      則假設是選項1,並進行驗算,同時按選項2生成一個新的標簽
                if (candidatNum[i][j][0] == 3) {// 有3種選擇
                            var timeline = document.getElementById('PaperList');
                            timeline.value += ('發現3叉分支!\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; // 在當前標簽上標記已選
                            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("數據格式不正確:\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>
  建議使用IE浏覽器,F12開啟調試模式<br>
<br><span>
<textarea id="PaperList" cols="30" rows="20" style="position:absolute;left:550px;"></textarea></span>
 </body>
</html>

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved