poj 3074 Sudoku(DX解9*9数独)
->タイトルはここを押してください.
9*9数独を記入すると、余計なことを言わなくなります.
題目の分析:以前は数独を書いて検索で作ったもので、やや暴力的に列挙しています.コードの量が多く、効率も高くないです.最近はdancing linksを勉強して、正確なカバー問題を解決します.数独が正確なカバー問題に転化したことについて、この論文の話はとても詳しくて、ここのクラスで斧をいじりませんでした.詳細はコードをご覧ください.
9*9数独を記入すると、余計なことを言わなくなります.
題目の分析:以前は数独を書いて検索で作ったもので、やや暴力的に列挙しています.コードの量が多く、効率も高くないです.最近はdancing linksを勉強して、正確なカバー問題を解決します.数独が正確なカバー問題に転化したことについて、この論文の話はとても詳しくて、ここのクラスで斧をいじりませんでした.詳細はコードをご覧ください.
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 9 * 9 * 9 * 9 * 9 * 4 + 5;//9 * 9 * 9 9 * 9 * 4
int s[N],h[N],u[N],d[N],l[N],r[N],col[N],row[N],ans[N];
int head,num;
char str[200];
void init()
{
memset(s,0,sizeof(s));// , TLE!!
head = 0;
int i;
int c = 9 * 9 * 4;
for(i = 0;i <= c;i ++)
{
u[i] = d[i] = i;
l[i] = (i - 1 + c + 1) % (c + 1);
r[i] = (i + 1) % (c + 1);
}
num = c + 1;
memset(h,0,sizeof(h));
}
void insert(int i,int j)
{
if(h[i])
{
r[num] = h[i];
l[num] = l[h[i]];
l[r[num]] = num;
r[l[num]] = num;
}
else
{
h[i] = num;
l[num] = r[num] = num;
}
s[j] ++;
u[num] = u[j];
d[num] = j;
d[u[j]] = num;
u[j] = num;
col[num] = j;
row[num] = i;
num ++;
}
void del(int c)
{
l[r[c]] = l[c];
r[l[c]] = r[c];
int i,j;
for(i = d[c];i != c;i = d[i])
{
for(j = r[i];j != i;j = r[j])
{
u[d[j]] = u[j];
d[u[j]] = d[j];
s[col[j]] --;
}
}
}
void recover(int c)
{
int i,j;
for(i = u[c];i != c;i = u[i])
{
for(j = l[i];j != i;j = l[j])
{
s[col[j]] ++;
u[d[j]] = d[u[j]] = j;
}
}
r[l[c]] = l[r[c]] = c;
}
bool dfs(int k)
{
int i,j;
if(r[head] == head)
{
sort(ans,ans + 81);
for(i = 0;i < 81;i ++)
{
printf("%d",ans[i] - i * 9);
}
printf("
");
return true;
}
int mn = N;
int c;
for(i = r[head];i != head;i = r[i])
{
if(s[i] < mn)
{
mn = s[i];
c = i;
}
}
del(c);
for(i = d[c];i != c;i = d[i])
{
ans[k] = row[i];
for(j = r[i];j != i;j = r[j])
del(col[j]);
if(dfs(k + 1))
return true;
for(j = l[i];j != i;j = l[j])
recover(col[j]);
}
recover(c);
return false;
}
int main()
{
while(scanf("%s",str) != EOF)
{
if(str[0] == 'e')
break;
init();
//system("pause");
for(int i = 0;i < strlen(str);i ++)
{
int rr = i / 9;
int cc = i - rr * 9;
int base = (rr * 9 + cc) * 9;
if(str[i] == '.')
{
for(int k = 1;k <= 9;k ++)// 1-9
{
insert(base + k,rr * 9 + k);// rr k
insert(base + k,81 + 9 * cc + k);// cc k
insert(base + k,81 + 81 + (3 * (rr / 3) + cc / 3) * 9 + k);
insert(base + k,81 + 81 + 81 + rr * 9 + cc + 1);
}
}
else
{
insert(base + str[i] - '0',rr * 9 + str[i] - '0');
insert(base + str[i] - '0',81 + 9 * cc + str[i] - '0');
insert(base + str[i] - '0',81 + 81 + (3 * (rr / 3) + cc / 3) * 9 + str[i] - '0');
insert(base + str[i] - '0',81 + 81 + 81 + rr * 9 + cc + 1);
}
}
dfs(0);
}
return 0;
}
//7568K 375MS