#include #include #include #include #include typedef unsigned char byte; class Alarm { public: Alarm() : _alarm_time(0), _went_off(false) {} void set_alarm(long seconds) { if (seconds == 0) _alarm_time = 0; else _alarm_time = clock() + CLK_TCK * seconds; _went_off = false; } void clear_alarm() { _alarm_time = 0; _went_off = false; } bool alarm() { if (_alarm_time > 0 && clock() > _alarm_time) { _went_off = true; } return _went_off; } bool went_off() { return _went_off; } private: clock_t _alarm_time; bool _went_off; }; #define MAX_SIZE 100 #define MAX_SIZE_D8 ((MAX_SIZE+7)/8) struct Need { void reset() { _need = 0; } bool needed(int type) { return (_need & (1 << type)) == 0; } void done(int type) { _need |= (1 << type); } private: int _need; }; struct Piece { int size; int min; int max; bool pos[MAX_SIZE]; void clear(int size) { min = size; max = 0; } bool empty() { return min >= max; } void init(int p, int s) { min = p; max = p + s; for (int i = 0; i < MAX_SIZE; i++) pos[i] = min <= i && i < max; } void assign(const Piece& p) { size = p.size; min = p.min; max = p.max; for (int i = 0; i < MAX_SIZE; i++) pos[i] = p.pos[i]; } void update(const Piece& p, bool& changed) { min = p.min; max = p.max; for (int i = 0; i < MAX_SIZE; i++) if (pos[i] && !p.pos[i]) { pos[i] = false; changed = true; } } bool reset(int i) { if (pos[i]) { pos[i] = false; if (i == min) { min++; while (min < max && !pos[min]) min++; } else if (i == max-1) { max--; while (min < max && !pos[max-1]) max--; } } return min < max; } bool limit_min(int i) { while (min < i && min < max) reset(min); return min < max; } bool limit_max(int i) { while (i < max && min < max) reset(max-1); return min < max; } bool set(int i) { pos[i] = true; if (i < min) min = i; if (i+1 > max) max = i+1; } }; struct Pieces { int nr; Piece pieces[MAX_SIZE]; Need need; void add(int v) { pieces[nr++].size = v; } void init(int size) { need.reset(); int sum = 0; for (int i = 0; i < nr; i++) sum += pieces[i].size; int left = size - (sum + nr - 1); if (left < 0) left = 0; int p = 0; for (int i = 0; i < nr; i++) { pieces[i].init(p, left+1); p += pieces[i].size + 1; } } void assign(const Pieces& ps) { need.reset(); nr = ps.nr; for (int i = 0; i < nr; i++) pieces[i].assign(ps.pieces[i]); } void update(const Pieces& ps, bool changed) { for (int i = 0; i < nr; i++) pieces[i].update(ps.pieces[i], changed); } }; int n; int m; int nm; #define UNKNOWN '?' #define FULL '*' #define EMPTY '_' struct TreeNode { TreeNode() : next(0), expanded(false), first_child(0) { for (int i = 0; i < MAX_SIZE_D8; i++) _line[i] = 0; } void remove(int& nr_nodes) { nr_nodes--; for (TreeNode* child = first_child; child != 0;) { TreeNode* old_child = child; child = child->next; old_child->remove(nr_nodes); } delete this; } char get(int i) { return _line[i/8] & (1 << (i%8)) ? FULL : EMPTY; } void set(int i, char val) { if (val == FULL) _line[i/8] |= (1 << (i%8)); } TreeNode* next; bool expanded; TreeNode* first_child; private: byte _line[MAX_SIZE_D8]; }; class Clues; struct Tree { Tree() : root(new TreeNode()), nr_filled(0), nr_nodes(0) {} Tree(const Tree& tree) : root(tree.root), nr_filled(0), nr_nodes(0) {} TreeNode* root; int nr_filled; int nr_nodes; int max_nr_nodes; bool full() { return nr_nodes >= max_nr_nodes; } bool changed; void assign(const Tree& tree) { root = tree.root; } virtual int pos(int level) const = 0; virtual int off() const = 0; virtual int size() const = 0; virtual int rowcol(int level) const = 0; virtual char* rowcolname() const = 0; virtual const Pieces& pieces(Clues &clues, int rowcol) const = 0; }; struct DownTree : public Tree { virtual int pos(int level) const { return level; } virtual int off() const { return n; } virtual int size() const { return m; } virtual int rowcol(int level) const { return level; } virtual char* rowcolname() const { return "rij"; } virtual const Pieces& pieces(Clues &clues, int rowcol) const; }; struct LeftTree : public Tree { virtual int pos(int level) const { return n*level; } virtual int off() const { return 1; } virtual int size() const { return n; } virtual int rowcol(int level) const { return level; } virtual char* rowcolname() const { return "kol"; } virtual const Pieces& pieces(Clues &clues, int rowcol) const; }; struct UpTree : public Tree { virtual int pos(int level) const { return (n-1)-level; } virtual int off() const { return n; } virtual int size() const { return m; } virtual int rowcol(int level) const { return (n-1)-level; } virtual char* rowcolname() const { return "rij"; } virtual const Pieces& pieces(Clues &clues, int rowcol) const; }; struct RightTree : public Tree { virtual int pos(int level) const { return n*((m-1)-level); } virtual int off() const { return 1; } virtual int size() const { return n; } virtual int rowcol(int level) const { return (m-1)-level; } virtual char* rowcolname() const { return "kol"; } virtual const Pieces& pieces(Clues &clues, int rowcol) const; }; struct Clues { Pieces row[MAX_SIZE]; Pieces col[MAX_SIZE]; DownTree down_tree; LeftTree left_tree; UpTree up_tree; RightTree right_tree; void assign(const Clues& clues) { for (int i = 0; i < n; i++) row[i].assign(clues.row[i]); for (int i = 0; i < m; i++) col[i].assign(clues.col[i]); down_tree.root = clues.down_tree.root; left_tree.root = clues.left_tree.root; up_tree.root = clues.up_tree.root; right_tree.root = clues.right_tree.root; } }; const Pieces& DownTree::pieces(Clues &clues, int rowcol) const { return clues.row[rowcol]; } const Pieces& LeftTree::pieces(Clues &clues, int rowcol) const { return clues.col[rowcol]; } const Pieces& UpTree::pieces(Clues &clues, int rowcol) const { return clues.row[rowcol]; } const Pieces& RightTree::pieces(Clues &clues, int rowcol) const { return clues.col[rowcol]; } struct Board { Need rowneeds[MAX_SIZE]; Need colneeds[MAX_SIZE]; int nr_unknown; char operator[](const int i) const { return _b[i]; } void clear() { for (int i = 0; i < nm; i++) _b[i] = UNKNOWN; nr_unknown = nm; } void copy(const Board& board) { for (int i = 0; i < nm; i++) _b[i] = board._b[i]; nr_unknown = board.nr_unknown; resetneeds(); } void clone(const Board& board) { for (int i = 0; i < nm; i++) if (board._b[i] == UNKNOWN) _b[i] = ' '; else _b[i] = board._b[i]; nr_unknown = 0; resetneeds(); } void assign(const int i, const int v) { if (v == UNKNOWN) { if (_b[i] != UNKNOWN) nr_unknown++; } else { if (_b[i] == UNKNOWN) nr_unknown--; } _b[i] = v; } void combine(const int i, const int v) { if (_b[i] == ' ') { _b[i] = v; if (v == UNKNOWN) nr_unknown++; } else if (_b[i] != v && _b[i] != UNKNOWN) { _b[i] = UNKNOWN; nr_unknown++; } } void combine(const Board& board) { for (int i = 0; i < nm; i++) combine(i, board[i]); } void intergrate(const int i, const int val, int &modified) { if (_b[i] == UNKNOWN && (val == FULL || val == EMPTY)) { modified++; _b[i] = val; rowneeds[i%n].reset(); colneeds[i/n].reset(); nr_unknown--; } } void intergrate(const Board& board, int &modified) { for (int i = 0; i < nm; i++) intergrate(i, board[i], modified); } void resetneeds() { for (int i = 0; i < MAX_SIZE; i++) { rowneeds[i].reset(); colneeds[i].reset(); } } int count_unknown() { int result = 0; for (int i = 0; i < nm; i++) if (_b[i] == UNKNOWN) result++; return result; } private: char _b[MAX_SIZE*MAX_SIZE]; }; void read_line(FILE* f, char *line, bool &more) { if (fgets(line, 299, f) == 0) { more = false; return; } if (line[strlen(line)-1] == '\n') line[strlen(line)-1] = '\0'; more = true; } bool read_clues(char *fn, Clues &clues) { FILE* f = fopen(fn, "rt"); char line[300]; bool more; read_line(f, line, more); while (more && strncmp(line, "width ", 6) != 0) read_line(f, line, more); if (!more) { fclose(f); return false; } m = atoi(line+6); read_line(f, line, more); while (more && strncmp(line, "height ", 7) != 0) read_line(f, line, more); if (!more) { fclose(f); return false; } n = atoi(line+7); read_line(f, line, more); while (more && strcmp(line, "rows") != 0) read_line(f, line, more); if (!more) { fclose(f); return false; } for (int i = 0; i < n; i++) { read_line(f, line, more); if (!more) { fclose(f); return false; } clues.row[i].nr = 0; int sum = 0; if (strcmp(line, "0") != 0) { char *s = line; while (*s != '\0') { int v = 0; for (; isdigit(*s); s++) v = 10 * v + *s - '0'; for(; *s == ',' || *s == ' '; s++) ; clues.row[i].add(v); } } clues.row[i].init(m); } read_line(f, line, more); while (more && strcmp(line, "columns") != 0) read_line(f, line, more); if (!more) { fclose(f); return false; } for (int i = 0; i < m; i++) { read_line(f, line, more); if (!more) { fclose(f); return false; } clues.col[i].nr = 0; int k = 0; if (strcmp(line, "0") != 0) { char *s = line; while (*s != '\0') { int v = 0; for (; isdigit(*s); s++) v = 10 * v + *s - '0'; for(; *s == ',' || *s == ' '; s++) ; clues.col[i].add(v); } } clues.col[i].init(n); } nm = n * m; fclose(f); return true; } void write_pieces(const Clues& clues) { for (int i = 0; i < n; i++) { printf("row %d:", i+1); const Pieces& ps = clues.row[i]; for (int j = 0; j < ps.nr; j++) { const Piece& p = ps.pieces[j]; printf(" %d (%d %d)", p.size, p.min, p.max); } printf("\n"); } for (int i = 0; i < m; i++) { printf("col %d:", i+1); const Pieces& ps = clues.col[i]; for (int j = 0; j < ps.nr; j++) { const Piece& p = ps.pieces[j]; printf(" %d (%d %d)", p.size, p.min, p.max); } printf("\n"); } } void read_prev_board(Board &board) { FILE *f = fopen("frans.prev_sol", "rt"); if (f == 0) { printf("cannot open file 'frans.prev_sol'\n"); return; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char ch = (char)fgetc(f); if (ch != FULL && ch != EMPTY && ch != UNKNOWN) goto error; board.assign(i+n*j, ch); } char ch = (char)fgetc(f); if (ch != '\n') goto error; } fclose(f); printf("continue with:\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) printf("%c", board[i+n*j]); printf("\n"); } return; error: fclose(f); board.clear(); } void printsol(Board &board) { rename("frans.sol", "frans.sol2"); FILE *g = fopen("frans.sol", "w"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) fprintf(g, "%c", board[i+n*j]); fprintf(g,"\n"); } fclose(g); } void dumpboard(Board &board) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) printf("%c", board[i+n*j]); printf("\n"); } } #define HOT 3 void dump(char* msg, char *line, int size, Pieces &ps) { printf("%s ", msg); for (int i = 0; i < size; i++) printf("%c", line[i]); printf(" "); for (int i = 0; i < ps.nr; i++) printf(" %d (%d-%d)", ps.pieces[i].size, ps.pieces[i].min, ps.pieces[i].max); printf("\n"); } bool reason(char *line, int size, Pieces &ps) { for (bool go = true; go; ) { go = false; bool notempty[MAX_SIZE]; for (int i = 0; i < size; i++) notempty[i] = false; for (int i = 0; i < ps.nr; i++) { Piece& p = ps.pieces[i]; for (int j = p.min; j < p.max; j++) if (p.pos[j]) { int e = j + p.size; bool possible = (j == 0 || line[j-1] != FULL) && (e == size || line[e] != FULL); for (int k = 0; k < p.size && possible; k++) if (line[j+k] == EMPTY) possible = false; if (possible) { for (int k = 0; k < p.size; k++) notempty[j+k] = true; } else { go = true; if (!p.reset(j)) { //printf("x1\n"); return false; } #ifdef DEBUG_REASON printf("piece %d: %d impossible: %d-%d\n", i, j, p.min, p.max); #endif } } } for (int i = 1; i < ps.nr; i++) { int min = ps.pieces[i-1].min + ps.pieces[i-1].size + 1; Piece& p = ps.pieces[i]; if (min > p.min) { if (!p.limit_min(min)) { //printf("x2\n"); return false; } go = true; #ifdef DEBUG_REASON printf("piece %d: limit min %d: %d-%d\n", i, min, p.min, p.max); #endif } } for (int i = ps.nr - 2; i >= 0; i--) { int max = ps.pieces[i+1].max - ps.pieces[i].size - 1; Piece& p = ps.pieces[i]; if (max < p.max) { if (!p.limit_max(max)) { //printf("piece %d: limit max %d: %d-%d\n", i, max, p.min, p.max); //printf("x3\n"); return false; } go = true; #ifdef DEBUG_REASON printf("piece %d: limit max %d: %d-%d\n", i, max, p.min, p.max); #endif } } for (int i = 0; i < ps.nr; i++) { Piece& p = ps.pieces[i]; bool pp = false; for (int k = p.max - 1; k < p.min + p.size; k++) { if (line[k] == EMPTY) { //printf("x4\n"); return false; } if (line[k] != FULL) { line[k] = FULL; go = true; #ifdef DEBUG_REASON if (!pp) printf("line FULL"); pp = true; printf(" %d", k); #endif } } #ifdef DEBUG_REASON if (pp) printf("\n"); #endif } bool pp = false; for (int i = 0; i < size; i++) if (!notempty[i]) { if (line[i] == FULL) { //printf("x5\n"); return false; } if (line[i] != EMPTY) { line[i] = EMPTY; go = true; #ifdef DEBUG_REASON if (!pp) printf("line EMPTY"); pp = true; printf(" %d", i); #endif } } #ifdef DEBUG_REASON if (pp) printf("\n"); #endif if (!go) { for (int i = 0; i < size; i++) if (line[i] == FULL) { char tline[MAX_SIZE]; int nr_pieces_overlap = 0; int nr_piece_overlap; for (int j = 0; j < size; j++) tline[j] = UNKNOWN; for (int j = 0; j < ps.nr; j++) { Piece& p = ps.pieces[j]; for (int k = p.min; k < p.max; k++) if (p.pos[k] && k <= i && i < k+p.size) { if (nr_pieces_overlap == 0 || nr_piece_overlap != j) { nr_pieces_overlap++; nr_piece_overlap = j; } for (int l = 0; l < k-1; l++) tline[l] = ' '; if (k > 0) { if (tline[k-1] == UNKNOWN) tline[k-1] = EMPTY; else if (tline[k-1] != EMPTY) tline[k-1] = ' '; } for (int l = 0; l < p.size; l++) { if (tline[k+l] == UNKNOWN) tline[k+l] = FULL; else if (tline[k+l-1] != FULL) tline[k+l] = ' '; } if (k + p.size < size) { if (tline[k + p.size] == UNKNOWN) tline[k + p.size] = EMPTY; else if (tline[k + p.size] != EMPTY) tline[k + p.size] = ' '; } for (int l = k + p.size + 1; l < size; l++) tline[l] = ' '; } } bool pp = false; for (int j = 0; j < size; j++) { #ifdef DEBUG_REASON if (!pp && line[j] == UNKNOWN && (tline[j] == FULL || tline[j] == EMPTY)) { printf("now: "); for (int k = 0; k < size; k++) printf("%c", line[k]); printf("\nnew: "); for (int k = 0; k < size; k++) printf("%c", tline[k]); printf("\nchanges: "); pp = true; } #endif if (tline[j] == FULL) { if (line[j] == EMPTY) { //printf("x6\n"); return false; } if (line[j] == UNKNOWN) { line[j] = FULL; go = true; #ifdef DEBUG_REASON printf(" %d FULL", j); #endif } } else if (tline[j] == EMPTY) { if (line[j] == FULL) { //printf("x7\n"); return false; } if (line[j] == UNKNOWN) { line[j] = EMPTY; go = true; #ifdef DEBUG_REASON printf(" %d EMPTY", j); #endif } } } #ifdef DEBUG_REASON if (pp) printf("\n"); #endif if (nr_pieces_overlap == 1) { Piece& p = ps.pieces[nr_piece_overlap]; for (int k = p.min; k < p.max; k++) if (p.pos[k] && !(k <= i && i < k+p.size)) { p.reset(k); go = true; } } } } #ifdef DEBUG_REASON if (go) dump("result ", line, size, ps); #endif } return true; } bool reason(char *rowcol, int nr, Board &board, int pos, int off, int size, Pieces& pieces, int& modified) { #ifdef DEBUG_REASON printf("%s%d\n", rowcol, nr); #endif char line[MAX_SIZE]; for (int i = 0; i < size; i++) line[i] = board[pos + off*i]; Pieces ps; ps.assign(pieces); if (!reason(line, size, ps)) return false; for (int i = 0; i < size; i++) board.intergrate(pos + off*i, line[i], modified); bool changed = false; pieces.update(ps, changed); if (changed) { modified++; } return true; } bool matches(const Clues &clues, const Board& board); bool guess_solve(Board &board, const Clues& clues) { static Clues guess_clues; guess_clues.assign(clues); board.resetneeds(); int modified; do { modified = 0; for (int i = 0; i < n; i++) if (board.rowneeds[i].needed(1) && !reason("rij", i+1, board, i, n, m, guess_clues.row[i], modified)) return false; else board.rowneeds[i].done(1); for (int j = 0; j < m; j++) if (board.colneeds[j].needed(1) && !reason("colom", j+1, board, j*n, 1, n, guess_clues.col[j], modified)) return false; else board.colneeds[j].done(1); //printf("\nguess modified = %d\n", modified); //printsol(board); } while (modified > 0); return matches(clues, board); } void guess_something(char *rowcol, int nr, const Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified) { printf("guess %s%d", rowcol, nr); bool reduced = false; for (int i = 0; i < pieces.nr && modified == 0; i++) { Piece& p = pieces.pieces[i]; printf(" %d", p.max - p.min); if (p.max - p.min > 1) { Board combined_guess_board; combined_guess_board.clone(board); bool found = false; for (int k = p.min; k < p.max; k++) if (p.pos[k]) { Board guess_board; guess_board.copy(board); if (k > 0) guess_board.assign(pos+off*(k-1), EMPTY); if (k + p.size < size) guess_board.assign(pos+off*(k + p.size), EMPTY); for (int l = 0; l < p.size; l++) guess_board.assign(pos+off*(k + l), FULL); if (guess_solve(guess_board, clues)) { found = true; combined_guess_board.combine(guess_board); if (combined_guess_board.nr_unknown == board.nr_unknown) break; } else { printf("%s%d impossible: %d at %d\n", rowcol, nr, i, k); p.reset(k); reduced = true; } } if (found && combined_guess_board.nr_unknown < board.nr_unknown) board.intergrate(combined_guess_board, modified); } } if (reduced) reason(rowcol, nr, board, pos, off, size, pieces, modified); printf("\n"); } class PiecesCombinationsIterator { public: PiecesCombinationsIterator(const Pieces& pieces, int size) : _pieces(pieces), _size(size) { for (int i = 0; i < _pieces.nr; i++) positions[i] = _pieces.pieces[i].min; _more = true; } bool more() { return _more; } void next() { for (int i = 0; i < _pieces.nr; i++) { const Piece& p = _pieces.pieces[i]; int end = p.max; if (i+1 < _pieces.nr) { int j = positions[i+1] - p.size; if (j < end) end = j; } for (int j = positions[i]+1; j < end; j++) if (p.pos[j]) { positions[i] = j; return; } positions[i] = p.min; } _more = false; } int positions[MAX_SIZE]; private: const Pieces& _pieces; int _size; bool _more; }; void try_all_combinations(char *rowcol, int nr, Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified, long& rfound) { printf("try_all_combinations %s%d", rowcol, nr); Pieces try_pieces; try_pieces.nr = pieces.nr; for (int i = 0; i < size; i++) try_pieces.pieces[i].clear(size); Board combined_try_board; combined_try_board.clone(board); #if 0 printf("\n"); for (int i = 0; i < size; i++) printf("%c", board[pos + off*i]); printf("\n"); #endif int tried = 0; int found = 0; for (PiecesCombinationsIterator it(pieces, size); it.more(); it.next()) { Board try_board; try_board.copy(board); int j = 0; for (int i = 0; i < pieces.nr; i++) { int begin = it.positions[i]; int end = begin + pieces.pieces[i].size; for (; j < begin; j++) try_board.assign(pos + off*j, EMPTY); for (; j < end; j++) try_board.assign(pos + off*j, FULL); } for (; j < size; j++) try_board.assign(pos + off*j, EMPTY); tried++; if (guess_solve(try_board, clues)) { combined_try_board.combine(try_board); for (int i = 0; i < pieces.nr; i++) try_pieces.pieces[i].set(it.positions[i]); #if 0 for (int i = 0; i < size; i++) printf("%c", try_board[pos + off*i]); printf("\n"); #endif found++; } } printf(" tried %d found %d", tried, found); if (found > 0) { int mod = 0; board.intergrate(combined_try_board, mod); modified += mod; } printf(" modified %d", modified); //#ifdef SHOW_SOLVING // printf("%s %2d: ", rowcol, nr); // if (mod) // { // for (int j = 0; j < size; j++) // printf("%c", board[pos + off * j]); // } // printf(" %d (%d)\n", mod, found); //#endif rfound = found; bool changed = false; pieces.update(try_pieces, changed); printf(" changed %d", changed); if (changed) { printf("\n"); for (int i = 0; i < pieces.nr; i++) { Piece& p = try_pieces.pieces[i]; printf("-- %d: %d-%d", i, p.min, p.max); for (int k = p.min; k < p.max; k++) if (p.pos[k]) printf(" %d", k); printf("\n"); } modified++; } printf("\n"); } ////// struct Combination { char rc; int i; int d; int side; long max; long nr; }; int compare_max(const void* vl, const void* vr) { Combination *l = (Combination*)vl; Combination *r = (Combination*)vr; if (l->max < r->max) return -1; if (l->max > r->max) return 1; if (l->d < r->d) return -1; if (l->d > r->d) return 1; if (l->side < r->side) return -1; if (l->side > r->side) return 1; if (l->rc > r->rc) return -1; if (l->rc < r->rc) return 1; if (l->i < r->i) return -1; if (l->i > r->i) return 1; return 0; } long calc_max_combinations(const Pieces& pieces) { long result = 1; for (int i = 0; i < pieces.nr; i++) { const Piece& p = pieces.pieces[i]; int nr = 0; for (int j = p.min; j < p.max; j++) if (p.pos[j]) nr++; result *= nr; if (result > 1000000) return 1000000; } return result; } void try_all_on_off(char *rowcol, int nr, const Clues& clues, Board &board, int pos, int off, int size, Pieces& pieces, int& modified) { printf("try_all_on_off"); for (int l = 0; l < m; l++) { int i = pos + off*l; if (board[i] == UNKNOWN) { Board combined_guesses; combined_guesses.clone(board); bool found = false; Board guess_board; guess_board.copy(board); guess_board.assign(i, FULL); if (guess_solve(guess_board, clues)) { combined_guesses.combine(guess_board); found = true; } guess_board.copy(board); guess_board.assign(i, EMPTY); if (guess_solve(guess_board, clues)) { combined_guesses.combine(guess_board); found = true; } if (found) { board.intergrate(combined_guesses, modified); } char s = board[i]; printf("%c", s == EMPTY ? 'E' : s == FULL ? 'F' : '?'); } else printf("%c", board[i]); } } char vals[1000]; #define SEARCH_MODE_NORMAL '-' #define SEARCH_MODE_FIRST '1' #define SEARCH_MODE_COUNTER 'C' Alarm try_alarm; bool try_all_in_square(int i, int j, int i_min, int i_max, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode, int depth) { if (j == j_max) { found = true; combined_try_board.combine(try_board); //printf("."); int n_unknown = combined_try_board.nr_unknown; //printf("\n%d ", n_unknown); //vals[depth] = '\0'; //printf("%s %c", vals, search_mode); printf("\n%c", search_mode); if (n_unknown > nr_unknown) printf(" ***** %d", combined_try_board.count_unknown()); return n_unknown < nr_unknown; } if (try_alarm.alarm()) { return false; } int next_i = i + 1; int next_j = j; if (next_i == i_max) { next_i = i_min; next_j++; } int inj = i+n*j; if (try_board[inj] != UNKNOWN) { vals[depth] = try_board[inj]; return try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, try_board, nr_unknown, found, search_mode, depth+1); } char first = EMPTY; char second = FULL; if (search_mode == SEARCH_MODE_COUNTER && combined_try_board[inj] == EMPTY) { first = FULL; second = EMPTY; } Board next_try_board; next_try_board.copy(try_board); next_try_board.assign(inj, first); if (guess_solve(next_try_board, clues)) { vals[depth] = first; //printf("%c", 'a'+depth); if (!try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode, depth+1)) return false; } if (search_mode != SEARCH_MODE_NORMAL && found) return true; next_try_board.copy(try_board); next_try_board.assign(inj, second); if (guess_solve(next_try_board, clues)) { vals[depth] = second; //printf("%c", 'a'+depth); if (!try_all_in_square(next_i, next_j, i_min, i_max, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode, depth+1)) return false; } return true; } int times_called; bool try_all_in_square_slow(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode) { times_called++; // scan all int still_unknown = 0; int first_unknown_inj; for (int i = i_min; i < i_max; i++) for (int j = j_min; j < j_max; j++) { int inj = i+n*j; if (try_board[inj] == UNKNOWN) { Board next_try_board; next_try_board.copy(try_board); next_try_board.assign(inj, EMPTY); bool empty_possible = guess_solve(next_try_board, clues); next_try_board.copy(try_board); next_try_board.assign(inj, FULL); bool full_possible = guess_solve(next_try_board, clues); //printf(" %d,%d %c%c", i,j, empty_possible ? 'E' : '_', full_possible ? 'F' : '_'); if (empty_possible) { if (full_possible) { if (still_unknown == 0) { first_unknown_inj = inj; } still_unknown++; } else try_board.assign(inj, EMPTY); } else { if (full_possible) try_board.assign(inj, FULL); else return true; // no solution possible } } } //printf(" still_unknown %d\n", still_unknown); if (still_unknown == 0) { // We found a solution found = true; combined_try_board.combine(try_board); //printf("."); int n_unknown = combined_try_board.nr_unknown; //printf("\n%d ", n_unknown); //vals[depth] = '\0'; //printf("%s %c", vals, search_mode); printf("\n%c", search_mode); if (n_unknown > nr_unknown) printf(" ***** %d", combined_try_board.count_unknown()); return n_unknown < nr_unknown; } int inj = first_unknown_inj; char first = EMPTY; char second = FULL; if (search_mode == SEARCH_MODE_COUNTER && combined_try_board[inj] == EMPTY) { first = FULL; second = EMPTY; } Board next_try_board; next_try_board.copy(try_board); next_try_board.assign(inj, first); if (guess_solve(next_try_board, clues)) { //vals[depth] = first; //printf("%c", 'a'+depth); if (!try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode)) return false; } if (search_mode != SEARCH_MODE_NORMAL && found && (search_mode != SEARCH_MODE_COUNTER || nr_unknown > 2)) return true; next_try_board.copy(try_board); next_try_board.assign(inj, second); if (guess_solve(next_try_board, clues)) { //vals[depth] = second; //printf("%c", 'a'+depth); if (!try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, next_try_board, nr_unknown, found, search_mode)) return false; } return true; } bool try_all_in_square_find_one(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, Board &try_board, int nr_unknown, bool &found, char search_mode) { try_alarm.set_alarm(3); if (try_all_in_square(i_min, j_min, i_min, i_max, j_max, clues, combined_try_board, try_board, nr_unknown, found, search_mode, 0)) return true; if (try_alarm.went_off()) { Board copy_try_board; copy_try_board.copy(try_board); times_called = 0; bool result = try_all_in_square_slow(i_min, i_max, j_min, j_max, clues, combined_try_board, copy_try_board, nr_unknown, found, search_mode); printf(" times_called = %d", times_called); return result; } return false; } bool try_all_in_square_counter(int i_min, int i_max, int j_min, int j_max, const Clues& clues, Board &combined_try_board, const Board &board, int nr_unknown, bool &found) { for (int i = i_min; i < i_max; i++) for (int j = j_min; j < j_max; j++) { int inj = i+n*j; if (board[inj] == UNKNOWN && combined_try_board[inj] != UNKNOWN) { Board try_board; try_board.copy(board); try_board.assign(inj, combined_try_board[inj] == FULL ? EMPTY : FULL); if (guess_solve(try_board, clues)) { bool try_found = false; bool result = try_all_in_square_find_one(i_min, i_max, j_min, j_max, clues, combined_try_board, try_board, nr_unknown, try_found, SEARCH_MODE_COUNTER); if (try_found) found = true; if (!result) return false; } } } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int inj = i+n*j; if ( combined_try_board[inj] != UNKNOWN && board[inj] == UNKNOWN && (i < i_min || i_max <= i || j < j_min || j_max <= j)) { Board try_board; try_board.copy(board); try_board.assign(inj, combined_try_board[inj] == FULL ? EMPTY : FULL); if (guess_solve(try_board, clues)) { bool try_found = false; bool result = try_all_in_square_find_one(i_min, i_max, j_min, j_max, clues, combined_try_board, try_board, nr_unknown, try_found, SEARCH_MODE_COUNTER); if (try_found) found = true; if (!result) return false; } } } return true; } void try_all_in_square(int unknowns, int nsize, int msize, const Clues& clues, Board &board, int &modified) { if (unknowns > nsize * msize) return; for (int j = 0; j < m - msize + 1; j++) for (int i = 0; i < n - nsize + 1; i++) { int cu = 0; for (int i1 = 0; i1 < nsize; i1++) for (int j1 = 0; j1 < msize; j1++) if (board[(i+i1)+n*(j+j1)] == UNKNOWN) cu++; if (unknowns == cu) { printf("%d: try_all_in_square(%2d-%2d, %2d-%2d) %d ", unknowns, i, i+nsize-1, j, j+nsize-1, board.nr_unknown); Board combined_try_board; combined_try_board.clone(board); Board try_board; try_board.copy(board); bool found = false; if ( try_all_in_square_find_one(i, i+nsize, j, j+msize, clues, combined_try_board, try_board, board.nr_unknown, found, SEARCH_MODE_FIRST) && found && try_all_in_square_counter(i, i+nsize, j, j+msize, clues, combined_try_board, board, board.nr_unknown, found)) { board.intergrate(combined_try_board, modified); } printf("\n"); } } } void solve_tree(Clues &clues, Board& board, int &modified, int max_nr_nodes); bool solve(Clues &clues, Board &board) { fprintf(stderr, "solve\n"); int l = 0; int modified; int max_nr_nodes = 0; do { modified = 0; for (int i = 0; i < n; i++) if (board.rowneeds[i].needed(1) && !reason("rij", i+1, board, i, n, m, clues.row[i], modified)) return false; else board.rowneeds[i].done(1); for (int j = 0; j < m; j++) if (board.colneeds[j].needed(1) && !reason("colom", j+1, board, j*n, 1, n, clues.col[j], modified)) return false; else board.colneeds[j].done(1); if (modified > 0) l = 0; if (modified == 0) { #if 0 Combination combinations[2*MAX_SIZE]; for (int i = 0; i < n; i++) { combinations[i].rc = 'r'; combinations[i].i = i; if (i < n-i) { combinations[i].d = i; combinations[i].side = 1; } else { combinations[i].d = n-i; combinations[i].side = 3; } combinations[i].max = calc_max_combinations(clues.row[i]); combinations[i].nr = combinations[i].max; } for (int i = 0; i < m; i++) { combinations[n+i].rc = 'c'; combinations[n+i].i = i; if (i < m-i) { combinations[n+i].d = i; combinations[n+i].side = 2; } else { combinations[n+i].d = m-i; combinations[n+i].side = 4; } combinations[n+i].max = calc_max_combinations(clues.col[i]); combinations[n+i].nr = combinations[n+i].max; } qsort(combinations, n+m, sizeof(Combination), compare_max); for (int j = 0; j < n+m && modified == 0; j++) { int i = combinations[j].i; if (combinations[j].rc == 'r') { guess_something("rij", i+1, clues, board, i, n, m, clues.row[i], modified); //if (modified == 0) // try_all_on_off("rij", i+1, clues, board, i, n, m, clues.row[i], modified); } else { guess_something("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified); //if (modified == 0) // try_all_on_off("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified); } } for (int j = 0; j < n+m && modified == 0; j++) { if (combinations[j].max > 1 && combinations[j].max < 1000) { printf("%c%d: %ld\n", combinations[j].rc, combinations[j].i, combinations[j].max); int i = combinations[j].i; if (combinations[j].rc == 'r') try_all_combinations("rij", i+1, clues, board, i, n, m, clues.row[i], modified, combinations[j].nr); else try_all_combinations("colom", i+1, clues, board, i*n, 1, n, clues.col[i], modified, combinations[i].nr); } } for (int unknowns = 2; modified == 0 && unknowns <= 25; unknowns++) { try_all_in_square(unknowns, 5, 5, clues, board, modified, 0); /* if (modified == 0) try_all_in_square(unknowns, 2, 2, clues, board, modified); if (modified == 0) try_all_in_square(unknowns, 3, 3, clues, board, modified); if (modified == 0) try_all_in_square(unknowns, 4, 4, clues, board, modified); if (modified == 0) try_all_in_square(unknowns, 5, 5, clues, board, modified); if (modified == 0) try_all_in_square(unknowns, 6, 6, clues, board, modified); if (modified == 0) try_all_in_square(unknowns, 7, 7, clues, board, modified); */ } for (int unknowns = 2; modified == 0 && unknowns <= 49; unknowns++) { try_all_in_square(unknowns, 7, 7, clues, board, modified); } for (int unknowns = 2; modified == 0 && unknowns <= 100; unknowns++) { try_all_in_square(unknowns, 10, 10, clues, board, modified); } static int first_time_start_at = 180; for (int unknowns = first_time_start_at; modified == 0 && unknowns <= 196; unknowns++) { try_all_in_square(unknowns, 14, 14, clues, board, modified); } first_time_start_at = 2; #endif if (modified == 0) { max_nr_nodes += 1000; solve_tree(clues, board, modified, max_nr_nodes); } if (modified > 0) { board.resetneeds(); } } /* for (; modified == 0 && l < MAX_SIZE; l++) { if (2*l <= n) guess_something("rij", l+1, clues, board, l, n, m, clues.row[l], hotcol, modified); if (2*l < n) guess_something("rij", (n-l-1)+1, clues, board, (n-l-1), n, m, clues.row[(n-l-1)], hotcol, modified); if (2*l <= m) guess_something("colom", l+1, clues, board, l*n, 1, n, clues.col[l], hotrow, modified); if (2*l < m) guess_something("colom", (m-l-1)+1, clues, board, (m-l-1)*n, 1, n, clues.col[(m-l-1)], hotrow, modified); if (modified > 0) { for (int i = 0; i < n; i++) hotrow[i] = HOT; for (int j = 0; j < m; j++) hotcol[j] = HOT; } } */ printf("\nmodified = %d\n", modified); printsol(board); //dumpboard(board); } while (modified > 0); return true; } Clues clues; Board board; int main(int argc, char *argv[]) { if (!read_clues("frans.nono", clues)) { printf("\n\nread error\n"); return 0; } //write_pieces(clues); board.clear(); read_prev_board(board); if (!solve(clues, board)) printf("\nNo solution\n"); printf("\n\ndone\n"); return 0; } bool expand_tree(Clues &clues, const Board& board, TreeNode* node, Tree* tree, int cur_level, int level, Board& combined_guess_board) { int pos = tree->pos(cur_level); int off = tree->off(); int rowcol = tree->rowcol(cur_level); int size = tree->size(); //printf("%*.*s%s %d\n", cur_level*2, cur_level*2, "", tree->rowcolname(), rowcol); if (node->expanded) { for (TreeNode** ref_child = &node->first_child; *ref_child != 0; ) { TreeNode* child = *ref_child; //printf("%*.*s- child: ", cur_level*2, cur_level*2, ""); Board try_board; try_board.copy(board); bool possible = true; for (int j = 0; j < size; j++) { if (board[pos + off*j] == UNKNOWN) { try_board.assign(pos + off*j, child->get(j)); } else if (board[pos + off*j] != child->get(j)) { possible = false; break; } } //if (!possible) // printf("not possible\n"); if (possible) { //for (int j = 0; j < size; j++) // printf("%c", try_board[pos + off*j]); //printf(" "); if (cur_level == level) { possible = guess_solve(try_board, clues); if (possible) { combined_guess_board.combine(try_board); } //printf("guess_solve: %s\n", possible ? "possible" : "not possible"); } else { //printf("deeper\n"); possible = expand_tree(clues, try_board, child, tree, cur_level+1, level, combined_guess_board); //printf("%*.*s result: %s\n", cur_level*2, cur_level*2, "", possible ? "possible" : "not possible"); } } if (possible) ref_child = &child->next; else { *ref_child = child->next; child->remove(tree->nr_nodes); tree->changed = true; } } } else { // ASSERT cur_level == level if (tree->full()) { combined_guess_board.combine(board); return true; } const Pieces& pieces = tree->pieces(clues, rowcol); if (calc_max_combinations(pieces) > tree->max_nr_nodes) { combined_guess_board.combine(board); return true; } for (PiecesCombinationsIterator it(pieces, size); it.more(); it.next()) { Board try_board; try_board.copy(board); bool fits = true; int j = 0; for (int l = 0; l < pieces.nr && fits; l++) { int begin = it.positions[l]; int end = begin + pieces.pieces[l].size; for (; j < begin && fits; j++) if (try_board[pos + off*j] == FULL) fits = false; else try_board.assign(pos + off*j, EMPTY); for (; j < end && fits; j++) if (try_board[pos + off*j] == EMPTY) fits = false; else try_board.assign(pos + off*j, FULL); } for (; j < size && fits; j++) if (try_board[pos + off*j] == FULL) fits = false; else try_board.assign(pos + off*j, EMPTY); if (fits && guess_solve(try_board, clues)) { TreeNode* new_child = new TreeNode(); tree->nr_nodes++; tree->changed = true; combined_guess_board.combine(try_board); //printf("%*.*s- expand: ", cur_level*2, cur_level*2, ""); for (int j = 0; j < size; j++) { //printf("%c", try_board[pos + off*j]); new_child->set(j, try_board[pos + off*j]); } //printf("\n"); // found new //printf("\n"); //for (int j = 0; j < size; j++) // printf("%c", new_child->get(j)); //printf("\n"); new_child->next = node->first_child; node->first_child = new_child; } } node->expanded = true; } return node->first_child != 0; } void solve_tree(Clues &clues, Board& board, Tree* tree, int &modified) { for (int level = 0; level < n && !tree->full(); level++) { printf("\n\nExpand to level %d\n", level); Board try_board; try_board.copy(board); Board combined_guess_board; combined_guess_board.clone(board); expand_tree(clues, board, tree->root, tree, 0, level, combined_guess_board); if (combined_guess_board.nr_unknown < board.nr_unknown) board.intergrate(combined_guess_board, modified); if (tree->full()) return; printf("Nodes = %d\n", tree->nr_nodes); tree->nr_filled = level; } } void solve_tree(Clues &clues, Board& board, int &modified, int max_nr_nodes) { clues.down_tree.changed = false; clues.down_tree.max_nr_nodes = max_nr_nodes; solve_tree(clues, board, &clues.down_tree, modified); if (modified > 0) return; clues.left_tree.changed = false; clues.left_tree.max_nr_nodes = max_nr_nodes; solve_tree(clues, board, &clues.left_tree, modified); if (modified > 0) return; clues.up_tree.changed = false; clues.up_tree.max_nr_nodes = max_nr_nodes; solve_tree(clues, board, &clues.up_tree, modified); if (modified > 0) return; clues.right_tree.changed = false; clues.right_tree.max_nr_nodes = max_nr_nodes; solve_tree(clues, board, &clues.right_tree, modified); if (modified > 0) return; if ( clues.down_tree.changed || clues.left_tree.changed || clues.up_tree.changed || clues.right_tree.changed) modified = 1; } bool matches(const Board& board, const Tree* tree, const TreeNode* node, int cur_level) { if (!node->expanded) return true; int pos = tree->pos(cur_level); int off = tree->off(); int rowcol = tree->rowcol(cur_level); int size = tree->size(); for (TreeNode* child = node->first_child; child != 0; child = child->next) { bool possible = true; for (int j = 0; j < size; j++) { if (board[pos + off*j] != UNKNOWN && board[pos + off*j] != child->get(j)) { possible = false; break; } } if (possible) { if (!node->expanded) return true; if (matches(board, tree, child, cur_level+1)) return true; } } return false; } bool matches(const Clues &clues, const Board& board) { return matches(board, &clues.down_tree, clues.down_tree.root, 0) && matches(board, &clues.left_tree, clues.left_tree.root, 0) && matches(board, &clues.up_tree, clues.up_tree.root, 0) && matches(board, &clues.right_tree, clues.right_tree.root, 0); }