/* 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, int j) { if (j == SIZE) { { 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); } } count++; return; } int n_i = i+1; int n_j = j; if (n_i == SIZE) { n_i = 0; n_j++; } Tree* row_tree_zero = row_tree[i][j]->zero; Tree* col_tree_zero = col_tree[i][j]->zero; if (row_tree_zero != 0 && col_tree_zero != 0) { sol[i][j] = 0; bool unique = true; if (i < SIZE-1) { row_tree[i+1][j] = row_tree_zero; if (i == SIZE-2) { if (++row_tree_zero->row_count > 1) unique = false; } } if (j < SIZE-1) { col_tree[i][j+1] = col_tree_zero; if (j == SIZE-2) { if (++col_tree_zero->col_count > 1) unique = false; } } if (unique) solve(n_i, n_j); if (i == SIZE-2) --row_tree_zero->row_count; if (j == SIZE-2) --col_tree_zero->col_count; } Tree* row_tree_one = row_tree[i][j]->one; Tree* col_tree_one = col_tree[i][j]->one; if (row_tree_one != 0 && col_tree_one != 0) { sol[i][j] = 1; bool unique = true; if (i < SIZE-1) { row_tree[i+1][j] = row_tree_one; if (i == SIZE-2) { if (++row_tree_one->row_count > 1) unique = false; } } if (j < SIZE-1) { col_tree[i][j+1] = col_tree_one; if (j == SIZE-2) { if (++col_tree_one->col_count > 1) unique = false; } } if (unique) solve(n_i, n_j); if (i == SIZE-2) --row_tree_one->row_count; if (j == SIZE-2) --col_tree_one->col_count; } } 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(0, 0); printf("count = %20.0lf\n", count); return 0; }