#include #include #define GETBIT(I,X) (((X) >> (I)) & 1) #define FOURBITS(A,B,C,D) (((A) << 3) | ((B) << 2) | ((C) << 1) | (D)) int validcombinations[9] = { FOURBITS(0, 0, 0, 1), FOURBITS(0, 0, 1, 0), FOURBITS(0, 1, 0, 0), FOURBITS(1, 0, 0, 0), FOURBITS(0, 1, 1, 1), FOURBITS(1, 0, 1, 1), FOURBITS(1, 1, 0, 1), FOURBITS(1, 1, 1, 0), FOURBITS(1, 1, 1, 1), }; #define SIZE 5 char horz[SIZE+1][SIZE]; char vert[SIZE][SIZE+1]; int connected[SIZE][SIZE]; int max_nr_1 = SIZE*SIZE-1; int max_nr_0 = 2*SIZE*(SIZE-1) - (SIZE*SIZE-1); bool matches(int b, char c) { return c == ' ' ? b == 0 : c == '?' ? true : b == 1; } bool isValid(int x, int y, int c) { return matches(GETBIT(0, c), horz[x][y]) && matches(GETBIT(1, c), vert[x][y]) && matches(GETBIT(2, c), horz[x+1][y]) && matches(GETBIT(3, c), vert[x][y+1]); } int countValidCombinations(int x, int y) { int result = 0; for (int i = 0; i < 9; i++) if (isValid(x, y, validcombinations[i])) result++; return result; } int groups[SIZE*SIZE+1]; int nr_groups = 1; int group(int i) { if (i == 0) return 0; while (groups[i] > 0) i = groups[i]; return i; } int new_group() { return nr_groups++; } void reset_nr_groups(int g) { if (g == nr_groups) return; for (int x = 0; x < SIZE; x++) for (int y = 0; y < SIZE; y++) if (connected[x][y] >= g) connected[x][y] = 0; for (int i = 0; i < nr_groups; i++) if (groups[i] >= g) groups[i] = 0; while (nr_groups > g) groups[--nr_groups] = 0; } bool connect(int &a, int &b) { if (a == 0) { a = new_group(); if (b == 0) { b = a; } else { groups[group(b)] = a; } } else { if (b == 0) { b = new_group(); groups[group(a)] = b; } else { int group_a = group(a); int group_b = group(b); if (group_a == group_b) return false; // cycle is created int g = new_group(); groups[group_a] = g; groups[group_b] = g; } } return true; } void solve(int nr_0, int nr_1) { if (nr_0 > max_nr_0 || nr_1 > max_nr_1) return; int min_p = 100; int min_x; int min_y; for (int x = 0; x < SIZE; x++) for (int y = 0; y < SIZE; y++) { int p = countValidCombinations(x, y); if (p == 0) return; if ( p < min_p && ( horz[x][y] == '?' || vert[x][y] == '?' || horz[x+1][y] == '?' || vert[x][y+1] == '?')) { min_p = p; min_x = x; min_y = y; } } if (min_p == 100) { // All have been resolved: check if it is minimal char repr[8][2*SIZE*(SIZE+1)+1]; int i = 0; for (int x = 0; x < SIZE+1; x++) for (int y = 0; y < SIZE; y++) { repr[0][i] = horz[x][y] != ' ' ? '*' : ' '; repr[1][i] = horz[SIZE-x][y] != ' ' ? '*' : ' '; repr[2][i] = horz[x][SIZE-1-y] != ' ' ? '*' : ' '; repr[3][i] = horz[SIZE-x][SIZE-1-y] != ' ' ? '*' : ' '; repr[4][i] = vert[y][x] != ' ' ? '*' : ' '; repr[5][i] = vert[y][SIZE-x] != ' ' ? '*' : ' '; repr[6][i] = vert[SIZE-1-y][x] != ' ' ? '*' : ' '; repr[7][i] = vert[SIZE-1-y][SIZE-x] != ' ' ? '*' : ' '; i++; } for (int x = 0; x < SIZE; x++) for (int y = 0; y < SIZE+1; y++) { repr[0][i] = vert[x][y] != ' ' ? '*' : ' '; repr[1][i] = vert[SIZE-1-x][y] != ' ' ? '*' : ' '; repr[2][i] = vert[x][SIZE-y] != ' ' ? '*' : ' '; repr[3][i] = vert[SIZE-1-x][SIZE-y] != ' ' ? '*' : ' '; repr[4][i] = horz[y][x] != ' ' ? '*' : ' '; repr[5][i] = horz[y][SIZE-1-x] != ' ' ? '*' : ' '; repr[6][i] = horz[SIZE-y][x] != ' ' ? '*' : ' '; repr[7][i] = horz[SIZE-y][SIZE-1-x] != ' ' ? '*' : ' '; i++; } for (int j = 0; j < 8; j++) repr[j][i] = '\0'; if ( strcmp(repr[0], repr[1]) <= 0 && strcmp(repr[0], repr[2]) <= 0 && strcmp(repr[0], repr[3]) <= 0 && strcmp(repr[0], repr[4]) <= 0 && strcmp(repr[0], repr[5]) <= 0 && strcmp(repr[0], repr[6]) <= 0 && strcmp(repr[0], repr[7]) <= 0) { for (int y = 0; y < SIZE+1; y++) { for (int x = 0; x < SIZE; x++) printf(" %c", vert[x][y]); printf("\n"); if (y < SIZE) { for (int x = 0; x < SIZE+1; x++) printf("%c%s", horz[x][y], x < SIZE ? "+" : ""); } printf("\n"); } } return; } for (int i = 0; i < 9; i++) { int c = validcombinations[i]; if (isValid(min_x, min_y, c)) { int new_nr_0 = nr_0; int new_nr_1 = nr_1; int old_nr_groups = nr_groups; bool has_cycle = false; char old_l = horz[min_x][min_y]; if (old_l == '?') { horz[min_x][min_y] = GETBIT(0, c) ? '-' : ' '; if (min_x > 0) if (GETBIT(0, c)) { if (!connect(connected[min_x][min_y], connected[min_x-1][min_y])) has_cycle = true; new_nr_1++; } else new_nr_0++; } char old_t = vert[min_x][min_y]; if (old_t == '?') { vert[min_x][min_y] = GETBIT(1, c) ? '|' : ' '; if (min_y > 0) if (GETBIT(1, c)) { if (!connect(connected[min_x][min_y], connected[min_x][min_y-1])) has_cycle = true; new_nr_1++; } else new_nr_0++; } char old_r = horz[min_x+1][min_y]; if (old_r == '?') { horz[min_x+1][min_y] = GETBIT(2, c) ? '-' : ' '; if (min_x+1 < SIZE) if (GETBIT(2, c)) { if (!connect(connected[min_x][min_y], connected[min_x+1][min_y])) has_cycle = true; new_nr_1++; } else new_nr_0++; } char old_b = vert[min_x][min_y+1]; if (old_b == '?') { vert[min_x][min_y+1] = GETBIT(3, c) ? '|' : ' '; if (min_y+1 < SIZE) if (GETBIT(3, c)) { if (!connect(connected[min_x][min_y], connected[min_x][min_y+1])) has_cycle = true; new_nr_1++; } else new_nr_0++; } if (!has_cycle) solve(new_nr_0, new_nr_1); horz[min_x][min_y] = old_l; vert[min_x][min_y] = old_t; horz[min_x+1][min_y] = old_r; vert[min_x][min_y+1] = old_b; reset_nr_groups(old_nr_groups); } } } int main(int argc, char *argv[]) { for (int x = 0; x < SIZE; x++) for (int y = 0; y < SIZE; y++) connected[x][y] = 0; for (int x = 0; x < SIZE+1; x++) for (int y = 0; y < SIZE; y++) horz[x][y] = (x == 0 || x == SIZE) ? ' ' : '?'; horz[0][(SIZE-1)/2] = '?'; horz[SIZE][(SIZE-1)/2] = '?'; for (int x = 0; x < SIZE; x++) for (int y = 0; y < SIZE+1; y++) vert[x][y] = (y == 0 || y == SIZE) ? ' ' : '?'; vert[(SIZE-1)/2][0] = '?'; vert[(SIZE-1)/2][SIZE] = '?'; solve(0, 0); return 0; }