#include #define MAX_N 20 #define MAX_M 20 int field[MAX_N][MAX_M]; int n,m; int count; int count_0; int count_1; int count_more; void fill(int depth, int min_nr_filled, int min_k) { //printf(" - %d %d\n", depth, min_nr_filled); if (depth == n) { bool zero_row = false; for (int j = 0; j < m; j++) { bool all_zero = true; for (int i = 0; i < n; i++) if (field[i][j] == 1) { all_zero = false; break; } if (all_zero) return; for (int j2 = j+1; j2 < m; j2++) { bool all_equal = true; for (int i = 0; i < n; i++) if (field[i][j] != field[i][j2]) { all_equal = false; break; } if (all_equal) return; } } count++; // count number of solutions: int nr_sols = 0; int sol = 0; for (int k = 1; k < (1 << m); k++) { bool correct = true; for (int i = 0; i < n; i++) { int nr_ones = 0; for (int j = 0; j < m; j++) if ((k & (1 << j)) && field[i][j] == 1) nr_ones++; if (nr_ones != 1) { correct = false; break; } } if (correct) { sol = k; nr_sols++; } } if (nr_sols == 0) count_0++; else if (nr_sols == 1) { count_1++; printf("--\n"); for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) printf("%d", field[i][j]); printf("%s\n", sol & (1 << j) ? " *" : ""); } } else count_more++; return; } // fill column 'depth' for (int k = 3; k < (1 << m); k++) { int nr_filled = 0; for (int j = 0; j < m; j++) if (k & (1 << j)) { field[depth][j] = 1; nr_filled++; } else field[depth][j] = 0; if (nr_filled >= min_nr_filled && nr_filled < m && (nr_filled > min_nr_filled || k > min_k)) { bool implied_row = false; for (int i = 0; i < depth; i++) { implied_row = true; for (int j = 0; j < m; j++) if (field[i][j] == 1 && field[depth][j] == 0) { implied_row = false; break; } if (implied_row) break; } if (!implied_row) { bool prev_is_filled = true; bool correct = true; for (int j = 0; j < m; j++) { bool is_filled = false; for (int i = 0; i <= depth; i++) if (field[i][j] == 1) { is_filled = true; break; } if (is_filled && !prev_is_filled) { correct = false; break; } prev_is_filled = is_filled; } if (correct) fill(depth+1, nr_filled, k); } } } } int main(int argc, char *argv[]) { for (int nm = 9; nm <= 36; nm++) for (n = 3; n <= 12; n++) for (m = 3; m <= 12 && n*m <= 36; m++) if (n*m == nm) if (m <= (1 << n)) { count = 0; count_0 = 0; count_1 = 0; count_more = 0; fill(0, 2, 0); printf("n = %d, m = %d: %d %d, %d, %d\n", n, m, count, count_0, count_1, count_more); } return 0; }