题解 | #Sudoku#

#include <stdio.h>
#include <string.h>
#define LEN 9

int DFS(int map[][LEN], int pos, int (*popen)[2], int count);
int islegal(int map[][LEN], int x, int y, int num);

int main()
{
	int map[LEN][LEN];
	int pos = 0;
	int i, j; 
	int count = 0;
	int open[LEN * LEN][2]; 
	
	/* 读入数据并记录空位 */ 
	for (i = 0; i < LEN; i++)
	{
		for (j = 0; j < LEN; j++)
		{
			scanf("%d", &map[i][j]);
			if (!map[i][j])
			{
				open[count][0] = i;
				open[count++][1] = j;
			}
		}
	}
	/* 深度优先遍历 */ 
	if (DFS(map, pos, open, count))
	{
		putchar('\n') ;
		for (i = 0; i < LEN; i++)
		{
			for (j = 0; j < LEN; j++)
				printf("%d ", map[i][j]);
			printf("\n");
		}
	}
	
	return 0;
}

/* pos 给第 pos个缺位匹配数值 pos 0 ~ count - 1。 DFS 本质就是穷举，找到一条成功的
路线之后不断返回上一层，return true,return true...,直到最上面一层，不需要要所有情况
都成功，只需要一条成功则达到目的。而所谓回溯实质上是退回对某个地址的值的改变。回溯与
否看会不会对其他路线造成影响，若会，则消除改变（如对数组和指针进行操作，则会改变该地
址的值），否则，则可不必回溯（如参数只是一个复制）。此外DFS不是多线程，所有路线是一次
一次尝试的，尝试到成功则停止，类似于树的遍历算法，也就意味着后面的操作可能会受到前面操
作的影响（例如改变了数组的值会对后面的计算判断造成影响，此时请务必回溯。*/ 
int DFS(int map[][LEN], int pos, int (*popen)[2], int count)
{
	int x, y;
	int i;
	
	if (pos == count) /* 递归出口，填满了 */ 
		return 1;
	x = popen[pos][0];
	y = popen[pos][1];
	/* 尝试填入数字 */ 
	for (i = 1; i <= 9; i++)
	{
		if (islegal(map, x, y, i))
		{
			map[x][y] = i;
			if (DFS(map, pos + 1, popen, count))
		    	return 1;
		    /* 回溯，目的是不对之后合法性计算造成影响，此处传递的是地址，故类似于全局变量 */ 
		    map[x][y] = 0;
		}
	}
	
	return 0;
}

int islegal(int map[][LEN], int x, int y, int num)
{
	int ret = 1;
	int cx, cy;
	int i, j; 
	
	/* 判断填入行是否合法 */ 
	for (i = 0; i < LEN; i++)
	{
		if (i != x && num == map[i][y])
			return 0; 
	}
	/* 判断填入列是否合法 */ 
	for (j = 0; j < LEN; j++)
	{
		if (j != y && num == map[x][j])
			return 0;
	}
	/* 判断所在九宫格是否合法 */ 
	cx = x / 3;
	cy = y / 3;
	for (i = cx * 3; i < cx * 3 + 3; i++)
	{
		for (j = cy * 3; j < cy * 3 + 3; j++)
		{
			if ((i != x || j != y) && num == map[i][j])
				return 0;
		}
	}
	
	return ret;
}