/* This program solves the exact cover problem. On the stdin it expects the representation of the exact cover, where each line on the input represents one vector. All vectors should be of the same length. The maximum length is 1000. A vector is represented by a sequence of 0 and 1. The remainder of the line (after skipping spaces) is used as the name for the vector. On the stdout put is generates the solutions (up to NR_SOLUTIONS_TO_FIND) by listing the names (each followed by '|') of the selected vectors on a line per solution found. The implementation makes use of dancing links, a technique suggested by D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links */ #include #include #include struct Vector; struct Position; struct Node { Node() : l(this), r(this), d(this), u(this), vector(0), position(0) {} void push_back(Node* n) { n->r = this, n->l = l; l->r = n; l = n; } void push_bottom(Node* n) { n->d = this, n->u = u; u->d = n; u = n; } void swapout_horz() { l->r = r; r->l = l; } void swapin_horz() { l->r = this; r->l = this; } void swapout_vert() { u->d = d; d->u = u; } void swapin_vert() { u->d = this; d->u = this; } Node *l; Node *r; Node *d; Node *u; Vector *vector; Position *position; }; struct Vector : public Node { char *name; }; struct Position : public Node { int nr; int nr_vec_left; }; Node root; int nr_pos = 0; int nr_vec = 0; void read(FILE *f) { char buf[1000]; while (fgets(buf, 1000, f)) { if (nr_pos == 0) { for (int i = 0; i < 1000 && (buf[i] == '0' || buf[i] == '1'); i++) nr_pos++; for (int i = 0; i < nr_pos; i++) { Position *position = new Position(); root.push_back(position); position->nr = i; position->nr_vec_left = 0; } } nr_vec++; Vector *vector = new Vector; root.push_bottom(vector); char *s = buf; Position *position = (Position*)root.r; for (int i = 0; i < 1000 && (*s == '0' || *s == '1'); i++, s++) { if (*s == '1') { Node *node = new Node(); position->push_bottom(node); vector->push_back(node); node->vector = vector; node->position = position; position->nr_vec_left++; } position = (Position*)position->r; } while (*s == ' ') s++; int l = strlen(s); while (s[l-1] < ' ') s[--l] = 0; vector->name = (char*)malloc(sizeof(char)*(l+1)); strcpy(vector->name, s); } } void ignoreVector(Vector* vector, Position* exclude) { vector->swapout_vert(); for (Node* node = vector->r; node != vector; node = node->r) { if (node->position != exclude) { node->swapout_vert(); node->position->nr_vec_left--; } } } void unignoreVector(Vector* vector, Position* exclude) { for (Node* node = vector->l; node != vector; node = node->l) { if (node->position != exclude) { node->swapin_vert(); node->position->nr_vec_left++; } } vector->swapin_vert(); } void selectPosition(Position* position, Vector* exclude) { position->swapout_horz(); for (Node* node = position->d; node != position; node = node->d) { if (node->vector != exclude) ignoreVector(node->vector, position); } } void unselectPosition(Position* position, Vector* exclude) { for (Node* node = position->u; node != position; node = node->u) { if (node->vector != exclude) unignoreVector(node->vector, position); } position->swapin_horz(); } void selectVector(Vector* vector) { vector->swapout_vert(); for (Node* node = vector->r; node != vector; node = node->r) selectPosition(node->position, vector); } void unselectVector(Vector* vector) { for (Node* node = vector->l; node != vector; node = node->l) unselectPosition(node->position, vector); vector->swapin_vert(); } int nr_solutions = 0; #define NR_SOLUTIONS_TO_FIND 10000 Vector* sol_vectors[1000]; int nr_sol_vectors = 0; bool solve() { // Found solution if there are no positions left if (root.r == &root) { nr_solutions++; for (int i = 0; i < nr_sol_vectors; i++) printf("%s|", sol_vectors[i]->name); printf("\n"); return nr_solutions >= NR_SOLUTIONS_TO_FIND; } // If there is a position that cannot be filled, then stop for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { if (position->nr_vec_left == 0) return false; } // If there is a position with only one possible vector, select this vector for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { if (position->nr_vec_left == 1) { Vector *vector = position->d->vector; sol_vectors[nr_sol_vectors++] = vector; selectVector(vector); bool result = solve(); unselectVector(vector); nr_sol_vectors--; return result; } } Vector* best_vec = 0; int best_nr = 0; for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d) { int nr = 0; for (Node* node = vector->r; node != vector; node = node->r) nr += node->position->nr_vec_left; if (best_vec == 0 || nr < best_nr) { best_vec = vector; best_nr = nr; } } if (best_vec == 0) return false; sol_vectors[nr_sol_vectors++] = best_vec; selectVector(best_vec); bool result = solve(); unselectVector(best_vec); nr_sol_vectors--; if (result) return true; ignoreVector(best_vec, 0); result = solve(); unignoreVector(best_vec, 0); return result; } void print(FILE *f) { for (Vector *vector = (Vector*)root.d; vector != &root; vector = (Vector*)vector->d) { Node *node = vector->r; for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { if (node != vector && node->position == position) { fprintf(f, "1"); node = node->r; } else fprintf(f, "0"); } fprintf(f, " %s\n", vector->name); } } int main(int argc, char* argv[]) { read(stdin); solve(); }