天天看點
傳回

第一章 趣味數獨據說這是世界上最難的數獨

    我一直覺得程式設計是一件極其有意思的事情，雖然沒有特别聰明的頭腦，也沒有對某領域做過深入研究（其實也不知道要研究哪些領域，老師覺得研究哪個領域都可，要看以後做什麼了，不知道這麼想對不對，但有一點一定是正确的，那就是打好基礎，将基本的資料結構和算法掌握透徹才是現在的王道），但很是着迷于一些算法、密碼什麼的，我本人不太喜歡看書，是以大部分事情都是在電腦上進行，刷了LeetCode上的150題，并對這些題深入思考，看文章部落格，找尋更多地解題路子，然後總結思路代碼寫部落格，又做了些ACM俱樂部的題目，最近這兩天又在學習結構之法——算法之道部落客的一系列部落格，什麼程式員面試寶典啊、何海濤面試100題啊什麼的，看到有興趣的就做做，零零散散下來也有不少題目和心得了，但是能力的提升不是靠刷題的多少，更重要的是對資料結構及算法的思考和總結，我一直這麼堅信，是以從現在開始，注重細節、注重總結     趣味題更有意思些，更能增加自己對程式設計的喜愛程度，好玩的事情總是可以反複玩味，那麼第一篇文章就先從趣味題開始吧，我特别喜歡數獨這個遊戲，佩服想出這個遊戲的人，那就先從這個遊戲開始吧。     去年網上看到一則新聞：

據說這是世界上最難的數獨

來源：每日郵報  作者：  2012-07-16 09:18

第一章 趣味數獨據說這是世界上最難的數獨

英國《每日郵報》6月30日發表了一篇報道，報道稱“芬蘭數學家因卡拉花費3個月設計出了世界上迄今難度最大的數獨遊戲，而且它隻有一個答案。因卡拉說隻有思考能力最快、頭腦最聰明的人才能破解這個遊戲。”     當然我肯定沒有能力手動解決這個問題，我隻是對它說的隻有一個答案充滿了好奇，真的隻有一個答案？看着不像啊。網上有很多實作數獨的方式，剛開始的時候可以學習，但是一定要思考，一定要自己動手實踐，這也是我寫這篇文章的原因所在     算法思想很簡單，深度暴搜，再自己實作一遍，算法思考和加深對遞歸的了解才是目的，那麼就開始吧 1、首先這張圖一定要存起來，matrix數組儲存，空格用0來代替，資料範圍不用考慮，因為所有資料大小都是定的； 2、深搜的一般套路得過一遍，一般都是從第一個位置開始進行，有一記錄通路點的數組，避免通路重複，然後上下左右四個方向，将滿足要求的點進行遞歸調用，這道題肯定要用到回溯，還得将通路過的點回溯回來，隻要在遞歸代碼後加代碼就可以了 3、還有一個問題就是遞歸的結束條件是什麼，怎麼來判斷數獨裡的數都已經填上了數字？每次檢視matrix數組是否都填上了數字當然行不通，可以以下處理 4、其實我們處理的隻是不填數字的位置，将不填數字的位置全部記錄下來，統計空格的個數，遞歸目前狀态就是對其中某個位置的處理，結束條件就是所有位置都填上了數字，那麼這樣的話，我們對所有空位置進行編号，1，2，3 每個位置存儲該位置所在的行和列，可以用結構體數組存，也可以用兩個一維數組存 5、接下來就是判斷位置是否合法，即此位置所在的行列和小九宮格是否已經存在要填的數字，對每個數字都行、列、區域判斷感覺複雜度高了一些，可以用數組來記錄某行或某列的數字存在狀态 想到這感覺差不多了，下面就來實作下，輕車熟路了，希望一次就能運作通過

#include <iostream>
using namespace std;

#define N 10
char m;
int n;
int matrix[][N]={//為了處理友善，将0行0列忽略
	{0,0,0,0,0,0,0,0,0,0},
	{0,8,0,0,0,0,0,0,0,0},
	{0,0,0,3,6,0,0,0,0,0},
	{0,0,7,0,0,9,0,2,0,0},
	{0,0,5,0,0,0,7,0,0,0},
	{0,0,0,0,0,4,5,7,0,0},
	{0,0,0,0,1,0,0,0,3,0},
	{0,0,0,1,0,0,0,0,6,8},
	{0,0,0,8,5,0,0,0,1,0},
	{0,0,9,0,0,0,0,4,0,0}
};
const int board[N][N]={//判斷第i行第j列是第幾個九宮格
	{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9}
};
bool r[N][N];//r[i][j]表示第i行是否已經有j了
bool c[N][N];//c[i][j]表示第i列是否已經有j了
bool s[N][N];//s[i][j]表示第i個九宮格中是否已經有j了
int counts, p[N*N], q[N*N];//counts記錄的是一共有多少個格子沒有填數字，
							//p數組記錄他們的行序号，q數組記錄他們的列序号

void Initial();
void DFS(int cur);
void Print();

int main()
{
	Initial();//初始化
	
	DFS(1);
	return 0;
}

void Initial(){
	counts = 0;
	memset(r,false,sizeof(r));
	memset(c,false,sizeof(r));
	memset(s,false,sizeof(r));
	for(int i = 1; i <= 9; i++)
	{
		for(int j = 1; j <= 9; j++)
		{
			if(matrix[i][j] != 0)
			{
				r[i][matrix[i][j]] = true;
				c[j][matrix[i][j]] = true;
				s[board[i][j]][matrix[i][j]] = true;
			}
			else//記錄沒有填數字的格子
			{
				counts++;
				p[counts] = i;
				q[counts] = j;
			}
		}
	}
}

void DFS(int cur)
{
	if(cur == counts + 1)
	{
		Print();
		return ;
	}
	for(int i = 1; i <= 9; i++)//p[cur]表示未填數字的格子的行序号，q[cur]表示未填數字的格子的列序号
	{
		if(r[p[cur]][i] == false && c[q[cur]][i] == false && s[board[p[cur]][q[cur]]][i] == false)
		{
			matrix[p[cur]][q[cur]] = i;
			r[p[cur]][i] = true;
			c[q[cur]][i] = true;
			s[board[p[cur]][q[cur]]][i] = true;
			DFS(cur + 1);
			r[p[cur]][i] = false;
			c[q[cur]][i] = false;
			s[board[p[cur]][q[cur]]][i] = false;
		}
	}
}

void Print()
{
	for(int i = 1; i <= 9; i++)
	{
		for(int j = 1; j <= 9; j++)
			cout << matrix[i][j];
		cout << endl;
	}
}

發現果然就隻有一個解啊，數學家就是牛 但是，既然數獨是一款遊戲，遊戲具有一定的可玩性，以上程式可不具備操作性，幸好我這兩年對網站比較感興趣，在學校裡做過一些網站，對javascript、css還是想對熟悉的，廢話不多說，趕緊做一款簡單的網頁遊戲，就先從這個“一鍵生成答案”的“數獨電腦”開始，嘻嘻 既然是網頁，那就稍微做的好看些，多動用些css，還得要簡單，貼上去的代碼可以直接複制粘貼，打開就能用，那就隻能一個頁面搞定，不能用jquery和圖檔啥的，代碼先貼上：

<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
    <title></title>
<style type="text/css">
body,div,h2,ul,li{margin:0;padding:0;}
body{font:12px/1.5 Arail;}
.box{width:860px;margin:10px auto;background:#eee;border:1px solid #b8b8b8;overflow:hidden}
.title{height:30px;line-height:30px;font-size:14px;padding:0 15px 0 35px;border-bottom:1px solid #b8b8b8;background:#fafafa url(http://js.alixixi.com/img/mm/ico.gif) 5px 50% no-repeat;}
.title span{float:left;}
.title a{float:right;color:#06f;outline:none;}
.title a:hover{color:red;}
    .box .tool {
        width:200px;
        float:left;
    }
    .box .content {
        width:480px;
        margin-left:210px;
    }
    .tool div {
        margin:10px auto;
        height:40px;
        text-align:center;
    }
    .content td {
        width:50px;
        height:50px;
        font-size:xx-large;
        line-height:50px;
        border:1px solid #c3c3c3;
        background:#fff;
        text-align:center;
    }

</style>
<script type="text/javascript">
    //一些常量
    
    var matrix = [//原始數組
        [8, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 3, 6, 0, 0, 0, 0, 0],
        [0, 7, 0, 0, 9, 0, 2, 0, 0],
        [0, 5, 0, 0, 0, 7, 0, 0, 0],
        [0, 0, 0, 0, 4, 5, 7, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 3, 0],
        [0, 0, 1, 0, 0, 0, 0, 6, 8],
        [0, 0, 8, 5, 0, 0, 0, 1, 0],
        [0, 9, 0, 0, 0, 0, 4, 0, 0]
    ];
    var board = [
        [1, 1, 1, 2, 2, 2, 3, 3, 3],
        [1, 1, 1, 2, 2, 2, 3, 3, 3],
        [1, 1, 1, 2, 2, 2, 3, 3, 3],
        [4, 4, 4, 5, 5, 5, 6, 6, 6],
        [4, 4, 4, 5, 5, 5, 6, 6, 6],
        [4, 4, 4, 5, 5, 5, 6, 6, 6],
        [7, 7, 7, 8, 8, 8, 9, 9, 9],
        [7, 7, 7, 8, 8, 8, 9, 9, 9],
        [7, 7, 7, 8, 8, 8, 9, 9, 9]
    ];
    var N = 10;
</script>
<script type="text/javascript">
    //一些公共函數
    //擷取ID
    var $ = function (id) { return typeof id === "string" ? document.getElementById(id) : id };
    //擷取tagName
    var $$ = function (tagName, oParent) { return (oParent || document).getElementsByTagName(tagName) };
    //擷取class
    var $$$ = function (sClass, oParent) {
        var aClass = [],
        i = 0,
        reClass = new RegExp("(\\s|^)" + sClass + "($|\\s)"),
        aElement = $$("*", oParent);
        for (i = 0; i < aElement.length; i++) reClass.test(aElement[i].className) && aClass.push(aElement[i]);
        return aClass
    };
    //擷取元素位置
    function getPos(obj) {
        var iTop = obj.offsetTop;
        var iLeft = obj.offsetLeft;
        while (obj.offsetParent) {
            iTop += obj.offsetParent.offsetTop;
            iLeft += obj.offsetParent.offsetLeft;
            obj = obj.offsetParent;
        }
        return { top: iTop, left: iLeft }
    };

</script>
<script type="text/javascript">
    //建立數獨對象
    var Sudoku = function () { this.initialize.apply(this, arguments) };
    Sudoku.prototype = {
        initMatrix: function (matrix,Data) {
            
            for (var i = 0; i < 9; i++) {
                matrix[i] = new Array(N);
                for (var j = 0; j < 9; j++) {
                    matrix[i][j] = Data[i][j];
                }
            }
        },
        initArray: function (Data) {
            for (var i = 0; i < N; i++) Data[i] = new Array(N);
        },
        initialize: function (obj ,Data) {
            var oThis = this;
            this.Parent = $(obj);//獲得table對象
            this.Table = $$("table", this.Parent)[0];
            this.ButtonA = $$$("answer", this.Parent)[0];
            this.ButtonB = $$$("restore", this.Parent)[0];
            this.ButtonC = $$$("clear", this.Parent)[0];

            this.matrix = new Array(N);//存放數獨矩陣
            this.Td = [];//table中的所有td列矩陣

            this.r = new Array(N);//r[i][j]表示第i行是否已經有j了
            this.c = new Array(N);//c[i][j]表示第i列是否已經有j了
            this.s = new Array(N);//s[i][j]表示第i個九宮格中是否已經有j了
            this.counts = 0;
            this.p = new Array(N * N);
            this.q = new Array(N * N);

            this.initMatrix(this.matrix, Data);
            this.initArray(this.r);
            this.initArray(this.c);
            this.initArray(this.s);

            this.dom = document.documentElement || document.body;
            this.ButtonA.onclick = function () {
                oThis.answer();
            }
            this.ButtonB.onclick = function () {
                for (var i = 0; i < 9; i++)
                    for (var j = 0; j < 9; j++) {
                        oThis.matrix[i][j] = Data[i][j];
                        if (Data[i][j] != 0) oThis.Td[i][j].innerText = Data[i][j];
                        else oThis.Td[i][j].innerText = "";
                    }
            }
            this.ButtonC.onclick = function () {
                oThis.clear();
            }
            this.create(Data);
        },
        create: function (Data) {
            var oThis = this;
            var aFrag = document.createDocumentFragment();
            var i = 0, j = 0;
            for (i = 0; i < 9; i++) {
                var tr = document.createElement("tr");
                oThis.Td.push([]);
                for (j = 0; j < 9; j++) {
                    var td = document.createElement("td");
                    if (Data[i][j] != 0) td.innerText = Data[i][j];
                    oThis.Td[i].push(td);
                    
                    tr.appendChild(td);
                }
                aFrag.appendChild(tr);
            }
            this.Table.appendChild(aFrag);
            this.select();
        },
        clear: function () {
            for (var i = 0; i < 9; i++) {
                for (var j = 0; j < 9; j++) {
                    this.Td[i][j].style.background = "#fff";
                    this.Td[i][j].innerText = "";
                    this.matrix[i][j] = 0;
                }
            }
        },
        renewTd: function () {
            for (var i = 0; i < 9; i++) {
                for (var j = 0; j < 9; j++) {
                    this.Td[i][j].style.background = "#fff";
                }
            }
        },
        getNumber:function(){
            var event = event || window.event;
            alert(event.keyCode);
        },
        select: function () {
            var oThis = this;
            for (var i = 0; i < 9; i++) {
                for (var j = 0; j < 9; j++) {
                    this.Td[i][j].onclick = function () {
                        oThis.renewTd();
                        this.style.background = "#06f";
                        this.onkeypress = function () {
                            var event = event || window.event;
                            if (49 <= event.keyCode && event.keyCode <= 57) {
                                this.innerText = event.keyCode - 48;
                                for (var i = 0; i < 9; i++) {
                                    for (var j = 0; j < 9; j++) {
                                        if (this == oThis.Td[i][j]) {
                                            oThis.matrix[i][j] = event.keyCode - 48;
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        },
        memset:function(Data,k){
            for(var i=0;i<N;i++)for(var j=0;j<N;j++)Data[i][j]=k;
        },
        initData: function () {
            this.counts = 0;  
            this.memset(this.r,0);  
            this.memset(this.c,0);  
            this.memset(this.s,0);  
            for(var i = 0; i < 9; i++)  
            {  
                for(var j = 0; j < 9; j++)  
                {  
                    if(this.matrix[i][j] != 0)  
                    {  
                        this.r[i][this.matrix[i][j]] = true;  
                        this.c[j][this.matrix[i][j]] = true;  
                        this.s[board[i][j]][this.matrix[i][j]] = true;  
                    }  
                    else//記錄沒有填數字的格子  
                    {  
                        this.counts++;  
                        this.p[this.counts] = i;  
                        this.q[this.counts] = j;  
                    }  
                }  
            }  
        },
        Print:function(){
            for (var i = 0; i < 9; i++) {
                for (var j = 0; j < 9; j++)
                    this.Td[i][j].innerText = this.matrix[i][j];
            }
        },
        DFS: function (cur) {
             if(cur == this.counts + 1)  
            {  
                this.Print();  
                return true;  
            }  
            for(var i = 1; i <= 9; i++)//p[cur]表示未填數字的格子的行序号，q[cur]表示未填數字的格子的列序号  
            {  
                if(this.r[this.p[cur]][i] == false && this.c[this.q[cur]][i] == false && this.s[board[this.p[cur]][this.q[cur]]][i] == false)  
                {  
                    this.matrix[this.p[cur]][this.q[cur]] = i;  
                    this.r[this.p[cur]][i] = true;  
                    this.c[this.q[cur]][i] = true;  
                    this.s[board[this.p[cur]][this.q[cur]]][i] = true;  
                    if(this.DFS(cur + 1))return true;  
                    this.r[this.p[cur]][i] = false;  
                    this.c[this.q[cur]][i] = false;  
                    this.s[board[this.p[cur]][this.q[cur]]][i] = false;  
                }  
            }
            return false;
        },
        answer: function () {
            this.initData();
            this.DFS(1);
        }
    };
    window.onload = function () {
        var Box = $$$("box");
        //建立執行個體
        new Sudoku(Box[0], matrix);
    };
</script>
</head>
<body>
<div class="box">
    <h2 class="title"><span>數獨電腦</span></h2>

    <div class="tool">
        <div><button class="answer">一鍵生成答案</button></div>
        <div><button class="restore">還原數獨</button></div>
        <div><button class="clear">清空數獨</button></div>
    </div>

    <div class="content">
        <table class="sudoku">
            
        </table>
    </div>
</div>

</body>
</html>

直接複制粘貼，儲存html檔案用IE打開就可以了，頁面如下：

第一章 趣味數獨據說這是世界上最難的數獨
第一章 趣味數獨據說這是世界上最難的數獨

功能不多，剛開始是這個預設的最難數獨，也可以自己設定數獨，然後按一鍵生成答案就會出現上面的情況了， 但是，如果要是不滿足數獨的要求的話會卡死的哦 第一章就先寫到這裡吧，以後大約每天寫一篇吧 王川 2014/02/12

程式員之路
上一篇: 15年12月C200，自動2.0T，天窗，多功能方向盤，倒車影像，價格便宜，支援0首付#高成本效益二手車推薦#看得見的高品
下一篇: filter,map,reduce函數

繼續閱讀