/* Nonogram2ExactCover - converting nonograms to Exact Covers The command line options are: [-01] [] The file 'filename' is expected to contain a description of a nonogram. This description constist of: - a line starting with "width " followed by a number giving the width - a line starting with "height " followed by a number giving the height - a line starting with "rows" followed by lines which specify one row each - a line starting with "columns" followed by lines which specify one column each The specification of a row or column either consists of "0" or a sequences of numbers followed by a comma and a space. The (optional) file 'filename2' contains a partial solution of the nonogram. On the output the program will generate an Exact Cover representing the given Nonogram. This program is refered to at http://www.iwriteiam.nl/D0906.html#27 The implementation makes use of dancing links, a technique suggested by D.E. Knuth. See: http://en.wikipedia.org/wiki/Dancing_Links Copyright (C) 2009 Frans Faase 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 #include #include typedef unsigned char byte; #define MAX_SIZE 100 #define MAX_SIZE_D8 ((MAX_SIZE+7)/8) struct Piece { int size; int min; int max; bool pos[MAX_SIZE]; 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; } 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; } }; struct Pieces { int nr; Piece pieces[MAX_SIZE]; void add(int v) { pieces[nr++].size = v; } void init(int size) { 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; } } }; int n; int m; int nm; #define UNKNOWN '?' #define FULL '*' #define EMPTY '_' struct Clues { Pieces row[MAX_SIZE]; Pieces col[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 read_partial_solution(char *fn, char* partial_sol) { FILE* f = fopen(fn, "rt"); if (f == 0) { printf("No file %s\n", fn); return; } for (int row_nr = 0; row_nr < n; row_nr++) { char line[1000]; fgets(line, 999, f); for (int col_nr = 0; col_nr < m; col_nr++) *partial_sol++ = line[col_nr]; } } 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; }; Clues clues; char *partial_sol; int main(int argc, char *argv[]) { char* clues_fn = 0; char* partial_sol_fn = 0; bool mode_01 = false; for (int i = 1; i < argc; i++) { if (strcmp(argv[i], "-01") == 0) mode_01 = true; else if (clues_fn == 0) clues_fn = argv[i]; else if (partial_sol_fn == 0) partial_sol_fn = argv[i]; else printf(" skipped argument '%s'\n", argv[i]); } if (clues_fn == 0) { printf("%s [-01] []\n", argv[0]); return 0; } if (!read_clues(clues_fn, clues)) { printf("\n\nread error\n"); return 0; } partial_sol = (char*)malloc(sizeof(char)*(n*m+1)); for (int i = 0; i < n*m; i++) partial_sol[i] = '?'; partial_sol[n*m] = '\0'; if (partial_sol_fn != 0) { read_partial_solution(partial_sol_fn, partial_sol); char *s = partial_sol; for (int row_nr = 0; row_nr < n; row_nr++) { for (int col_nr = 0; col_nr < m; col_nr++) printf("%c", *s++); printf("\n"); } } bool row_solved[MAX_SIZE]; for (int row_nr = 0; row_nr < n; row_nr++) row_solved[row_nr] = true; bool col_solved[MAX_SIZE]; for (int col_nr = 0; col_nr < m; col_nr++) col_solved[col_nr] = true; { char *s = partial_sol; for (int row_nr = 0; row_nr < n; row_nr++) { for (int col_nr = 0; col_nr < m; col_nr++) if (*s++ == '?') { col_solved[col_nr] = false; row_solved[row_nr] = false; } } } for (int row_nr = 0; row_nr < n; row_nr++) { fprintf(stderr, "row %d\n", row_nr); if (row_solved[row_nr]) continue; Pieces& pieces = clues.row[row_nr]; for (int i = 0; i < pieces.nr; i++) { Piece& p = pieces.pieces[i]; for (int j = p.min; j < p.max; j++) { int col_nr = j - 1; bool matches = col_nr < 0 || partial_sol[m*row_nr + col_nr] != FULL; col_nr++; for (int k = 0; k < p.size && matches; k++, col_nr++) if (partial_sol[m*row_nr + col_nr] == EMPTY) matches = false; if (matches && col_nr < m && partial_sol[m*row_nr + col_nr] == FULL) matches = false; if (!matches) p.reset(j); } } for (PiecesCombinationsIterator it(pieces, m); it.more(); it.next()) { int values[MAX_SIZE]; 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++) values[j] = 0; for (; j < end; j++) values[j] = 1; } for (; j < m; j++) values[j] = 0; bool matches = true; for (int col_nr = 0; col_nr < m; col_nr++) { if (partial_sol[m*row_nr + col_nr] == (values[col_nr] ? '_' : '*')) { matches = false; break; } } if (matches) { if (mode_01) { char *s = partial_sol; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (*s++ == '?') printf("%s", i != row_nr ? "00" : values[j] == 1 ? "10" : "01"); } else { for (int i = 0; i < n; i++) if (!row_solved[i]) printf("%c", (i == row_nr) ? '1' : '0'); for (int i = 0; i < m; i++) if (!col_solved[i]) printf("0"); char *s = partial_sol; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (*s++ == '?') printf("%c", (i == row_nr && values[j] == 1) ? '1' : '0'); } printf(" row %2d: ", row_nr+1); for (int i = 0; i < m; i++) printf("%d", values[i]); for (int j = 0; j < pieces.nr; j++) { const Piece& p = pieces.pieces[j]; printf(" %d", p.size); } printf("\n"); } } } for (int col_nr = 0; col_nr < m; col_nr++) { if (col_solved[col_nr]) continue; fprintf(stderr, "col %d\n", col_nr); const Pieces& pieces = clues.col[col_nr]; for (PiecesCombinationsIterator it(pieces, n); it.more(); it.next()) { int values[MAX_SIZE]; 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++) values[j] = 0; for (; j < end; j++) values[j] = 1; } for (; j < n; j++) values[j] = 0; bool matches = true; for (int row_nr = 0; row_nr < n; row_nr++) { if (partial_sol[m*row_nr + col_nr] == (values[row_nr] ? '_' : '*')) { matches = false; break; } } if (matches) { if (mode_01) { char *s = partial_sol; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (*s++ == '?') printf("%s", j != col_nr ? "00" : values[i] == 1 ? "01" : "10"); } else { for (int i = 0; i < n; i++) if (!row_solved[i]) printf("0"); for (int i = 0; i < m; i++) if (!col_solved[i]) printf("%c", (i == col_nr) ? '1' : '0'); char *s = partial_sol; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (*s++ == '?') printf("%c", (j == col_nr && values[i] == 0) ? '1' : '0'); } printf(" col %2d: ", col_nr+1); for (int i = 0; i < n; i++) printf("%d", values[i]); for (int j = 0; j < pieces.nr; j++) { const Piece& p = pieces.pieces[j]; printf(" %d", p.size); } printf("\n"); } } } return 0; }