用C语言解9×9数独（亲测可用）（思路分析）

数独，相信大家都不陌生，就像这样：

从几年前就喜欢做数独题目，到现在读大学了，今年寒假期间想回归童年——玩数独。玩了好几天，突然拍醒自己！想起我是个程序员……为什么不做点该做的事？

用代码来解数独！！！

用的方法是基本的解数独思路，即按每一行每一列以及所在的九宫格，数字不重复的原则依次进行检索。

#include <stdio.h>
#include <stdbool.h>
#include <windows.h>
#pragma warning(disable:4996);

//读取未完成的数独矩阵
void readMatrix(int array[9][9])
{
	int row, //行
		col; //列
	for (row = 0; row < 9; row++)
	{
		for (col = 0; col < 9; col++)
			scanf(" %1d", &array[row][col]); /****注意%1d及前面是有空格的****/
		getchar();
	}
}

//判断在行和列上有没有重复数字（不重复返回true,重复返回false）
bool RowAndColRepeat(int array[9][9], int row, int col, int num)
{
	int i; //计数
	//判断行上有没有重复的数字
	for (i = 0; i < 9; i++)
		if (array[row][i] == num)
			return false;
	//判断列上有没有重复的数字
	for (i = 0; i < 9; i++)
		if (array[i][col] == num)
			return false;
	return true;
}

//判断位置 属于哪个3x3九宫格 
int getRowOrCol(int num)
{
	if (num < 3)
		return 0;
	else if (num < 6)
		return 3;
	else
		return 6;
}

//判断3x3九宫格内是否有重复的数字（不重复返回true,重复返回false） 
bool BlockRepeat(int array[9][9], int row, int col, int num)
{
	int getRowOrCol(int num); //得到3x3九宫格起始位置的函数原型声明 
	int rowStart, //行号
		colStart, //列号
		i, j; //计数
	rowStart = getRowOrCol(row);
	colStart = getRowOrCol(col);
	for (i = rowStart; i < rowStart + 3; i++)
		for (j = colStart; j < colStart + 3; j++)
			if (array[i][j] == num)
				return false;
	return true;
}

//对数独进行深度检索
void calculation(int array[9][9], int row, int col)
{
	int i, j; //计数 //递归，设置出口：如果行号row超出数组行下标，则退出递归输出答案
	if (row > 8)
	{
		for (i = 0; i < 9; i++)
		{
			for (j = 0; j < 9; j++)
				printf("%d ", array[i][j]);
			printf("\n");
		}
		return;
	}
	//如果array[row][col] == 0即该位置的数未确定
	if (array[row][col] == 0)
	{
		for (i = 1; i < 10; i++)
			//从1至9开始试数 for(i = 1;i < 10;i++)
			//试数方法：分别判断在该位置的行和列上有没有重复数字，再判断在所处的3x3宫格内是否重复
			//如果1至9中有合适的数，则该位置的数为该数，并开始遍历下一个位置
			if (RowAndColRepeat(array, row, col, i) && BlockRepeat(array, row, col, i))
			{
				array[row][col] = i;
				calculation(array, row + (col + 1) / 9, (col + 1) % 9); //当每一行的单元格都遍历过，再进入下一行 
			}
		array[row][col] = 0; //如果没有或不是正确的数，则重置为0
	}
	else
	{	// 如果该位置的数已确定则跳过该位置，遍历下一个位置
		calculation(array, row + (col + 1) / 9, (col + 1) % 9); //当每一行的单元格都遍历过，再进入下一行
	}
}

int main()
{
	int array[9][9];//声明一个9x9数独矩阵
	printf("请输入题目：\n");
	readMatrix(array);//读取数独题目
	printf("\n计算结果：\n");
	calculation(array, 0, 0);//从第一个单元开始深度检索
	system("pause");//暂停窗口，显示结果
	return 0;
}