JavaScript之破解数独（附详细代码）-低调大师

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

2018-01-11 638

在上一篇分享中，我们用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';
            }
        }
    }

}

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

首先，如果没有任何输入而直接点击“Show Answer”按钮，则会显示如下页面：

如何在表格中一旦输入非数字，则会显示如下页面：

若在九宫格中输入的数字不符合规则，则会显示页面如下：

当我们输入的数字符合规则时，就能得到正确的答案，比如，我们在 http://www.cn.sudokupuzzle.org/上随便找一个“骨灰级”的数独并输入，页面如下：

当我们按下“Show Answer”按钮时，显示的答案如下：

当按下“Clear”按钮时，所有格子将会被清空，这样我们就能就行下一次破解啦~~
本次分享到此结束，欢迎大家交流~~
P.S.写这个项目主要是为了学习JavaScript,因为最近刚开始接触前端。欢迎大家访问这个项目的Github地址： https://github.com/percent4/Sudoku-Solver-JavaScript-Version .

微信关注我们

原文链接：https://yq.aliyun.com/articles/615251

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

JSON Web Token (JWT)，服务端信息传输安全解决方案。

image JWT介绍 JSON Web Token(JWT)是一种开放标准(RFC 7519)，它定义了一种紧凑独立的基于JSON对象在各方之间安全地传输信息的方式。这些信息可以被验证和信任，因为它是数字签名的。JWTs可以使用一个密钥(HMAC算法)，或使用RSA的公钥/私钥密钥对对信息进行签名。让我们进一步解释这个定义的一些概念。紧凑由于其较小的体积，JWTs可以通过URL、POST参数或HTTP头部参数进行传递，体积小也意味着其传输速度会相当快。独立有效负载包含了所需要的关于用户的所有信息，避免了多次查询数据库的需要。 JWT的应用场景认证这是使用JWT最常见的场景，一旦用户登录后，每个后续的请求都会包含JWT token，允许用户访问该token所允许的路由、服务、资源等。如单点登录是目前广泛使用JWT的一项功能，因为它的开销很小，而且在不同的域名中很容易使用。信息交换 JWT是一种在多方之间传递数据比较好的方式，因为JWT能使用签名，能确保发送者是谁，也可以验证传递过来的的信息是否被篡改。 JWT的结构 JWT由以下三部分组成： Header（头部） Pay...

2018-01-12

672

区块链是一种新型去中心化协议，能安全地存储比特币交易或其他数据，信息不可伪造和篡改，可以自动执行智能合约，无需任何中心化机构的审核。交易既可以是比特币这样的数字货币，也可以是债权、股权、版权等数字资产，区块链技术解决了拜占庭将军问题，大大降低了现实经济的信任成本与会计成本，重新定义了互联网时代的产权制度。 1月9日晚，朋友圈刷屏了徐小平的预言“区块链革命到来，这是一场顺我者昌，逆我者亡的伟大革命”。显然，“区块链革命”的旗帜已经高举在无数创业者的心中了，但是我们应该清楚地认识到任何一个新技术浪潮到来的时候，都伴随着一定的狂热与泡沫，但到头来最终胜出的，还是那些提供了实实在在技术和产品、创造了能够被人类使用价值的人和公司。徐小平说，谈到互联网革命的时候，有所谓“水泥加鼠标”的说法，而只有鼠标没有水泥（实际价值）的公司，没有一个成功的。

2018-01-12

675

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。