不规则数独的计算机求解

不了解数独的请看：数独分类

在规则数独的计算机求解一文中，我给出了用于求解任何规则数独的代码。

本文，我将对代码进行修改，得到可以用于求解任何不规则数独的代码。

不规则数独和规则数独的区别，在于划分9个区的方式不同，规则数独是9个3*3的正方形区，而不规则数独的分区各种各样的。

只需要用1个数组par记录如何分区，即可求解不规则数独。

代码：

#include<iostream>
using namespace std;

int list[10][10];
int par[10][10];		//par[i][j]=n
int anti[10][10];		//anti[n][?]=i*10+j;

void init()
{
	cout << "<em>输入数字，没有数字的用0代替</em>" << endl;
	char c;
	for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)
	{
		cin >> c;
		list[i][j] = c - '0';
	}
	cout << "<em>输入每个格子属于哪一块（1-9）</em>" << endl;
	for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)anti[i][j] = 0;
	for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)
	{
		cin >> c;
		par[i][j] = c - '0';
		for (int k = 1; k < 10; k++)if (anti[par[i][j]][k] == 0)
		{
			anti[par[i][j]][k] = i * 10 + j;
			break;
		}
	}
}

bool ok(int i, int j, int k)
{
	for (int jj = 1; jj < 10; jj++)if (list[i][jj] == k)return false;
	for (int ii = 1; ii < 10; ii++)if (list[ii][j] == k)return false;
	int p = par[i][j];
	for (int ii = 1; ii < 10; ii++)
		if (list[anti[p][ii] / 10][anti[p][ii] % 10] == k)return false;
	return true;
}

bool trys(int i, int j)
{
	if (j == 10)
	{
		i++;
		j = 1;
	}
	if (i == 10)return true;
	if (list[i][j])return trys(i, j + 1);
	for (int k = 1; k < 10; k++)
	{
		if (ok(i, j, k))
		{
			list[i][j] = k;
			if (trys(i, j + 1))return true;
		}
	}
	list[i][j] = 0;
	return false;
}

void out()
{
	for (int i = 1; i < 10; i++)
	{
		for (int j = 1; j < 9; j++)cout << list[i][j] << " ";
		cout << list[i][9] << endl;
	}
}

int main()
{
	init();
	trys(1, 1);
	out();
	system("pause>nul");
	return 0;
}

在ok函数中，由任何一个格子的坐标，需要直接得到其他所有格子的坐标，所以需要一个数组anti将par反过来记录。

其实不用这个数组也行，大不了在ok里面做一个搜索，搜索81个格子，根据par值判断是否在一个区。

这样做，代码稍微简单一点点，虽然复杂度是一样的，但是时间肯定慢一些。

上面的代码，对于任何不规则数独，应该都能在2秒之内输出答案。

用法示例：

对于这个数独，将空格全部补0：

030159080
209000603
007803400
900040005
706000108
300090006
002907500
501000802
070516020

然后，将9个区编号1-9：

然后同样的变成9*9的方阵：

122333444
122333444
122233444
125253666
115555566
111859596
777889996
777888996
777888996

将这2个9*9的方阵输入程序即可得到答案：

所以答案是：