2 * Enumerate positions of the game Digit
4 * Martin Mares <mj@ucw.cz>, September 2011
13 #define SIZE (2*MATCHES+3)
15 typedef char conf[SIZE][SIZE];
17 static void print(conf c)
19 for (int i=0; i<SIZE; i++)
21 for (int j=0; j<SIZE; j++)
25 putchar((i%2) ? '|' : '-');
41 static void print_matches(conf c)
44 for (int i=0; i<SIZE; i++)
45 for (int j=1-i%2; j<SIZE; j+=2)
49 printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2+1, j/2);
51 printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2, j/2+1);
56 static void norm(conf from, conf to)
59 for (int i=0; i<SIZE; i++)
60 for (int j=0; j<SIZE; j++)
66 ASSERT(ii < SIZE && jj < SIZE);
68 int di = 2 - (ii & ~1U);
69 int dj = 2 - (jj & ~1U);
71 bzero(to, sizeof(conf));
72 for (int i=ii; i<SIZE; i++)
73 for (int j=jj; j<SIZE; j++)
78 ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
83 static void mirror(conf from, conf to)
85 for (int i=0; i<SIZE; i++)
86 for (int j=0; j<SIZE; j++)
87 to[i][j] = from[j][i];
90 static void rotate(conf from, conf to)
92 for (int i=0; i<SIZE; i++)
93 for (int j=0; j<SIZE; j++)
94 to[j][SIZE-1-i] = from[i][j];
97 static int rr(conf c, int i, int j)
99 if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
105 static int has_neighbor(conf c, int i, int j)
107 if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
108 : (rr(c, i, j-2) || rr(c, i, j+2)))
110 if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
111 rr(c, i+1, j-1) || rr(c, i+1, j+1))
125 #define MAXSTATES 1000
127 static struct state states[MAXSTATES];
130 static struct state *lookup_direct(conf c)
134 for (int i=0; i<wi; i++)
135 if (!memcmp(states[i].c, n, sizeof(conf)))
140 static struct state *lookup_rot(conf c)
143 memcpy(d[0], c, sizeof(conf));
144 for (int i=0; i<4; i++)
146 struct state *s = lookup_direct(d[i]);
150 rotate(d[i], d[i+1]);
155 static struct state *lookup(conf c)
157 struct state *s = lookup_rot(c);
163 return lookup_rot(d);
169 static void generate(void)
171 conf c = { [2][5] = 1 };
172 norm(c, states[0].c);
173 states[0].matches = 1;
179 struct state *s = &states[ri++];
181 memcpy(to, s->c, sizeof(conf));
182 printf("### State %d (%d matches) ###\n", s->id, s->matches);
184 if (s->matches < MATCHES)
186 for (int i=0; i<SIZE; i++)
187 for (int j=1-(i%2); j<SIZE; j+=2)
188 if (!to[i][j] && has_neighbor(to, i, j))
191 struct state *t = lookup(to);
196 t->matches = s->matches+1;
199 if (t->from != s->id)
201 printf("-> %d\n", t->id);
209 printf("Degree: %d in, %d out, from=%d\n", s->indegree, s->outdegree, s->from);