/* takuzu.cpp -- Counting number of Takuzu Copyright (C) 2015 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 Details: http://www.iwriteiam.nl/D1512.html#14 */ #include #include #define SIZE 10 long nr_rows; int row[SIZE]; class Tree { public: Tree() : zero(0), one(0), row_count(0), col_count(0) {} Tree* zero; Tree* one; int row_count; int col_count; }; Tree *trees = 0; void findrow(int p, int zeros, int ones) { if (zeros == 0 && ones == 0) { Tree **rtree = &trees; for (int i = 0; i < SIZE; i++) { if (*rtree == 0) *rtree = new Tree(); rtree = row[i] == 0 ? &(*rtree)->zero : &(*rtree)->one; printf("%d",row[i]); } *rtree = new Tree(); printf("\n"); nr_rows++; return; } if (zeros > 0 && (p < 2 || row[p-1] != 0 || row[p-2] != 0)) { row[p] = 0; findrow(p+1, zeros-1, ones); } if (ones > 0 && (p < 2 || row[p-1] != 1 || row[p-2] != 1)) { row[p] = 1; findrow(p+1, zeros, ones-1); } } double count = 0; int sol[SIZE][SIZE]; Tree* row_tree[SIZE][SIZE]; Tree* col_tree[SIZE][SIZE]; void solve() { int i = 0; int j = 0; sol[0][0] = 0; bool go = true; while (go) { bool zero = sol[i][j] == 0; Tree* row_tree_ij = zero ? row_tree[i][j]->zero : row_tree[i][j]->one; Tree* col_tree_ij = zero ? col_tree[i][j]->zero : col_tree[i][j]->one; if (row_tree_ij != 0 && col_tree_ij != 0) { bool unique = true; if (i < SIZE-1) { row_tree[i+1][j] = row_tree_ij; if (i == SIZE-2) { if (++row_tree_ij->row_count > 1) unique = false; } } if (j < SIZE-1) { col_tree[i][j+1] = col_tree_ij; if (j == SIZE-2) { if (++col_tree_ij->col_count > 1) unique = false; } } if (unique) { if (++i == SIZE) { i = 0; if (++j == SIZE) { count++; static clock_t s = clock(); static clock_t ct = clock(); if (ct < clock()) { ct = clock() + 6000; double secs = (clock() - s)/1000.0; printf("%10.1lf %20.0lf (%10.3lf)\n", secs, count, count/secs); } --j; i = SIZE-1; } else { sol[i][j] = 0; continue; } } else { sol[i][j] = 0; continue; } } } for (;;) { bool zero = sol[i][j] == 0; Tree* row_tree_ij = zero ? row_tree[i][j]->zero : row_tree[i][j]->one; Tree* col_tree_ij = zero ? col_tree[i][j]->zero : col_tree[i][j]->one; if (row_tree_ij != 0 && col_tree_ij != 0) { if (i == SIZE-2) --row_tree_ij->row_count; if (j == SIZE-2) --col_tree_ij->col_count; } if (zero) { sol[i][j] = 1; break; } if (i == 0) { if (j == 0) { go = false; break; } j--; i = SIZE-1; } else i--; } } } int main(int argc, char *argv[]) { findrow(0, SIZE/2, SIZE/2); printf("Rows = %d\n", nr_rows); for (int i = 0; i < SIZE; i++) col_tree[i][0] = trees; for (int j = 0; j < SIZE; j++) row_tree[0][j] = trees; solve(); printf("count = %20.0lf\n", count); return 0; }