/* NCover - solving exact N cover problems For more information see: http://www.iwriteiam.nl/Dpuzzle.html#EC The implementation makes use of dancing links, a technique suggested by D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links Copyright (C) 2011-2019 Frans Faase http://www.iwriteiam.nl/ This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. GNU General Public License: http://www.iwriteiam.nl/GNU.txt */ #include #include #include class NCover { public: struct Vector; struct Position; NCover() : nr_pos(0), nr_vec(0), nr_impossible_pos(0), nr_calls_to_solve(0), p_depth(0), nr_solutions(0), sol_depth(0) {} private: 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; }; public: struct Vector : public Node { Vector(char *n_name) : name(n_name), next_ignored(0), next_selected(0) {} char *name; Vector* next_ignored; Vector* next_selected; Vector* next_best; }; struct Position : public Node { Position(char *n_name) : name(n_name), nr_needed(1), nr_vec_left(0) {} void setN(int nr) { nr_needed = nr; } char *name; int nr_needed; int nr_vec_left; }; struct Vectors { Vectors(Vector *v, Vectors *n) : vec(v), next(n) {} Vector *vec; Vectors *next; }; private: Node root; int nr_pos; int nr_vec; int nr_impossible_pos; long nr_calls_to_solve; 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(); if (node->position->nr_vec_left-- == node->position->nr_needed) nr_impossible_pos++; } } } void unignoreVector(Vector* vector, Position* exclude) { for (Node* node = vector->l; node != vector; node = node->l) { if (node->position != exclude) { node->swapin_vert(); if (++node->position->nr_vec_left == node->position->nr_needed) nr_impossible_pos--; } } 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) if (--node->position->nr_needed == 0) selectPosition(node->position, vector); else { node->swapout_vert(); node->position->nr_vec_left--; } } void unselectVector(Vector* vector) { for (Node* node = vector->l; node != vector; node = node->l) if (node->position->nr_needed++ == 0) unselectPosition(node->position, vector); else { node->position->nr_vec_left++; node->swapin_vert(); } vector->swapin_vert(); } void unignoreVectors(Vector* vector) { while (vector != 0) { Vector* next = vector->next_ignored; vector->next_ignored = 0; unignoreVector(vector, 0); vector = next; } } public: long int nr_solutions; long int sol_depth; private: Vector* sol_vectors; bool _solve() { nr_calls_to_solve++; // Found solution if there are no positions left if (root.r == &root) { nr_solutions++; for (Vector *vector = sol_vectors; vector != 0; vector = vector->next_selected) if (*vector->name != 0) fprintf(stdout, "%s|", vector->name); fprintf(stdout, "\n"); return false; } Vector *ignored_vectors = 0; for(;;) { // If there is a position that cannot be filled, then stop if (nr_impossible_pos > 0) { unignoreVectors(ignored_vectors); return false; } Position* best_pos = 0; int best_nr = 0; for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { int nr = position->nr_vec_left; if (position->nr_needed > 1) { int k = nr; for (int i = 2; i <= position->nr_needed; i++) nr = (nr * (--k)) / i; } if (nr == 1) { best_pos = position; best_nr = 1; break; } if (best_pos == 0 || position->nr_vec_left > best_nr) { best_pos = position; best_nr = position->nr_vec_left; } } if (best_nr == 0) { fprintf(stderr, "ERROR\n"); unignoreVectors(ignored_vectors); return false; } Vector* sel_vector = best_pos->d->vector; sel_vector->next_selected = sol_vectors; sol_vectors = sel_vector; selectVector(sel_vector); bool result = _solve(); unselectVector(sel_vector); sol_vectors = sel_vector->next_selected; sel_vector->next_selected = 0; if (result) { unignoreVectors(ignored_vectors); return true; } if (best_nr == 1) { unignoreVectors(ignored_vectors); return false; } sel_vector->next_ignored = ignored_vectors; ignored_vectors = sel_vector; ignoreVector(sel_vector, 0); } unignoreVectors(ignored_vectors); return false; } int steps; bool _solve_random() { nr_calls_to_solve++; // Found solution if there are no positions left if (root.r == &root) { nr_solutions++; sol_depth += steps; sol_found_in_periode++; return true; // true: stop searching } // If there is a position that cannot be filled, then stop if (nr_impossible_pos > 0) return false; int best_nr = 0; for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { int nr = 1; { int k = position->nr_vec_left;; for (int i = 1; i <= position->nr_needed; i++, k--) { nr *= k; nr /= i; } } if (best_nr == 0 || nr < best_nr) { best_nr = nr; if (best_nr == 1) break; } } if (best_nr == 0) { fprintf(stderr, "ERROR\n"); return false; } Vectors *best_vectors = 0; int nr_best_vectors = 0; for (Position *position = (Position*)root.r; position != &root; position = (Position*)position->r) { int nr = 1; { int k = position->nr_vec_left;; for (int i = 1; i <= position->nr_needed; i++, k--) { nr *= k; nr /= i; } } if (nr == best_nr) { for (Node* node = position->d; node != position; node = node->d) { bool already_included = false; for (Vectors* best_vector = best_vectors; best_vector != 0; best_vector = best_vector->next) if (best_vector->vec == node->vector) { already_included = true; break; } if (!already_included) { nr_best_vectors++; best_vectors = new Vectors(node->vector, best_vectors); } } } } int nr_sel = rand() % nr_best_vectors; Vector *sel_vector = 0; for (int i = 0; i < nr_best_vectors; i++) { if (i == nr_sel) sel_vector = best_vectors->vec; Vectors *next = best_vectors->next; delete best_vectors; best_vectors = next; } steps++; sel_vector->next_selected = sol_vectors; sol_vectors = sel_vector; selectVector(sel_vector); bool result = _solve_random(); unselectVector(sel_vector); sol_vectors = sel_vector->next_selected; sel_vector->next_selected = 0; if (result) return true; steps++; ignoreVector(sel_vector, 0); result = _solve_random(); unignoreVector(sel_vector, 0); return result; } public: Position *newPosition(char *name) { Position *position = new Position(name); root.push_back(position); nr_impossible_pos++; return position; } Vector *newVector(char *name) { nr_vec++; Vector *vector = new Vector(name); root.push_bottom(vector); return vector; } void add(Vector *vector, Position *position) { Node *node = new Node(); position->push_bottom(node); vector->push_back(node); node->vector = vector; node->position = position; if (++position->nr_vec_left == position->nr_needed) nr_impossible_pos--; } void solve() { nr_solutions = 0; _solve(); } void solve_random(int sec) { nr_solutions = 0; sol_depth = 0; clock_t till = clock() + sec * CLOCKS_PER_SEC; while (clock() < till) { steps = 0; sol_vectors = 0; _solve_random(); } } };