puzzle（0112）不规则数独、变种数独
。。
目录
一，不规则数独
1，规则
没有分9个宫，而是用特定的线分成9个区，其他规则和标准数独一样。
2，对称性
在我做过的这些不规则数独里面，居然全部有着对称性！
有的是格子有对称性，有的是数字有对称性，还有的是格子和数字都有对称性。
对称性又分很多很多种。
含正方形的不规则数独
这5个不规则数独，正中间都是正方形，而且里面给出的数字都是对称分布的。
具体说来
图一的格子是中心对称的，数字几乎是中心对称的。
图二的格子和数字都是左右对称的
下面一行的三个图，格子和数字都是中心对称的
这个图有2个正方形，也是格子和数字都是中心对称的。
这个图有3个正方形，格子是关于主对角线对称的，而数字是关于2条对角线都对称的。
中心对称的不规则数独
不规则数独有很多很多都是格子成中心对称的，比如下面这个：
然而更可怕的是，有的数独在此基础上，数字的位置也有着规律。
这3个数独，数字也是成中心对称的
这2个数独还是挺像的，而且，数字的位置，都是关于2个对角线对称的。
关于2个对角线对称是中心对称里面的一种，比一般的中心对称更具有对称美。
这3个数独，数字都是90°旋转对称。
90°旋转对称是中心对称里面的一种，比一般的中心对称更具有对称美。
这3个数独，一看就是非常非常对称，上下对称，左右对称，对角线对称，90度旋转对称
其他对称不规则数独
格子是关于副对角线对称的，而数字是上下对称而且左右对称
格子是左右对称的
格子是左右对称的，而数字是关于副对角线对称的。
格子是关于副对角线对称的，而数字是左右对称的。
3，计算机求解
前面我给出了用于求解任何规则数独的代码，这里我将对代码进行修改，得到可以用于求解任何不规则数独的代码。
不规则数独和规则数独的区别，在于划分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 << "输入数字，没有数字的用0代替" << 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 << "输入每个格子属于哪一块（1-9）" << 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的方阵输入程序即可得到答案：
所以答案是：
二，变种数独
1，规则
变种数独是在规则数独的基础之上，加一点点特殊的规则。
这些规则，有的也可以加在不规则数独之上，不过比较少见。
因为多了一些约束，所以相对来说，一般来说给出的数字比较少。
变种数独里面，有很多都是规定一些大小为9的区域，这些区域里面都是1到9的数字。
2，对角线数独
在规则数独的基础上，还要满足2条对角线也是1到9
比如这个：
除了很对称之外，好像没什么特点。
但是，这个数独很特殊，要自己去解才能体会。
在解这个数独的时候，你会感觉，这个数独几乎有一套独特的推理规则，
规则数独常用的方法在这里很不好用。
规则数独，用行唯一性、列唯一性是最多的。
而这个数独，行唯一性、列唯一性用的很少，反而对角线用的很多很多！
然而，比对角线用的更多的，是一个奇特的规律，仅对本数独有效！
这个规律我不明说，在下面的答案我用图画出来
对角线的规则可以叠加在其他变种数独之上，比如窗口数独，
也可以叠加在不规则数独之上。
3个奇特的数独：
这3个数独，一看就都有着较强的对称性。
然而，不仅是对称性，任何2个数字之间的曼哈顿距离都是偶数！
也就是说，如果把数独按照如下方式染色的话
这3个数独的所有数字都会被黑格子盖住！
他们的解分别是：
第一个数独很难，第二个数独难度普通，第三个数独很简单。
他们给出的初始数字分别有24、28、24个，但是因为结构差异很大，所以难度差别大。
这3个数独，共性很明显，却又都有着很独特的结构，解法截然不同，
而且都和普通的规则数独解法不太像，这些，只有自己去解才能体会的到！
3，窗口数独
在规则数独的基础上，还要满足4个灰色的宫也是1到9
答案：
4，超级窗口数独
在规则数独的基础上，还有9个块也都是1到9
约束比较多，答案：
5，奇偶数独
变种数独里面，还有各种奇偶数独，就是标出特定的区域必须是奇数或者必须是偶数。
情人节趣味数独
情人节趣味数独这个是奇偶数独的一种。
这个趣味数独的规则和规则数独差不多，只是标出了16个格子必须是偶数。
求解的过程也很有趣：
到这个时候，奇数全部填完了，偶数还没开始填（除了最开始本来就给了的）
不是我刻意而为之，而是按照正常的思路来求解，就会出现这一幕。
接下来就十分简单了。
实际上，到了这一步，规则就已经退化了。
因为奇数已经填完了，所以剩下的自然全部是偶数，所以现在这个数独的规则已经和规则数独一样了。
6，摆造型的数独
年字数独
这个就是对角线数独了。
对于对角线数独，一般来说，对角线是最好填的。
这很好理解，因为对角线的格子所拥有的约束较多，所以更容易确定数字。
到了这个时候，对角线上的数字已经全部给出，现在这个数独已经和规则数独没有区别了。
京字数独
这个数独，很明显不可能是对角线数独，因为副对角线上面已经也2个2了。
所以图片中写的是错的，可能是数字写错了，所以这个只能按照规则数独去解。
答案：
7，连续数独
连续数独是，在规则数独的基础上，多了一个规则：
相邻两格内数字之差为1的两格间标出粗线，相邻两格间若没有粗线则两数字之差不能为1。
求解很容易。
8，连续数独2
去掉九宫格，即使是9*9的也没有宫。
4*4
9*9
9，箭头数独
这个数独和杀手数独有一定的类似性，但是难度自然比不了杀手数独。
相似性在于，突破点都是枚举拆分的组合，如果能排除掉其他的，得到唯一的组合，就能得到一些信息。
这样，箭头路径上的格子是最先破解的：
到了这个时候，这个数独就和规则数独没有差别了，这就是规则退化现象
最后的结果：
10，边框数独
边框类数独，每行的左边右边都有一个数，每列的上边下边都有一个数，用来描述一些信息。
边框奇偶数独
边框奇偶数独的规则是，在规则数独的基础上，对每一行和每一列都有2个约束。
对于列来说，如果上面写的是奇数，那么最上面的奇数必须是这个数，如果上面写的是偶数，那么最上面的偶数必须是这个数，每一列的下面同理。
行和列同理。
比如说，上面的数独里面，第一列最上面的奇数必须是3，最下面的奇数必须是9，
第一行的最左边的偶数必须是8，最右边的奇数必须是9。
边框奇偶数独是我本人最喜欢的数独之一，中学的时候做过很多，不过都没有留下记载。
边框奇偶数独非常有趣，一般情况下，初始给出的数字很少，上面的数独里面只给出了7个。
她有趣的地方体现在，很容易做错！
之所以把边上的数字都抹掉了，是因为，逐步的记录规则的退化，有利于化简。
整个求解的过程我都录制成了视频：资源分享汇总_nameofcsdn的博客-CSDN博客
摩天楼数独
在标准规则的基础上，四周数字代表楼房的高度，高楼会挡住低楼（也就是大数字挡住小数字，小数字就是看不到的了），周围的数字是从这个角度可以看到的楼房的数目。
求解：
11，满覆盖杀手数独
满覆盖杀手数独是不给出数字的。
满覆盖杀手数独是在规则数独的基础上，增加2条规则：
第一，每个虚线框内所有数字都不同
第二，每个虚线框内所有数字之和都为虚线框所标注的数。
在资源分享汇总_nameofcsdn的博客-CSDN博客有我求解这个数独的时候录的完整的视频
计算机求解V1
满覆盖杀手数独也是有9个3*3的宫，这一点是和规则数独一样的。
而对于每一个小的区，给出了这个区中所有数字之和，这一点自然是必须要计算的。
这些区的划分没有固定的规律，只能逐一输入，根据区的编号标识，这一点，倒是和不规则数独一模一样。
下面先看代码再介绍如何使用。
代码：
#include<iostream>
using namespace std;
int list__[10][10];
int par[10][10]; //par[i][j]=n , n is less than 40
int anti[40][10]; //anti[n][?]=i*10+j;
int sum[40];
void init()
{
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)list__[i][j] = 0;
cout << "输入每一块的所有数字之和,以0结束" << endl;
for (int i = 1; i < 40; i++)
{
cin >> sum[i];
if (sum[i] == 0)break;
}
cout << "输入每个格子属于哪一块" << endl;
for (int i = 1; i < 40; 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 >> par[i][j];
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)
{
int p = par[i][j], m;
if (k > sum[p])return false;
if (k < sum[p])
{
bool flag = true;
for (int ii = 1; ii < 10; ii++)
{
m = anti[p][ii];
if (m == 0)break;
if (m == i * 10 + j)continue;
if (list__[m / 10][m % 10] == 0)flag = false;
if (list__[m / 10][m % 10] == k)return false;
}
if (flag)return false;
}
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 x = (i - 1) / 3 * 3, y = (j - 1) / 3 * 3;
for (int ii = x + 1; ii <= x + 3; ii++)for (int jj = y + 1; jj <= y + 3; jj++)
if (list__[ii][jj] == 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;
sum[par[i][j]] -= k;
if (trys(i, j + 1))return true;
sum[par[i][j]] += k;
}
list__[i][j] = 0;
return false;
}
void out()
{
for (int i = 1; i < 10; i++)
{
cout << endl;
for (int j = 1; j < 10; j++)cout << list__[i][j];
}
}
int main()
{
init();
auto s1=clock();
trys(1, 1);
out();
auto e1 = clock();
cout << endl<<e1 - s1;
return 0;
}使用示例：
首先，把这些区编号，顺序任意。
然后，各个区的左上角的数字按编号顺序写出来就是：（最后补1个0）
15 24 11 17 5 14 10 16 10 15 10 9 10 21 7 20 15 15 12 17 8 16 18 10 13 12 13 32 10 0
然后，把每个格子属于哪个区表示出来：
1 2 3 3 5 5 8 8 8
1 2 2 4 6 7 7 9 9
1 2 2 4 6 6 14 15 9
10 10 12 13 13 14 14 15 16
11 11 12 19 18 17 17 16 16
20 19 19 19 18 22 17 16 23
20 20 21 21 22 22 22 23 23
24 25 25 25 25 28 28 28 28
24 26 26 27 27 27 29 29 28
得到这2个数组，就可以开始求解了。
实际上，这2个数组已经包含了整个满覆盖杀手数独的所有信息。
这个和答案是一致的。
答案：
因为初始没有确定的数字，然后剪枝做的很粗略，所以求解整个满覆盖杀手数独大约需要300毫秒。
计算机求解V2
用状态压缩加快搜索
int list__[10][10];
int par[10][10]; //par[i][j]=n , n is less than 40
int anti[40][10]; //anti[n][?]=i*10+j;
int sum[40];
int row[10];
int col[10];
int gong[9];
void init()
{
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)list__[i][j] = 0;
cout << "输入每一块的所有数字之和,以0结束" << endl;
for (int i = 1; i < 40; i++)
{
Read(sum[i]);
if (sum[i] == 0)break;
}
cout << "输入每个格子属于哪一块" << endl;
for (int i = 1; i < 40; 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++)
{
Read(par[i][j]);
if (par[i][j] == -1)continue;
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)
{
int p = par[i][j], m;
if (p > 0) {
if (k > sum[p])return false;
if (k < sum[p])
{
bool flag = true;
for (int ii = 1; ii < 10; ii++)
{
m = anti[p][ii];
if (m == 0)break;
if (m == i * 10 + j)continue;
if (list__[m / 10][m % 10] == 0)flag = false;
if (list__[m / 10][m % 10] == k)return false;
}
if (flag)return false;
}
}
if (row[i] & (1 << k))return false;
if (col[j] & (1 << k))return false;
int x = (i - 1) / 3, y = (j - 1) / 3;
if (gong[x * 3 + y] & (1 << k))return false;
return true;
}
void out()
{
for (int i = 1; i < 10; i++)
{
cout << endl;
for (int j = 1; j < 10; j++)cout << list__[i][j];
}
}
bool trys(int id)
{
if (id >= 81) {
return true;
}
int i = id / 9 + 1, j = id % 9 + 1;
if (list__[i][j])return trys(id+1);
for (int k = 1; k < 10; k++)if (ok(i, j, k))
{
list__[i][j] = k;
int x = (i - 1) / 3, y = (j - 1) / 3;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] -= k;
if (trys(id + 1))return true;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] += k;
}
list__[i][j] = 0;
return false;
}
int main()
{
init();
auto s1 = clock();
trys(0);
out();
auto e1 = clock();
cout << endl << e1 - s1;
return 0;
}还是上面这个数独，一样的输入，运行时间从300毫秒优化到150毫秒。
计算机求解V3
如果能调整搜索顺序，而不是81个格子按顺序搜索，肯定能加速搜索。
我先试一下手动输入搜索顺序的效果：
int list__[10][10];
int par[10][10]; //par[i][j]=n 每个格子属于哪一块
vector<int>anti[82]; //每个分组有哪些格子
int antiLast[82];
int sum[82];
vector<int>tryId(81);
int row[10];
int col[10];
int gong[9];
void init()
{
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)list__[i][j] = 0;
cout << "输入每一块的所有数字之和,以0结束" << endl;
for (int i = 1; i < 40; i++)
{
Read(sum[i]);
if (sum[i] == 0)break;
}
cout << "输入每个格子属于哪一块" << endl;
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)
{
Read(par[i][j]);
if (par[i][j] == -1)continue;
anti[par[i][j]].push_back(i * 10 + j);
antiLast[par[i][j]] = i * 10 + j;
}
}
bool ok(int i, int j, int k)
{
int p = par[i][j];
if (p > 0) {
if (k > sum[p])return false;
if (k < sum[p])
{
if (i * 10 + j == antiLast[p])return false;
for (auto m : anti[p])
{
if (m == i * 10 + j)continue;
if (list__[m / 10][m % 10] == k)return false;
}
}
else {
if( i * 10 + j != antiLast[p])return false;
}
}
if (row[i] & (1 << k))return false;
if (col[j] & (1 << k))return false;
int x = (i - 1) / 3, y = (j - 1) / 3;
if (gong[x * 3 + y] & (1 << k))return false;
return true;
}
void out()
{
for (int i = 1; i < 10; i++)
{
cout << endl;
for (int j = 1; j < 10; j++)cout << list__[i][j];
}
}
bool trys(int id)
{
if (id >= 81) {
return true;
}
int i = tryId[id] / 9 + 1, j = tryId[id] % 9 + 1;
if (list__[i][j])return trys(id + 1);
for (int k = 1; k < 10; k++)if (ok(i, j, k))
{
list__[i][j] = k;
int x = (i - 1) / 3, y = (j - 1) / 3;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] -= k;
if (trys(id + 1))return true;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] += k;
}
list__[i][j] = 0;
return false;
}
void getTryId()
{
int x;
for (int i = 0; i < 81; i++) {
cin >> x;
tryId[x - 1] = i;
}
}
int main()
{
init();
getTryId();
auto s1 = clock();
trys(0);
out();
auto e1 = clock();
cout << endl << e1 - s1;
return 0;
}还是上面的数独，我大概编排了一下搜索顺序（需要保证每个小框的最后一行中最右边的格子是小框里面最后一个搜索的）
在搜索算法模板里面的代码是没有这个限制的，搜索顺序可以完全自定义。
输入：
15 24 11 17 5 14 10 16 10 15 10 9 10 21 7 20 15 15 12 17 8 16 18 10 13 12 13 32 10 0
1 2 3 3 5 5 8 8 8
1 2 2 4 6 7 7 9 9
1 2 2 4 6 6 14 15 9
10 10 12 13 13 14 14 15 16
11 11 12 19 18 17 17 16 16
20 19 19 19 18 22 17 16 23
20 20 21 21 22 22 22 23 23
24 25 25 25 25 28 28 28 28
24 26 26 27 27 27 29 29 28
12 13 1 2 3 4 5 6 7
14 22 23 10 16 8 9 19 20
15 24 25 11 17 18 27 26 21
29 30 33 35 36 37 38 28 49
31 32 34 39 44 46 47 50 51
43 40 41 42 45 57 48 52 58
53 54 55 56 59 60 61 62 63
64 66 68 70 72 74 76 79 80
65 67 69 71 73 75 77 78 81
运行时间优化到15毫秒。
12，非满覆盖杀手数独
满覆盖杀手数独的小框是覆盖所有格子的。
非满覆盖数独就是小框数量少一点，只覆盖一部分格子，剩下的格子虽然总和也是知道的，但是不保证里面没有重复数字。（如果剩下的格子数量超过9则一定有重复数字）
这个非满覆盖杀手数独有的小框覆盖了53个格子，剩下28个格子里面显然有重复数字。
计算机求解V1
在枚举完小框之后，数独就退化成标准数独，则可以用dancing links去求解了。
class DancingLink // 精确覆盖算法
{
public:
DancingLink(int m, int n, int maxNum) //01矩阵的行、列、1的最大数量
{
this->m = m, this->n = n, maxNum += n + 1;
rhead.resize(m + 1), nums.resize(n + 1);
row.resize(maxNum), col.resize(maxNum);
up.resize(maxNum), down.resize(maxNum), lef.resize(maxNum), rig.resize(maxNum);
sc.resize(m), rows.resize(m);
for (int i = 0; i <= n; i++)
{
up[i] = i, down[i] = i;
lef[i] = i - 1, rig[i] = i + 1;
row[i] = 0, col[i] = i, nums[i] = 0;
}
lef[0] = n, rig[n] = 0, nums[0] = INT_MAX;
key = n;
for (int i = 0; i <= m; i++)rhead[i] = 0;
}
void push(int r, int c)//新增坐标在(r,c)的一个节点
{
row[++key] = r, col[key] = c;
up[key] = c, down[key] = down[c];
up[down[c]] = key, down[c] = key;
if (rhead[r] == 0)rhead[r] = lef[key] = rig[key] = key;
else
{
lef[key] = rhead[r], rig[key] = rig[rhead[r]];
lef[rig[rhead[r]]] = key, rig[rhead[r]] = key;
}
nums[c]++;
}
vector<vector<int>> getAllAns()
{
return dfs(false);
}
vector<int> getAnyAns()
{
auto v = dfs(true);
if (v.size())return v[0];
return vector<int>{};
}
private:
vector<vector<int>> dfs(bool onlyOne)
{
vector<vector<int>>ans;
while (true) {
if (rig[0] == 0) {
rows.resize(rowsid);
ans.push_back(rows);
rows.resize(m);
if (onlyOne)return ans;
}
int c = min_element(nums.begin() + 1, nums.end()) - nums.begin();
if (rig[0] == 0)c = 0;
del(c);
while (true) {
c = down[c];
if (c > n)break;
reback(col[c]);
if (scid == 0)return ans;
c = sc[--scid];
rowsid--;
for (int j = rig[c]; j != c; j = rig[j])reback(col[j]);
}
sc[scid++] = c;//记录选中id
rows[rowsid++] = row[c];
for (int j = rig[c]; j != c; j = rig[j])del(col[j]);
}
return ans;
}
inline void del(int c)//删除第c列的所有元素和他们所在行的所有元素
{
lef[rig[c]] = lef[c], rig[lef[c]] = rig[c];
for (int i = down[c]; i != c; i = down[i])
for (int j = rig[i]; j != i; j = rig[j])
down[up[j]] = down[j], up[down[j]] = up[j], nums[col[j]]--;
nums[c] = INT_MAX;
}
inline void reback(int c)//完全回退del操作
{
lef[rig[c]] = rig[lef[c]] = c, nums[c] = 0;
for (int i = down[c]; i != c; i = down[i]) {
for (int j = rig[i]; j != i; j = rig[j])
down[up[j]] = up[down[j]] = j, nums[col[j]]++;
nums[c]++;
}
}
private:
int m, n, key;
vector<int>row, col;//每个节点的行，列
vector<int>rhead;//每行第一个节点的id
vector<int>up, down, lef, rig;//每个节点上下左右的节点id
vector<int>nums;//每一列的元素个数
vector<int>sc;
int scid = 0, rowsid = 0;
vector<int>rows;//覆盖选中的行，值的范围是从1到m
};
string Sudoku(string s, int cEmpty = '.')
{
int num = 0;
for (auto c : s)if (c != cEmpty)num++;
int m = (81 - num) * 9 + num;
int n = 81 * 4;
DancingLink d(m, n, m * 4 + n + 5);
int row = 0;
map<int, int>mrow;
mrow[0] = -1;
for (int i = 0; i < 81; i++) {//第i个格子
char c = s[i];
int low = 0, high = 8;
if (c != cEmpty)low = high = c - '1';//第i个格子的搜索值域
for (int x = low; x <= high; x++) {
d.push(++row, i + 1), d.push(row, i / 9 * 9 + x + 81 + 1);
d.push(row, i % 9 * 9 + x + 162 + 1), d.push(row, (i / 27 * 3 + i % 9 / 3) * 9 + x + 243 + 1);
mrow[row] = i;
}
}
vector<int> vans = d.getAnyAns();
if (vans.empty())return "";
string ans = s;
for(auto row: vans){
int id = mrow[row];
if (s[id] == cEmpty) {
ans[id] = '1';
while (mrow[row - 1] == id)ans[id]++, row--;
}
else ans[id] = s[id];
}
return ans;
}
int list__[10][10];
int par[10][10]; //par[i][j]=n 每个格子属于哪一块
vector<int>anti[82]; //每个分组有哪些格子
int antiLast[82];
int sum[82];
vector<int>tryId(81);
int row[10];
int col[10];
int gong[9];
void init()
{
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)list__[i][j] = 0;
cout << "输入每一块的所有数字之和,以0结束" << endl;
for (int i = 1; i < 40; i++)
{
Read(sum[i]);
if (sum[i] == 0)break;
}
cout << "输入每个格子属于哪一块" << endl;
for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)
{
Read(par[i][j]);
if (par[i][j] == -1)continue;
anti[par[i][j]].push_back(i * 10 + j);
antiLast[par[i][j]] = i * 10 + j;
}
}
bool ok(int i, int j, int k)
{
int p = par[i][j];
if (p > 0) {
if (k > sum[p])return false;
if (k < sum[p])
{
if (i * 10 + j == antiLast[p])return false;
for (auto m : anti[p])
{
if (m == i * 10 + j)continue;
if (list__[m / 10][m % 10] == k)return false;
}
}
else {
if( i * 10 + j != antiLast[p])return false;
}
}
if (row[i] & (1 << k))return false;
if (col[j] & (1 << k))return false;
int x = (i - 1) / 3, y = (j - 1) / 3;
if (gong[x * 3 + y] & (1 << k))return false;
return true;
}
void out()
{
for (int i = 1; i < 10; i++)
{
cout << endl;
for (int j = 1; j < 10; j++)cout << list__[i][j];
}
}
int xxx = 0;
bool trys(int id)
{
if (id == 59) {
xxx++;
if (xxx % 10000 == 0)cout << xxx << " ";
string s;
char c = '0';
for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++) {
s += list__[i][j] ? list__[i][j] + c : '.';
}
s = Sudoku(s);
if (s != "")cout << s << endl;
return false;
}
if (id >= 81) {
return true;
}
int i = tryId[id] / 9 + 1, j = tryId[id] % 9 + 1;
if (list__[i][j])return trys(id + 1);
for (int k = 1; k < 10; k++)if (ok(i, j, k))
{
list__[i][j] = k;
int x = (i - 1) / 3, y = (j - 1) / 3;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] -= k;
if (trys(id + 1))return true;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] += k;
}
list__[i][j] = 0;
return false;
}
void getTryId()
{
int x;
for (int i = 0; i < 81; i++) {
cin >> x;
tryId[x - 1] = i;
}
}
int main()
{
init();
getTryId();
auto s1 = clock();
trys(0);
out();
auto e1 = clock();
cout << endl << e1 - s1;
return 0;
}输入：
20 25 22 23 17 28 21 14 29 17 28 21 18 0
-1 -1 -1 -1 -1 -1 10 10 10
-1 8 8 8 -1 9 11 11 10
-1 -1 7 7 -1 9 11 11 10
5 6 6 7 -1 9 9 9 -1
5 5 5 -1 -1 -1 -1 -1 -1
5 6 6 -1 -1 12 12 13 -1
2 1 1 4 3 4 12 13 -1
2 2 1 4 3 4 -1 13 -1
2 2 2 3 3 3 -1 -1 -1
60 26 23 63 64 65 50 51 52
61 24 22 25 66 55 46 47 53
62 27 19 20 67 56 48 49 54
14 10 11 21 68 57 58 59 74
15 16 17 69 70 71 75 76 77
18 12 13 72 73 37 38 40 78
5 2 3 28 32 30 39 41 43
6 1 4 29 33 31 44 42 45
7 8 9 34 35 36 79 80 81
可惜计算量还是太大了，没算出来结果。
计算机求解V2
对于接近满覆盖的杀手数独，就不需要dancing links了，直接求解
bool trys(int id)
{
if (id >= 81) {
return true;
}
int i = tryId[id] / 9 + 1, j = tryId[id] % 9 + 1;
if (list__[i][j])return trys(id + 1);
for (int k = 1; k < 10; k++)if (ok(i, j, k))
{
list__[i][j] = k;
int x = (i - 1) / 3, y = (j - 1) / 3;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] -= k;
if (trys(id + 1))return true;
row[i] ^= (1 << k);
col[j] ^= (1 << k);
gong[x * 3 + y] ^= (1 << k);
sum[par[i][j]] += k;
}
list__[i][j] = 0;
return false;
}
void getTryId()
{
int x;
for (int i = 0; i < 81; i++) {
cin >> x;
tryId[x - 1] = i;
}
}
int main()
{
init();
getTryId();
auto s1 = clock();
trys(0);
out();
auto e1 = clock();
cout << endl << e1 - s1;
return 0;
}
输入：
26 14 16 12 16 6 14 14 12 8 20 12 26 22 6 6 38 16 14 6 14 0
-1 1 2 2 3 3 -1 4 -1
1 1 1 5 5 3 -1 4 4
6 1 -1 5 5 8 8 -1 7
6 9 9 -1 10 10 11 12 7
13 13 13 14 -1 10 11 12 12
15 13 13 14 14 -1 11 11 21
15 -1 16 16 17 17 -1 -1 21
18 -1 -1 17 17 17 -1 19 19
18 18 -1 17 17 20 20 19 -1
18 19 25 26 30 31 47 42 46
17 20 21 35 36 32 45 43 44
1 22 27 37 38 33 34 39 40
2 7 8 51 48 49 52 53 41
9 10 11 54 57 50 61 59 60
3 12 13 55 56 58 62 63 64
4 23 5 6 75 76 73 70 65
14 24 28 78 79 77 74 68 66
15 16 29 80 81 71 72 69 67
输出：
956834217
742169583
183725946
539241768
867953124
214678395
421587639
395416872
678392451
耗时72毫秒
13，倍数数独
把所有相邻格子的数是倍数关系的都标注出来的数独（1和其他数之间不算）
原始数独：
首先画出倍数关系：
然后画出简化图：
然后就可以开始求解数独了
比如，第8行第8列的格子是和3个不同的数都有倍数关系，那它就是2
再比如，第2列是一个长为6的串，所以一定是936248或者936284
于是得到：
照这个思路继续求解即可。
14，不等式数独
数字需要符合版面上不等式(大于/小于)要求。
4*4
5*5
7*7
15，武士数独
武士数独是5个数独叠在一起。
如果我没看错的话，这个武士数独，数字的位置居然是中心对称的！
首先，很明显，有4个特殊的3*3的小正方形是最容易破解的。
也就是最中间的标准数独和另外4个标准数独分别重合的小正方形。
这4个小正方形受到双方约束的叠加，所以很容易求出来。
于是第一步，把这4个小正方形全部破解，当然，如果有必要的话，少数其他的格子要先推出来。
又或者，在思考的时候，发现一些特别明显的格子，也可以写下来。
这样，数独就变成了下面这样：
这样，武士数独就直接变成了5个完全独立的数独。
上面2个是：
中间是：
下面2个是：
这样，武士数独就完全解决了，这个过程，花了我89分钟。
当然，我是用电脑自带的画图画的（全程口算无任何草稿），如果是用笔的话，
不仅写起来很快，而且可以在纸上打草稿，估计1个小时是可以解决的。
16，变种数独的规则退化现象
很多变种数独，在求解的过程中，会使得这附加的规则已经满足，
这个时候，规则退化，数独就变成了规则数独了。
例如：情人节趣味数独、箭头数独、对角线数独
但是，也有的变种数独，是基本上不会退化的。
只有当数独基本上已经解决了，只剩下极少数的格子的时候，才会退化，这相当于没有退化。
例如：窗口数独
而杀手数独，是真的永不退化。
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
2
0- 0
已为社区贡献20条内容
所有评论(0)