第一章趣味数独

阅读量：4136 次

发布时间：2019-05-25

本文共 3833 字，大约阅读时间需要 12 分钟。

我一直觉得编程是一件极其有意思的事情，虽然没有特别聪明的头脑，也没有对某领域做过深入研究（其实也不知道要研究哪些领域，老师觉得研究哪个领域都可，要看以后做什么了，不知道这么想对不对，但有一点一定是正确的，那就是打好基础，将基本的数据结构和算法掌握透彻才是现在的王道），但很是着迷于一些算法、密码什么的，我本人不太喜欢看书，所以大部分事情都是在电脑上进行，刷了LeetCode上的150题，并对这些题深入思考，看文章博客，找寻更多地解题路子，然后总结思路代码写博客，又做了些ACM俱乐部的题目，最近这两天又在学习结构之法——算法之道博主的一系列博客，什么程序员面试宝典啊、何海涛面试100题啊什么的，看到有兴趣的就做做，零零散散下来也有不少题目和心得了，但是能力的提升不是靠刷题的多少，更重要的是对数据结构及算法的思考和总结，我一直这么坚信，所以从现在开始，注重细节、注重总结

趣味题更有意思些，更能增加自己对编程的喜爱程度，好玩的事情总是可以反复玩味，那么第一篇文章就先从趣味题开始吧，我特别喜欢数独这个游戏，佩服想出这个游戏的人，那就先从这个游戏开始吧。

去年网上看到一则新闻：

据说这是世界上最难的数独

来源：每日邮报作者： 2012-07-16 09:18

英国《每日邮报》6月30日发表了一篇报道，报道称“芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”

当然我肯定没有能力手动解决这个问题，我只是对它说的只有一个答案充满了好奇，真的只有一个答案？看着不像啊。网上有很多实现数独的方式，刚开始的时候可以学习，但是一定要思考，一定要自己动手实践，这也是我写这篇文章的原因所在

算法思想很简单，深度暴搜，再自己实现一遍，算法思考和加深对递归的理解才是目的，那么就开始吧

1、首先这张图一定要存起来，matrix数组保存，空格用0来代替，数据范围不用考虑，因为所有数据大小都是定的；

2、深搜的一般套路得过一遍，一般都是从第一个位置开始进行，有一记录访问点的数组，避免访问重复，然后上下左右四个方向，将满足要求的点进行递归调用，这道题肯定要用到回溯，还得将访问过的点回溯回来，只要在递归代码后加代码就可以了

3、还有一个问题就是递归的结束条件是什么，怎么来判断数独里的数都已经填上了数字？每次查看matrix数组是否都填上了数字当然行不通，可以以下处理

4、其实我们处理的只是不填数字的位置，将不填数字的位置全部记录下来，统计空格的个数，递归当前状态就是对其中某个位置的处理，结束条件就是所有位置都填上了数字，那么这样的话，我们对所有空位置进行编号，1，2，3 每个位置存储该位置所在的行和列，可以用结构体数组存，也可以用两个一维数组存

5、接下来就是判断位置是否合法，即此位置所在的行列和小九宫格是否已经存在要填的数字，对每个数字都行、列、区域判断感觉复杂度高了一些，可以用数组来记录某行或某列的数字存在状态

想到这感觉差不多了，下面就来实现下，轻车熟路了，希望一次就能运行通过

#include 
        
         using namespace std;#define N 10char 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和图片啥的，代码先贴上：


              
              
           数独计算器

直接复制粘贴，保存html文件用IE打开就可以了，页面如下：

功能不多，刚开始是这个默认的最难数独，也可以自己设定数独，然后按一键生成答案就会出现上面的情况了，

但是，如果要是不满足数独的要求的话会卡死的哦

第一章就先写到这里吧，以后大约每天写一篇吧

王川

2014/02/12

转载地址：http://udvvi.baihongyu.com/

你可能感兴趣的文章

据说这是世界上最难的数独

来源：每日邮报 作者： 2012-07-16 09:18

数独计算器

来源：每日邮报作者： 2012-07-16 09:18