poj3074Sudoku(DLX解9*9数独)

->题目请戳这里<-

题目大意：填9*9数独，就不多废话了。

题目分析：以前写数独是用搜索做的，略带暴力枚举，代码量比较大，效率也不高，最近学dancing links，用来解决精确覆盖问题，效率蛮高，而且代码非常优雅。关于数独转化成精确覆盖问题，这篇论文讲的很详细，就不在这里班门弄斧了，详情请见代码：

#include 
#include
#include
#include
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("\n");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行填kinsert(base + k,81 + 9 * cc + k);//第cc列填kinsert(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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！