/* BinaryPuzzle2ExactCover - transforms a Binary Puzzle into Exact Cover On the stdin it expects the representation of a Binary Puzzle (see http://www.binarypuzzle.com/ for the rules). Each line of the input represents a row using the characters '.', '0', and '1'. On the stdout it generates a Exact Cover representation of the puzzle. 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 char puzzle[1000]; int n, m; bool sol[1000]; class TreeNode { public: TreeNode() : count(0), id(0), left(0), right(0) {} TreeNode* left; TreeNode* right; int count; int id; TreeNode* select(bool value) { if (value) { if (left == 0) left = new TreeNode; return left; } else { if (right == 0) right = new TreeNode; return right; } } }; TreeNode rowTree; TreeNode colTree; int nr_same = 0; bool find_same_rows; void generate_all(int a, int b, int na, int nb, int pos, int offset, bool is_row, int nr) { int left = a + b; if (left == 0) { TreeNode *tree = 0; if (is_row) { tree = &rowTree; for (int i = 0; i < n; i++) tree = tree->select(sol[nr*n+i]); } else { tree = &colTree; for (int j = 0; j < m; j++) tree = tree->select(sol[j*n+nr]); } if (find_same_rows) { tree->count++; if (tree->count == 2) tree->id = nr_same++; } else { for (int j = 0; j < m; j++) printf("%c", is_row && j == nr ? '1' : '0'); for (int i = 0; i < n; i++) printf("%c", !is_row && i == nr ? '1' : '0'); for (int i = 0; i < n*m; i++) if (puzzle[i] == '.') printf("%c", sol[i] ? '1' : '0'); int l = tree->count > 1 ? tree->id : -1; for (int k = 0; k < nr_same; k++) printf("%c", l == k ? '1' : '0'); printf(" %s %2d: ", is_row ? "row" : "col", nr+1); if (is_row) for (int i = 0; i < n; i++) printf("%c", sol[nr*n+i] ? '1' : '0'); else for (int j = 0; j < m; j++) printf("%c", sol[j*n+nr] ? '0' : '1'); printf("\n"); } return; } if (a < left/3 || b < left/3) return; if (a > 0 && na < 2 && puzzle[pos] != '1') { sol[pos] = !is_row; generate_all(a-1, b, na+1, 0, pos + offset, offset, is_row, nr); } if (b > 0 && nb < 2 && puzzle[pos] != '0') { sol[pos] = is_row; generate_all(a, b-1, 0, nb+1, pos + offset, offset, is_row, nr); } } int main(int argc, char* argv[]) { n = 200; m = 0; { char line[101]; while (fgets(line, 100, stdin)) { int i; for (i = 0; i < n; i++) if (line[i] == '1' || line[i] == '0' || line[i] == '.') puzzle[n*m + i] = line[i]; else break; if (i == 0) break; if (n == 200) n = i; m++; } } fprintf(stderr, "n = %d, m = %d\n", n, m); for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) fprintf(stderr, "%c", puzzle[n*j+i]); fprintf(stderr, "\n"); } find_same_rows = true; for (int j = 0; j < m; j++) { for (int k = 0; k < n*m; k++) sol[k] = false; generate_all(n/2, n/2, 0, 0, n*j, 1, true, j); } for (int i = 0; i < n; i++) { for (int k = 0; k < n*m; k++) sol[k] = false; generate_all(m/2, m/2, 0, 0, i, m, false, i); } fprintf(stderr, "same rows/cols: %d\n", nr_same); find_same_rows = false; for (int j = 0; j < m; j++) { for (int k = 0; k < n*m; k++) sol[k] = false; generate_all(n/2, n/2, 0, 0, n*j, 1, true, j); } for (int i = 0; i < n; i++) { for (int k = 0; k < n*m; k++) sol[k] = false; generate_all(m/2, m/2, 0, 0, i, m, false, i); } for (int l = 0; l < nr_same; l++) { for (int j = 0; j < m; j++) printf("0"); for (int i = 0; i < n; i++) printf("0"); for (int i = 0; i < n*m; i++) if (puzzle[i] == '.') printf("0"); for (int k = 0; k < nr_same; k++) printf("%c", l == k ? '1' : '0'); printf("\n"); } return 0; }