C++解决数独问题（回溯）

输入一个数独作为9*9的数组，例如输入一个测试数据map[9][9]为：

0 9 0 0 0 0 0 6 0 8 0 1 0 0 0 5 0 9 0 5 0 3 0 4 0 7 0 0 0 8 0 7 0 9 0 0 0 0 0 9 0 8 0 0 0 0 0 6 0 2 0 7 0 0 0 8 0 7 0 5 0 4 0 2 0 5 0 0 0 8 0 7 0 6 0 0 0 0 0 9 0 解决思路为：设定一个count来计数，当count=81的时候，遍历完整个数组，这时可以输出结果； 从左上角的数字开始，如果该数为0，则在这个位置从1开始填，这时检查填入的数字能否填入，1没在第一行中出现，也没在第一列中出现，但是在3*3的格子中出现了，则这个位置变为2；再次检查2是否能填入，同理，发现也不能填入，则变成3，发现3可以填入。 以此类推，可以将第一行填满。当遇到冲突发现不能填数字时，将该位置变成0，再返回上一个数，将其+1；就是这样一个不断试值不断重复迭代，遇到冲突，返回纠错然后再迭代的过程。 代码理解：

void backtrace(int count) 
{
	//如果循环完81个数字，则打印出来
	if (count == 81) 
	{
		cout << "result is:" << endl;
		for (int i = 0; i < 9; ++i) 
		{
			for (int j = 0; j < 9; ++j) 
			{
				cout << map[i][j] << " ";
			}
			cout << endl;
		}
		return;
	}

	int row = count / 9;
	int col = count % 9;
	//如果该位置为0，
	if (map[row][col] == 0) 
	{
		for (int i = 1; i <= 9; ++i) 
		{
			map[row][col] = i;//将1-9填入该位置
			if (isPlace(count)) //判断填入的数时候能够放入
			{
				backtrace(count + 1);//如果可以放入，则对下一个位置进行操作
			}
		}
		map[row][col] = 0;
	}
	//如果该位置不为0，则直接对下个位置的进行操作
	else
	{
		backtrace(count + 1);
	}
}

bool isPlace(int count) 
{
	int row = count / 9;
	int col = count % 9;
	int j;
	//判断填入的数是否在该行
	for (j = 0; j < 9; ++j) 
	{
		if (map[row][j] == map[row][col] && j != col) 
		{
			return false;
		}
	}
	//判断填入的数是否在该列
	for (j = 0; j < 9; ++j) 
	{
		if (map[j][col] == map[row][col] && j != row) 
		{
			return false;
		}
	}
	//判断填入的数是否在3*3的小框中
	int tempRow = row / 3 * 3;
	int tempCol = col / 3 * 3;
	for (j = tempRow; j < tempRow + 3; ++j) 
	{
		for (int k = tempCol; k < tempCol + 3; ++k) 
		
		{
			if (map[j][k] == map[row][col] && j!=row && k!=col) 
			{
				return false;
			}
		}
	}
	return true;
}

输出为：

7 9 3 8 5 1 4 6 2 8 4 1 2 6 7 5 3 9 6 5 2 3 9 4 1 7 8 3 2 8 4 7 6 9 5 1 5 7 4 9 1 8 6 2 3 9 1 6 5 2 3 7 8 4 1 8 9 7 3 5 2 4 6 2 3 5 6 4 9 8 1 7 4 6 7 1 8 2 3 9 5

第一次写blog，如有错误，请多指教！~