共有回帖数 0 个
-
mapping 是 字符 到 0~N-1 的映射
mapping 是 0~N-1 到 对应字符 的映射
大家应该注意到字符集中 '1'~'9' 不一定连续，这样做在修改为高阶后也可以方便地自定义字符
这个程序可以很方便地更改为更高阶的，不局限于9阶。宫（刚刚知道这个术语）的大小也可以更改
我似乎没完整地解出过数独……刚看了 http://baike.baidu.com/view/961.htm 发现还有这么多解法……
从上面那一段中，大家应该能看出我几乎不懂数独，所以用的算法就是搜索！
搜索也是有技巧的。感谢 Donald E. Knuth 的 Dancing Links 和 Algorithm X，让我这样一个不懂数独的人也能写出比较快求解数独的程序
输入格式
输入８１个字符后结束
.：空格
1：就是数字１……
2：就是数字2……
重发，KM 帮忙删掉啊
#include algorithm
#include limits
#include cstdio
#include cstring
using namespace std;
const int N = 9, LEN = 3; //size
const int MAX_R = N*N*N, MAX_C = N*N*4, MAX = MAX_C+1+MAX_R*4;
int L[MAX], R[MAX], U[MAX], D[MAX], size[MAX_C+1], column[MAX];
int res[N*N]; //result
pairint, int mean[MAX]; //first: pos. second: number
int mapping[256];
char mapping2[N];
void insert(int cur, int left, int right, int top)
{
L[cur] = left; R[cur] = right;
U[cur] = U[top]; D[U[cur]] = cur;
D[cur] = top; U[top] = cur;
column[cur] = top;
++size[top];
}
void remove(int c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for (int i = D[c]; i != c; i = D)
for (int j = R; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
--size[column[j]];
}
}
void resume(int c)
{
for (int i = U[c]; i != c; i = U)
for (int j = L; j != i; j = L[j])
{
U[D[j]] = j;
D[U[j]] = j;
++size[column[j]];
}
L[R[c]] = c;
R[L[c]] = c;
}
bool DLX(int k)
{
if (R[MAX_C] == MAX_C) return true;
int c, mins = numeric_limitsint::max();
for (int i = R[MAX_C]; i != MAX_C; i = R)
if (size mins)
mins = size, c = i;
remove( c );
for (int i = D[c]; i != c; i = D)
{
for (int j = R; j != i; j = R[j])
remove(column[j]);
res[mean.first] = mean.second;
if (DLX(k+1)) return true;
for (int j = L; j != i; j = L[j])
resume(column[j]);
}
resume( c );
return false;
}
int main()
{
char str[N*N+1], tmp[N*N+1];
str[0] = 0;
mapping['1'] = 0; mapping2[0] = '1';
mapping['2'] = 1; mapping2[1] = '2';
mapping['3'] = 2; mapping2[2] = '3';
mapping['4'] = 3; mapping2[3] = '4';
mapping['5'] = 4; mapping2[4] = '5';
mapping['6'] = 5; mapping2[5] = '6';
mapping['7'] = 6; mapping2[6] = '7';
mapping['8'] = 7; mapping2[7] = '8';
mapping['9'] = 8; mapping2[8] = '9';
while (strlen(str) N*N)
scanf("%s", tmp), strcat(str, tmp);
int cur = MAX_C+1;
for (int i = 0; i = MAX_C; ++i)
{
L = i-1; R = i+1;
U = i; D = i;
size = 0;
}
L[0] = MAX_C; R[MAX_C] = 0;
for (int i = 0; i N; ++i)
for (int j = 0; j N; ++j)
if (str[i*N+j] == '.')
{
for (int k = 0; k N; ++k)
{
insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
}
}
else
{
const int k = mapping[str[i*N+j]];
insert(cur, cur+3, cur+1, i*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N+j*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur+1, N*N*2+(i/LEN*LEN+j/LEN)*N+k); mean[cur++] = make_pair(i*N+j, k);
insert(cur, cur-1, cur-3, N*N*3+i*N+j); mean[cur++] = make_pair(i*N+j, k);
res[i*N+j] = k;
}
if (!DLX(0))
puts("No solution.");
else
for (int i = 0; i N; ++i, puts(""))
for (int j = 0; j N; ++j)
putchar(mapping2[res[i*N+j]]);
}
楼主 2015-12-24 21:11 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
