Django之破解数独

数独是一项快乐的益智游戏，起源于18世纪瑞士的一种数学游戏。解答者需要运用纸、笔进行演算，需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。
本次分享讲展示如何利用Django来直观方便地破解数独。
首先新建两个模板来展示页面，一个是index.html，方便用户输入数独，此数独可以来自其他网站；一个是answer.html，用于展示用户输入的数独的答案。
index.html的代码如下：

<html>
    
<head>
{% load staticfiles %}
<link rel="stylesheet" type="text/css" href="{% static 'App/mystyle.css' %}" />
</head>

<body background="{% static 'App/mountain.jpg' %}">
    <center><h1>Solve A Sudoku</h1></center>
    <form action="/answer/" method="get">
    <table class="sd" border="0" align="center" cellspacing="1" cellpadding="1">
        <tr>
            <td class="xx"><input id="1" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="2" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="3" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="4" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="5" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="6" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="7" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="8" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="9" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="10" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="11" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="12" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="13" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="14" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="15" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="16" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="17" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="18" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="19" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="20" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="21" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="22" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="23" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="24" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="25" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="26" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="27" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="top"><input id="28" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="29" class="big" name="grid" maxlength="1"></td>
            <td class="topr"><input id="30" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="31" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="32" class="big" name="grid" maxlength="1"></td>
            <td class="topr"><input id="33" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="34" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="35" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="36" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="37" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="38" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="39" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="40" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="41" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="42" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="43" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="44" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="45" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="46" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="47" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="48" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="49" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="50" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="51" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="52" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="53" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="54" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="top"><input id="55" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="56" class="big" name="grid" maxlength="1"></td>
            <td class="topr"><input id="57" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="58" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="59" class="big" name="grid" maxlength="1"></td>
            <td class="topr"><input id="60" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="61" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="52" class="big" name="grid" maxlength="1"></td>
            <td class="top"><input id="63" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="64" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="65" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="66" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="67" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="68" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="69" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="70" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="71" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="72" class="big" name="grid" maxlength="1"></td>
        </tr>
        <tr>
            <td class="xx"><input id="73" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="74" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="75" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="76" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="77" class="big" name="grid" maxlength="1"></td>
            <td class="rr"><input id="78" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="79" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="80" class="big" name="grid" maxlength="1"></td>
            <td class="xx"><input id="81" class="big" name="grid" maxlength="1"></td>
        </tr>
    </table>
    <br>
    <center>
    <button type="reset" value="Reset">Reset</button>
    <input type="submit" value="Show Anwser"> 
    </center>
    </form>
</body>

</html>

answer.html的代码如下：

<html>

<head>
{% load staticfiles %}
<link rel="stylesheet" type="text/css" href="{% static 'App/mystyle.css' %}" />
</head>

<body background="{% static 'App/sky.jpg' %}">
    <center><h1>{{info}}</h1>
    {% ifequal info 'The solution is found:'%}
    <script>
        var mat = {{grid|safe}};
        var mat_orig = {{grid_orig|safe}};
        var i,j;
        document.write('<table class="sd" border="0" align="center" cellspacing="1" cellpadding="1">');
        for(i=0;i<9;i++){
            document.write('<tr>');
            if (i != 3 && i != 6){
                for(j=0;j<9;j++){
                    if(j ==2 || j ==5){
                        if(mat[i][j] == mat_orig[i][j]){
                            document.write('<td class="rr"><font color="blue" size="5">'+mat[i][j]+'</font</td>');
                        }
                        else{
                            document.write('<td class="rr">'+mat[i][j]+'</td>');
                        }
                    }
                    else{
                        if(mat[i][j] == mat_orig[i][j]){
                            document.write('<td class="xx"><font color="blue" size="5">'+mat[i][j]+'</font</td>');
                        }
                        else{
                            document.write('<td class="xx">'+mat[i][j]+'</td>');
                        }
                    }
                }
            }
            else{
                for(j=0;j<9;j++){
                    if(j ==2 || j ==5){
                        if(mat[i][j] == mat_orig[i][j]){
                            document.write('<td class="topr"><font color="blue" size="5">'+mat[i][j]+'</font</td>');
                        }
                        else{
                            document.write('<td class="topr">'+mat[i][j]+'</td>');
                        }
                    }
                    else{
                        if(mat[i][j] == mat_orig[i][j]){
                            document.write('<td class="top"><font color="blue" size="5">'+mat[i][j]+'</font</td>');
                        }
                        else{
                            document.write('<td class="top">'+mat[i][j]+'</td>');
                        }
                    }
                }
            }
            document.write('</tr>');
        }
    </script>
    {% endifequal %}
    <button onclick="window.location.href='http://localhost:8000/index'">Return</button>
    <br><br>
    </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;
}

在views.py中，获取从前端index.html输入的数字信息，并进行数独的破解，再将破解后的答案输出到answer.html.其中，views.py的代码如下：

import json
from django.http import HttpResponse
from django.shortcuts import render_to_response

def index(request):
    return render_to_response('index.html')

#Read a Sudoku puzzle from the web page
def readAPuzzle(lst):
    grid=[]
    for i in range(9):
        grid.append(lst[9*i:9*(i+1)])
 
    return grid
 
#Obtain a list of free cells from the puzzle
def getFreeCellList(grid):
    freeCellList=[]
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                freeCellList.append([i,j])
 
    return freeCellList

#Search for a solution
def search(grid):
    freeCellList=getFreeCellList(grid)
    numberOfFreeCells=len(freeCellList)
    if numberOfFreeCells == 0:
        return True
     
    k=0  #Start from the first free cell
 
    while True:
        i=freeCellList[k][0]
        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 += 1
        elif grid[i][j] < 9:
            #Fill the free cell with the next possible value
            grid[i][j] += 1
        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 -= 1  #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] += 1
 
    return True  #A solution is found
 
#Check whether grid[i][j] is valid in the grid
def isValid(i,j,grid):
    #Check whether grid[i][j] is valid at the i's row
    for column in range(9):
        if column != j and grid[i][column] == grid[i][j]:
            return False
         
    #Check whether grid[i][j] is valid at the j's column
    for row in range(9):
        if row != i and grid[row][j] == grid[i][j]:
            return False
 
    #Check whether grid[i][j] is valid at the 3-by-3 box
    for row in range((i//3)*3,(i//3)*3+3):
        for col in range((j//3)*3,(j//3)*3+3):
            if row != i and col != j and 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
def isValidGrid(grid):
    for i in range(9):
        for j in range(9):
            if grid[i][j] not in range(10) or (grid[i][j] in range(1,10) and not isValid(i,j,grid)):
                return False
    return True

def answer(request):
    #Get input from the index.html page
    get_lst = request.REQUEST.getlist("grid")
    #original grid to store the input numbers, replace empty string with 0
    grid_orig = readAPuzzle(lst = [int(_) if _ else 0 for _ in get_lst])
    #the grid that store a answer with latter processing
    grid = readAPuzzle(lst = [int(_) if _ else 0 for _ in get_lst])
    
    #information to output
    info = ""
    if not isValidGrid(grid):
        info = "Invalid input"
    elif search(grid):
        info = "The solution is found:"
    else:
        info = "No solution!"
    return render_to_response('answer.html',{'grid_orig':json.dumps(grid_orig),'grid':json.dumps(grid),'info':info})

启动该Django项目的服务，在浏览器中输入'localhost:8000/index'，页面如下：

用户输入界面

我们在http://www.sudoku-cn.com/中随便找一个难度为‘高级+’的数独游戏，将其输入到index.html页面中，如下：

数独游戏

按下"Show Answer"按钮，不用1秒，答案就出来了，如下所示：

显示答案

在该页面中，按下"Return"按钮可回到原先的输入页面。
怎么样？这样的数独破解程序是不是酷酷的？欢迎访问该项目的Github地址：https://github.com/percent4/Sudoku-Solver .
本次分享到此结束，欢迎大家交流~~

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350

Django之破解数独

推荐阅读更多精彩内容