JavaScript之破解数独（附详细代码）

灰太狼 2022-06-02 12:11 196阅读 0赞

在[上一篇分享][Link 1]中，我们用Python和Django来破解数独，这对不熟悉Python和Django的人来说是非常不友好的。这次，笔者只用HTML和JavaScript写了破解数独的程序，对于熟悉前端的人，这是十分友好的。  
  话不多说，直接上代码。  
  首页index.html的代码如下：

<html>
    
    <head>
        <link rel="stylesheet" type="text/css" href="mystyle.css" />
        <script type="text/javascript" src="answer.js"></script>
    </head>
    
    <body background="mountain.jpg">
        <center><h1>Solve A Sudoku</h1></center>
        <table class="sd" border="0" align="center" cellspacing="1" cellpadding="1">
            <tr>
                <td class="xx"><input id="1" class="big" maxlength="1"></td>
                <td class="xx"><input id="2" class="big" maxlength="1"></td>
                <td class="rr"><input id="3" class="big" maxlength="1"></td>
                <td class="xx"><input id="4" class="big" maxlength="1"></td>
                <td class="xx"><input id="5" class="big" maxlength="1"></td>
                <td class="rr"><input id="6" class="big" maxlength="1"></td>
                <td class="xx"><input id="7" class="big" maxlength="1"></td>
                <td class="xx"><input id="8" class="big" maxlength="1"></td>
                <td class="xx"><input id="9" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="10" class="big" maxlength="1"></td>
                <td class="xx"><input id="11" class="big" maxlength="1"></td>
                <td class="rr"><input id="12" class="big" maxlength="1"></td>
                <td class="xx"><input id="13" class="big" maxlength="1"></td>
                <td class="xx"><input id="14" class="big" maxlength="1"></td>
                <td class="rr"><input id="15" class="big" maxlength="1"></td>
                <td class="xx"><input id="16" class="big" maxlength="1"></td>
                <td class="xx"><input id="17" class="big" maxlength="1"></td>
                <td class="xx"><input id="18" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="19" class="big" maxlength="1"></td>
                <td class="xx"><input id="20" class="big" maxlength="1"></td>
                <td class="rr"><input id="21" class="big" maxlength="1"></td>
                <td class="xx"><input id="22" class="big" maxlength="1"></td>
                <td class="xx"><input id="23" class="big" maxlength="1"></td>
                <td class="rr"><input id="24" class="big" maxlength="1"></td>
                <td class="xx"><input id="25" class="big" maxlength="1"></td>
                <td class="xx"><input id="26" class="big" maxlength="1"></td>
                <td class="xx"><input id="27" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="top"><input id="28" class="big" maxlength="1"></td>
                <td class="top"><input id="29" class="big" maxlength="1"></td>
                <td class="topr"><input id="30" class="big" maxlength="1"></td>
                <td class="top"><input id="31" class="big" maxlength="1"></td>
                <td class="top"><input id="32" class="big" maxlength="1"></td>
                <td class="topr"><input id="33" class="big" maxlength="1"></td>
                <td class="top"><input id="34" class="big" maxlength="1"></td>
                <td class="top"><input id="35" class="big" maxlength="1"></td>
                <td class="top"><input id="36" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="37" class="big" maxlength="1"></td>
                <td class="xx"><input id="38" class="big" maxlength="1"></td>
                <td class="rr"><input id="39" class="big" maxlength="1"></td>
                <td class="xx"><input id="40" class="big" maxlength="1"></td>
                <td class="xx"><input id="41" class="big" maxlength="1"></td>
                <td class="rr"><input id="42" class="big" maxlength="1"></td>
                <td class="xx"><input id="43" class="big" maxlength="1"></td>
                <td class="xx"><input id="44" class="big" maxlength="1"></td>
                <td class="xx"><input id="45" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="46" class="big" maxlength="1"></td>
                <td class="xx"><input id="47" class="big" maxlength="1"></td>
                <td class="rr"><input id="48" class="big" maxlength="1"></td>
                <td class="xx"><input id="49" class="big" maxlength="1"></td>
                <td class="xx"><input id="50" class="big" maxlength="1"></td>
                <td class="rr"><input id="51" class="big" maxlength="1"></td>
                <td class="xx"><input id="52" class="big" maxlength="1"></td>
                <td class="xx"><input id="53" class="big" maxlength="1"></td>
                <td class="xx"><input id="54" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="top"><input id="55" class="big" maxlength="1"></td>
                <td class="top"><input id="56" class="big" maxlength="1"></td>
                <td class="topr"><input id="57" class="big" maxlength="1"></td>
                <td class="top"><input id="58" class="big" maxlength="1"></td>
                <td class="top"><input id="59" class="big" maxlength="1"></td>
                <td class="topr"><input id="60" class="big" maxlength="1"></td>
                <td class="top"><input id="61" class="big" maxlength="1"></td>
                <td class="top"><input id="52" class="big" maxlength="1"></td>
                <td class="top"><input id="63" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="64" class="big" maxlength="1"></td>
                <td class="xx"><input id="65" class="big" maxlength="1"></td>
                <td class="rr"><input id="66" class="big" maxlength="1"></td>
                <td class="xx"><input id="67" class="big" maxlength="1"></td>
                <td class="xx"><input id="68" class="big" maxlength="1"></td>
                <td class="rr"><input id="69" class="big" maxlength="1"></td>
                <td class="xx"><input id="70" class="big" maxlength="1"></td>
                <td class="xx"><input id="71" class="big" maxlength="1"></td>
                <td class="xx"><input id="72" class="big" maxlength="1"></td>
            </tr>
            <tr>
                <td class="xx"><input id="73" class="big" maxlength="1"></td>
                <td class="xx"><input id="74" class="big" maxlength="1"></td>
                <td class="rr"><input id="75" class="big" maxlength="1"></td>
                <td class="xx"><input id="76" class="big" maxlength="1"></td>
                <td class="xx"><input id="77" class="big" maxlength="1"></td>
                <td class="rr"><input id="78" class="big" maxlength="1"></td>
                <td class="xx"><input id="79" class="big" maxlength="1"></td>
                <td class="xx"><input id="80" class="big" maxlength="1"></td>
                <td class="xx"><input id="81" class="big" maxlength="1"></td>
            </tr>
        </table>
        <br>
        <center>
        <button type="button" onclick="clc()">Clear</button> 
        <button type="button" onclick="get_answer()">Show Answer</button> 
        </center>
    </body>
    
    </html>

其使用的样式表mystyle.css的代码如下：

.sd { table-layout: fixed; border: #443 3px solid; width: 355px; height: 355px; background-color: #fff; vertical-align: middle; border-collapse: collapse; text-align: center; }
    .big { FONT-SIZE: 25px; border: none; background-color: transparent; WIDTH: 30px; HEIGHT: 30px; LINE-HEIGHT: 28px; TEXT-ALIGN: center; margin: 0px; COLOR: #0000FF; FONT-FAMILY: Verdana; }
    td.xx { border-right: #999 1px solid; border-top: #999 1px solid; width: 30px; height: 30px; text-align: center; LINE-height: 30px; }
    td.rr { border-right: #443 2px solid; border-top: #999 1px solid; width: 30px; height: 30px; text-align: center; LINE-height: 30px; }
    td.top { border-right: #999 1px solid; border-top: #443 2px solid; width: 30px; height: 30px; text-align: center; LINE-height: 30px; }
    td.topr { border-right: #443 2px solid; border-top: #443 2px solid; width: 30px; height: 30px; text-align: center; LINE-height: 30px; }

其使用的JavaScript的代码（answer.js）如下：

//clear all the input
    function clc(){ 
        for(var i=0; i<81; i++){
            document.getElementsByTagName("input")[i].value = "";
            document.getElementsByTagName("input")[i].style.color = 'blue';
        }
        document.body.style.backgroundImage = "url(mountain.jpg)";
    }
    
    //press "show answer" button and show answer then
    function get_answer(){ 
        var bool = check_input();
        if(bool){
            var grid = readAPuzzle();
            if(!isValidGrid(grid)){
                alert("Invalid input, please try again!");
            }
            else{
                if(search(grid)){
                    output_ans();
                    document.body.style.backgroundImage = "url(sky.jpg)";
                }
                else{
                    alert("Found no solution!");
                }
            }
        }
    }
    
    //check if the input are valid
    function check_input(){ 
        var arr = new Array();
    
        for(var i=0; i<81; i++){
            arr[i] = Number(document.getElementsByTagName("input")[i].value);
            if(isNaN(arr[i])){
                alert('Input should be any number between 1 and 9 !');
                return false
            }
        }
    
        if(arr.every(function isZero(x){ return x== 0})){
            alert('There is no input!');
            return false
        }
    
        return true
    }
    
    //read a puzzle from the web page
    function readAPuzzle(){ 
        var arr = new Array();
    
        for(var i=0; i<81; i++){
            arr[i] = Number(document.getElementsByTagName("input")[i].value);
        }
    
        var grid = new Array();
        for(var i=0; i<9; i++){
            grid[i] = new Array();
            for(var j=0; j<9; j++){
                grid[i][j] = 0;
            }    
        }
    
    
        for(var i=0; i<81; i++){
            grid[Math.floor(i/9)][i%9] = arr[i];
        }
    
        return grid
    }
    
    //Obtain a list of free cells from the puzzle
    function getFreeCellList(grid){ 
        var freeCellList = new Array();
        index = 0
    
        for(var i=0; i<9; i++){
            for(var j=0; j<9; j++){
                if(grid[i][j] == 0){
                    freeCellList[index] = new Array(i,j);
                    index++;
                }
            }
        }
    
        return freeCellList
    }
    
    //Check whether grid[i][j] is valid in the grid
    function isValid(i,j,grid){ 
        //Check whether grid[i][j] is valid at the i's row
        for(var column=0; column<9; column++){
            if((column != j) && (grid[i][column] == grid[i][j])){
                return false
            }
        }
    
        //Check whether grid[i][j] is valid at the j's column
        for(var row=0; row<9; row++){
            if((row != i) && (grid[row][j] == grid[i][j])){
                return false
            }
        }
    
        //Check whether grid[i][j] is valid at the 3-by-3 box
        for(var row=Math.floor(i/3)*3; row < Math.floor(i/3)*3+3; row++){
            for(var col=Math.floor(j/3)*3; col < Math.floor(j/3)*3+3; col++){
                if((row != i) && (col != j) && (grid[row][col] == grid[i][j])){
                    return false
                }
            }
        }
    
        return true //The current value at grid[i][j] is valid
    }
    
    //Check whether the fixed cells are valid in the grid
    function isValidGrid(grid){ 
        for(var i=0; i<9; i++){
            for(var j=0; j<9; j++){
                if((grid[i][j] < 0) || (grid[i][j] > 9) || ((grid[i][j] != 0) && (! isValid(i,j,grid)))){
                    return false
                }
            }
        }
        return true
    }
    
    
    //Search for a solution
    function search(grid){ 
        var freeCellList = getFreeCellList(grid);
        var numberOfFreeCells = freeCellList.length;
        if(numberOfFreeCells == 0){
            return true
        }
    
        var k = 0;  //Start from the first free cell
    
        while(true){
            var i = freeCellList[k][0];
            var j = freeCellList[k][1];
            if(grid[i][j] == 0){
                grid[i][j] = 1;
            }
    
            if(isValid(i,j,grid)){
                if(k+1 == numberOfFreeCells){
                    //no more free cells
                    return true  //A solution is found
                }
                else{
                    //Move to the next free cell
                    k++;
                }
            }
            else{
                if(grid[i][j] < 9){
                    //Fill the free cell with the next possible value
                    grid[i][j]++;
                }
    
                else{
                    //grid[i][j] is 9,backtrack
                    while(grid[i][j] == 9){
                        if(k == 0){
                            return false  //No possible value
                        }
                        grid[i][j] = 0;  //Reset to free cell
                        k--;  //Backtrack to the preceding free cell
                        i = freeCellList[k][0];
                        j = freeCellList[k][1];
    
                    } 
                    //Fill the free cell with the next possible value
                    //search continues from this free cell at k
                    grid[i][j]++;
                }
            }
        }
    
        return true  //A solution is found
    }
    
    
    //output the answer on the web page
    function output_ans(){ 
        var grid = readAPuzzle();
        var grid_original = readAPuzzle();
    
        if(search(grid)){
            for(var i=0; i<81; i++){
                if(grid[Math.floor(i/9)][i%9] != grid_original[Math.floor(i/9)][i%9]){
                    document.getElementsByTagName("input")[i].value = grid[Math.floor(i/9)][i%9];
                    document.getElementsByTagName("input")[i].style.color = 'black';
                }
            }
        }
    
    }

我们将对如何操作做一个简单的图解说明。  
  开始的页面如下：

![开始页面][SouthEast]  
  
  首先，如果没有任何输入而直接点击“Show Answer”按钮，则会显示如下页面：  
  
![没有任何输入而直接点击“Show Answer”按钮][Show Answer]  
  
  如何在表格中一旦输入非数字，则会显示如下页面：  
  
![在表格中输入非数字][SouthEast 1]  
  
  若在九宫格中输入的数字不符合规则，则会显示页面如下：  
  
![在九宫格中输入的数字不符合规则][SouthEast 2]  
  
  当我们输入的数字符合规则时，就能得到正确的答案，比如，我们在 [http://www.cn.sudokupuzzle.org/][http_www.cn.sudokupuzzle.org]上随便找一个“骨灰级”的数独并输入，页面如下：  
  
![“骨灰级”的数独][SouthEast 3]  
  
当我们按下“Show Answer”按钮时，显示的答案如下：  
  
![显示答案][SouthEast 4]  
  
  当按下“Clear”按钮时，所有格子将会被清空，这样我们就能就行下一次破解啦~~  
  本次分享到此结束，欢迎大家交流~~  
  P.S.写这个项目主要是为了学习JavaScript,因为最近刚开始接触前端。欢迎大家访问这个项目的Github地址： [https://github.com/percent4/Sudoku-Solver-JavaScript-Version][https_github.com_percent4_Sudoku-Solver-JavaScript-Version] .

[Link 1]: http://blog.csdn.net/jclian91/article/details/79026051
[SouthEast]: /images/20220602/4ef820c3799a4ba999d331d1e79d041c.png
[Show Answer]: /images/20220602/c12127d534384266a4caeda94fbd2ca5.png
[SouthEast 1]: /images/20220602/c399cef8cf4843e7aaaed8e83a37c7ad.png
[SouthEast 2]: /images/20220602/64b96136495e4a4d9fa114a8e7ae72ab.png
[http_www.cn.sudokupuzzle.org]: http://www.cn.sudokupuzzle.org/
[SouthEast 3]: /images/20220602/5cebd02f2df74873a3a46882b4f3b328.png
[SouthEast 4]: /images/20220602/b176afe3589f4c558dc1655cbb375d3f.png
[https_github.com_percent4_Sudoku-Solver-JavaScript-Version]: https://github.com/percent4/Sudoku-Solver-JavaScript-Version