Source Code

Source Code

Problem: 3074User: twoyao
Memory: 192KTime: 32MS
Language: C++Result: Accepted
  • Source Code
  • /***
    *Sudoku[http://poj.org/problem?id=3704]
    ***********************************************/
    
    #include <stdio.h>
    #define max_level 81
    #define max_degree 1000
    #define cols_num 324		
    #define rows_num 729
    #define max_nodes 2916 // 729 * 4
    
    typedef struct node_struct {
    	struct node_struct *left, *right;
    	struct node_struct *up, *down;
    	struct col_struct *col;
    } node;
    
    typedef struct col_struct {
    	struct node_struct head;
    	int len;
    	int id;
    	struct col_struct *prev, *next;
    } column ;
    
    column col_array[cols_num + 1];
    node node_array[max_nodes];
    node* choice[max_level];
    
    #define root col_array[0]
    
    void init() {
    	register column *cur_col;
    	register node *cur_node;
    	register int i, j, k;
    	for (cur_col = col_array + 1, i = 0; cur_col <= &col_array[cols_num]; ++cur_col) {
    		cur_col->head.up = cur_col->head.down = &cur_col->head;
    		cur_col->len = 0;
    		cur_col->id = i++;
    		cur_col->prev = cur_col-1;
    		(cur_col-1)->next = cur_col;
    	}
    	col_array[cols_num].next = &root;
    	root.prev = &col_array[cols_num];
    
    	cur_node = node_array;
    	for (i = 0; i < 9; ++i) {
    		for (j = 0; j < 9; ++j) {
    			for (k = 0; k < 9; ++k) {
    				// cols : i * 9 + k, j * 9 + k, ((i / 3) * 3 + j / 3) * 9 + k, i * 9 + j
    
    				cur_node->right = cur_node+1, (cur_node+1)->right = cur_node+2; 
    				(cur_node+2)->right = cur_node+3, (cur_node+3)->right = cur_node;
    
    				cur_node->left = cur_node+3, (cur_node+1)->left = cur_node; 
    				(cur_node+2)->left = cur_node+1, (cur_node+3)->left = cur_node+2;
    
    				cur_col = col_array + (1+i*9+k);
    				cur_node->col = cur_col;
    				cur_node->up = cur_col->head.up, cur_col->head.up->down = cur_node;
    				cur_col->head.up = cur_node, cur_node->down = &cur_col->head;
    				cur_col->len ++;
    				cur_node++;
    
    				cur_col = col_array + (82+j*9+k);
    				cur_node->col = cur_col;
    				cur_node->up = cur_col->head.up, cur_col->head.up->down = cur_node;
    				cur_col->head.up = cur_node, cur_node->down = &cur_col->head;
    				cur_col->len ++;
    				cur_node++;
    
    				cur_col = col_array + (163+((i/3)*3+j/3)*9+k);
    				cur_node->col = cur_col;
    				cur_node->up = cur_col->head.up, cur_col->head.up->down = cur_node;
    				cur_col->head.up = cur_node, cur_node->down = &cur_col->head;
    				cur_col->len ++;
    				cur_node++;
    
    				cur_col = col_array + (244+i*9+j);
    				cur_node->col = cur_col;
    				cur_node->up = cur_col->head.up, cur_col->head.up->down = cur_node;
    				cur_col->head.up = cur_node, cur_node->down = &cur_col->head;
    				cur_col->len ++;
    				cur_node++;
    			}
    		}
    	}
    }
    
    void cover(column *c) {
    	register column *l, *r;
    	register node *rr, *nn, *uu, *dd;
    	l = c->prev, r = c->next;
    	l->next = r, r->prev = l;
    	for (rr = c->head.down; rr != &(c->head); rr = rr->down) {
    		for (nn = rr->right; nn != rr; nn = nn->right) {
    			uu = nn->up, dd = nn->down;
    			uu->down = dd, dd->up = uu;
    			if (nn->col->len < 0 ) {
    				nn->col->len = 0;
    			}
    			nn->col->len--;
    		}
    	}
    }
    
    void uncover(column *c) {
    	register column *l, *r;
    	register node *rr, *nn, *uu, *dd;
    	for (rr = c->head.up; rr != &(c->head); rr = rr->up) {
    		for (nn = rr->left; nn != rr; nn = nn->left) {
    			uu = nn->up, dd = nn->down;
    			uu->down = dd->up = nn;
    			nn->col->len ++;
    		}
    	}
    	l = c->prev, r = c->next;
    	l->next = r->prev = c;
    }
    
    int main()  {
    	register column *cur_col, *best_col;
    	register node *cur_node, *pp;
    	int i, j, t, minLen, level;
    	char buf[82];
    	
    #ifdef LOCAL_DEBUG
    	freopen("data.txt", "r", stdin);
    #endif
    	while (gets(buf)) 
    	{
    		if (buf[0] == 'e') break;
    		init();
    		for (i = 0; i < 81; ++i) {
    			if (buf[i] != '.') {
    				pp = cur_node = node_array + (i*9 + buf[i] - '1') * 4;
    				do { cover(pp->col); pp = pp->right; } while (pp != cur_node);
    			}
    		}
    		level = 0;
    forward:
    		minLen = max_nodes;
    		for (cur_col = root.next; cur_col != &root; cur_col = cur_col->next) {
    			if (cur_col->len < minLen) best_col = cur_col, minLen = cur_col->len;
    		}
    		cover(best_col);
    		cur_node = choice[level] = best_col->head.down;
    advance:
    		if (cur_node == &(best_col->head)) goto backup;
    		for (pp=cur_node->right; pp!=cur_node; pp=pp->right) cover(pp->col);
    		if (root.next == &root) {
    			for (i = 0; i <= level; ++i) {
    				t = (choice[i] - node_array) / 4;
    				buf[t/9] = (t % 9) + '1';
    			}
    			puts(buf);
    			continue;
    			//goto recover;
    		}
    		level++;
    		goto forward;
    backup:
    		uncover(best_col);
    		if (level == 0) goto done;
    		level --;
    		cur_node = choice[level];
    		best_col = cur_node->col;
    recover:
    		for (pp=cur_node->left;pp!=cur_node;pp=pp->left) uncover(pp->col);
    		cur_node = choice[level] = cur_node->down; 
    		goto advance;
    done:
    		continue;
    	}
    	return 0;
    }