[数据结构与算法]DFS算法解决数独问题

DFS算法解决数独问题

一，情景描述

??一天晚自习，看到女朋友在旁边玩数独，便想着不如用个算法帮助她快速通关。毕竟，我想以后能成为一个AI算法工程师，所以现在不管是什么算法，多写点总归是有好处的。
??对于这个程序的功能，我希望它能够从文件夹里读取棋盘，然后运行之后输出完整的棋盘。这样对于不同的棋盘，只要更改一下文件路径，就能输出结果。其实，我想着利用计算机视觉就可以直接输入图片，然后电脑自己处理自己输出。但是奈何大二的自己还对计算机视觉一无所知，就只能手动输入到文本文件中了。

二，最初思路

??最开始，我的思路是1，先将棋盘遍历一遍，获取所有空格位置（横纵坐标），然后将他们放在一个数组里面。2，由于每个空格位置所填的内容是1~9之间的数字，所以对每个空格，从1开始，按照行列和所属九宫格进行三次筛选，删去不可能的数值。3，经过前两步的筛选，就可以锁定每个空格能够填的几个数字。然后利用蛮力法进行一种一种的尝试。
??为了实现这个思路，首先定义数据结构如下：

struct point{
	int x,y;  //表示棋盘的每一格所在行，所在列
	strign maynum="123456789";   //初始设置空格可能所取的值
	int index;   //用来指示具体空格的值
}

如上，设置了这样一个复杂的结构，并定义了一个一维数组 point zero[n];
zero[m] 表示第m+1个空格。则zero[m].x和zero[m].y就能分别表示这个空格在棋盘的第几行第几列，zero[m].string[zero[m].index]; 就能表示这个空格的值。于是，照着这个思路，我完成了最初思路的前面两步，等到最后一步准备蛮力法的时候，发现不知道该如何遍历了。要是硬生生继续写下去，那怕不是要写出个m层循环出来，瞬间失去方向。最终，我还是选择来到CSDN上观摩各位大佬的文章。才学得了DFS算法的思路（上学期学习数据结构，学到图的遍历时，怎么没想到这DFS如今还能派上用场。）

三，最终思路

??最终思路为：先从第一个空格开始，对其调用dfs算法为其赋上一个可能值，如果合法，则对下一个空格调用dfs算法。如果有一个空格所有可能值都不合法，则跳出递归函数返回上一个空格，对其赋值下一个可能值，再重复往后进行，知道能够输出全部完整的棋盘为止。完整代码如下：

#include<iostream>
#include<string>
#include<fstream>

using namespace std;
int dataa[10][10];

//建立二维数组用来存储数独棋盘
void Create()
{
	ifstream infile;
	infile.open("D:\\Visual Studio 2017\\代码项目文件夹\\Project1\\数独3.txt", ios::in);
	if (!infile.is_open())
	{
		cout << "读取文件失败" << endl;
		exit(-1);
	}
	char n[100];    //辅助数组，用于读取文件中的数据 然后转移到二维数组中
	int f = 0;
	while (!infile.eof())    //逐字符读取
		infile >> n[f++];
	f = 0;
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			dataa[i + 1][j + 1] = n[f++] - '0';
	infile.close();
}


int judge(int x, int y, int z)//判断是否有重复的z
{
	for (int j = 1; j < 10; j++) {//横行
		if (dataa[x][j] == z)
			return 0;
	}
	for (int j = 1; j < 10; j++) {//纵行
		if (dataa[j][y] == z)
			return 0;
	}
	int tempx = (x - 1) / 3, tempy = (y - 1) / 3;
	for (int j = 1; j <= 3; j++) {//3*3
		for (int k = 1; k <= 3; k++)
			if (dataa[tempx * 3 + j][tempy * 3 + k] == z)
				return 0;
	}
	return 1;
}
void print()
{
	for (int i = 1; i < 10; i++) {
		cout << " | ";
		for (int j = 1; j < 10; j++)
		{

			cout << dataa[i][j];
			if (j % 3 == 0)    // 1 2 3   4 5 6   7 8 9
			{
				cout << " | ";
			}
		}
		if (i % 3 == 0)
		{
			cout << endl;
			cout << " -------------------";
		}
		cout << endl;
	}
}
void dfs(int x, int y) {
	if (x > 9) {//结束
		print();
		cout << endl;
		return;
	}
	if (dataa[x][y] == 0)    //检测到这是一个空格
	{
		for (int i = 1; i < 10; i++)  //可能值从1开始，一直到9
		{
			if (judge(x, y, i))     //如果这个可能值合法
			{
				dataa[x][y] = i;
				dfs((x + (y + 1) / 10), (y + 1) > 9 ? 1 : (y + 1));   //向下一个空格递归，遍历
			}
		}
		dataa[x][y] = 0;     //如果这个空格的所有可能值填入都不合法，则将该空格清零，然后跳出递归函数，返回上一格
	}
	else
		dfs((x + (y + 1) / 10), (y + 1) > 9 ? 1 : (y + 1));
}
int main()
{
	Create();
	dfs(1, 1);
	return 0;
}

算法总结

??不用设置那么麻烦的数据结构，直接利用dfs算法（前提是对该算法很熟悉并能灵活运用。）算法本身还要利用一个判断可能值是否合法的函数。Judeg函数中，对九宫格的判断不用分成九种情况讨论，要观察空格坐标的特点，直接分析出公式，可以提高时间复杂度，减少代码冗余度。
??同时对dfs进行递归调用时，dfs((x + (y + 1) / 10), (y + 1) > 9 ? 1 : (y + 1));这里的参数设置就很巧妙，利用求模，直接用一个式子就对二维数组进行了遍历，非常的方便。

写在最后

??虽然这次自己的思路没有成功，最后还是借鉴的大佬的算法，但是总归还是有收获的。作为这学期第一个自己主动尝试编写的课程之外的算法，我觉得还是一个挺好的开头的。转眼间，大二这学期已经开学整整四周了，可自己的状态好像还没有完全调整过来。这学期的专业课更难了，时间也更加紧张。面对眼前这条成长为一个优秀的AI算法工程师的道路，我也应该停止空想，真正开始往前大踏步前进。希望每一步都能踩出一个深深的印记！作为这学期在CSDN上的第一篇博客，它将开启全新的《算法设计与分析》这一专栏，希望能够记录下自己学习的点滴。