dlx算法解数独,有空会写详解,暂时就这样了
| Sudoku
Description In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,
Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns. Input The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”. Output For each test case, print a line representing the completed Sudoku puzzle. Sample Input .2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.end Sample Output 527389416819426735436751829375692184194538267268174593643217958951843672782965341416837529982465371735129468571298643293746185864351297647913852359682714128574936 Source |
[] [Go Back] [] []
/*=============================================================================# FileName: 3074.cpp# Desc: # Author: zhuting# Email: cnjs.zhuting@gmail.com# HomePage: my.oschina.net/locusxt# Version: 0.0.1# CreatTime: 2014-01-16 21:44:18# LastChange: 2014-01-16 21:44:18# History:=============================================================================*//* * 数独需要满足的四个条件: * 1.每个格子都有数字 * 2.每一行要有1-9 * 3.每一列要有1-9 * 4.每个3*3的块要有1-9 * * 1-81列 表示某个格子有没有填数字,填了则为1 * 82-162列 表示某一行有没有1-9 * 163-243列 表示某一列有没有1-9 * 244-324列 表示某个块有没有1-9 * * 共9*9*9行 * 表示某一个格子填了某个数后的影响 */#include#include #include #include #include #define maxl 100#define maxc 325 //最大列数,包含头结点#define maxr 730 //最大行数,包含待匹配行#define maxn 240000 //最大总结点数#define head 0 //head的编号为0#define GET_CEL(i, j, k) i*9+j#define GET_ROW(i, j, k) 80+i*9+k#define GET_COL(i, j, k) 161+j*9+k#define GET_BLO(i, j, k) 242+(3*(i/3)+j/3)*9+k#define GET_I(l) (l-1)/81#define GET_J(l) (l-1)%81/9#define GET_K(l) (l-1)%81%9+1const int m = 729;//行数const int n = 324;//列数bool mymap[maxr][maxc];int num[maxc] = {0};//数组实现的dancing linksint up[maxn] = {0}, down[maxn] = {0}, left[maxn] = {0}, right[maxn] = {0};//顾名思义是某个结点的上下左右结点的标号int column[maxn] = {0}, row[maxn] = {0}, ans[maxn] = {0};//某个结点对应的行号,ans是取的行号的数组char str[maxl];/* * 每填一个数,假设填在数独i行j列填的是k * 那么会产生以下影响: * 9*j+i个cell被填上了数字 *///生成初始的01串void gen_zero_one(){ int cur_line = 0; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { for (int k = 1; k <= 9; ++k) { mymap[cur_line][GET_CEL(i, j, k)] = 1; mymap[cur_line][GET_ROW(i, j, k)] = 1; mymap[cur_line][GET_COL(i, j, k)] = 1; mymap[cur_line][GET_BLO(i, j, k)] = 1; ++cur_line; } } } return;}//生产初始的节点表void gen_node(){ int id = 1; int tmp = 0; int lineup[maxc] = {0}; for (int j = 0; j < n; ++j)//待匹配行 { lineup[j] = id; column[id] = j + 1; if (j != n - 1) { right[id] = id + 1; } left[id] = id - 1; ++id; } right[head] = 1; left[head] = id - 1; right[id - 1] = head; for (int i = 0; i < m; ++i) { int first_id = 0; int left_id = 0; for (int j = 0; j < n; ++j) { //scanf("%d", &tmp); tmp = mymap[i][j]; if (tmp) { row[id] = i + 1; column[id] = j + 1; if (first_id == 0) { first_id = id; left_id = id; } else { left[id] = left_id; right[left_id] = id; left_id = id; } int upid = lineup[j]; up[id] = upid; down[upid] = id; lineup[j] = id; ++id; } } if (first_id != 0) { left[first_id] = left_id; right[left_id] = first_id; } } for (int j = 0; j < n; ++j) { down[lineup[j]] = j + 1; up[j + 1] = lineup[j]; } //test(id); return;}void init()//初始化{ memset(up, 0, sizeof(up)); memset(down, 0, sizeof(down)); memset(left, 0, sizeof(left)); memset(right, 0, sizeof(right)); memset(column, 0, sizeof(column)); memset(row, 0, sizeof(row)); memset(ans, 0, sizeof(ans)); memset(mymap, 0, sizeof(mymap)); for (int i = 1; i <= n; ++i) num[i] = 9; return;}//这里的remove其实并没有真正删除掉结点,可以用resume恢复void remove(int c)//去掉c号结点,以及在c所在列上有结点的行的结点{ left[right[c]] = left[c]; right[left[c]] = right[c]; for (int i = down[c]; i != c; i = down[i]) { for (int j = right[i]; j != i; j = right[j]) { up[down[j]] = up[j]; down[up[j]] = down[j]; --num[column[j]]; } } return;}void resume(int c)//remove的逆操作{ left[right[c]] = c; right[left[c]] = c; for (int i = up[c]; i != c; i = up[i]) { for (int j = right[i]; j != i; j = right[j]) { up[down[j]] = j; down[up[j]] = j; ++num[column[j]]; } } return;}void recover(int t){ for (int i = 0; i < t; ++i) { int tmp = ans[i]; int cur = GET_I(tmp) * 9 + GET_J(tmp); str[cur] = GET_K(tmp) + '0'; /* printf("%d:\n", tmp); printf("%d %d %d\n", GET_I(tmp), GET_J(tmp), GET_K(tmp)); */ } return;}//我们的终极目标实际上是把十字链表中所有的结点都删掉,只留一个头结点bool dance(int k)//这里的k实际上是没多大意义的{ //printf("dance: %d\n", k); int c = right[head];//c是头结点的右边一个结点 if (c == head)//只剩下十字链表的头结点,则完成了目标 { recover(k); return true; } int min_n = num[c]; int min_cur = c; while(true) { c = right[c]; if (c == head) break; if(num[c] < min_n) { min_n = num[c]; min_cur = c; } } c = min_cur; remove(c); for (int i = down[c]; i != c; i = down[i])//这里其实是枚举某一行对待匹配行的第c位进行匹配 { ans[k] = row[i]; for (int j = right[i]; j != i; j = right[j]) remove(column[j]);//remove待匹配行的column[j]结点 if (dance(k + 1)) return true; for (int j = left[i]; j != i; j = left[j]) resume(column[j]); } resume(c); return false;}void parse(char* a){ int tmp = 0; for(int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if(a[i * 9 + j] != '.') { tmp = a[i * 9 + j] - '0'; remove(GET_CEL(i, j, tmp) + 1); remove(GET_ROW(i, j, tmp) + 1); remove(GET_COL(i, j, tmp) + 1); remove(GET_BLO(i, j, tmp) + 1); } } } return;}int main(){ while (true) { scanf("%s", str); if (str[0] == 'e') { break; } init(); gen_zero_one(); gen_node(); parse(str); int is_possible = dance(0); if (is_possible) { printf("%s\n", str); } else printf("error\n"); } return 0;}