2 * Enumerate positions of the game Digit
4 * Martin Mares <mj@ucw.cz>, September 2011
13 #define SIZE (2*MATCHES+5)
14 /* +5, because possible_moves() sometimes needs to represent a disconnected 5-match configuration with 1 gap */
16 typedef char conf[SIZE][SIZE];
18 static void print(conf c)
20 for (int i=0; i<SIZE; i++)
22 for (int j=0; j<SIZE; j++)
26 putchar((i%2) ? '|' : '-');
42 static void print_matches(conf c)
45 for (int i=0; i<SIZE; i++)
46 for (int j=1-i%2; j<SIZE; j+=2)
50 printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2+1, j/2);
52 printf(" (%d,%d)-(%d,%d)", i/2, j/2, i/2, j/2+1);
57 static void norm(conf from, conf to)
60 for (int i=0; i<SIZE; i++)
61 for (int j=0; j<SIZE; j++)
67 ASSERT(ii < SIZE && jj < SIZE);
69 int di = 2 - (ii & ~1U);
70 int dj = 2 - (jj & ~1U);
72 bzero(to, sizeof(conf));
73 for (int i=ii; i<SIZE; i++)
74 for (int j=jj; j<SIZE; j++)
79 ASSERT(fi >= 0 && fj >= 0 && fi < SIZE && fj < SIZE);
84 static void mirror(conf from, conf to)
86 for (int i=0; i<SIZE; i++)
87 for (int j=0; j<SIZE; j++)
88 to[i][j] = from[j][i];
91 static void rotate(conf from, conf to)
93 for (int i=0; i<SIZE; i++)
94 for (int j=0; j<SIZE; j++)
95 to[j][SIZE-1-i] = from[i][j];
98 static int rr(conf c, int i, int j)
100 if (i < 0 || i >= SIZE || j < 0 || j >= SIZE)
106 static int has_neighbor(conf c, int i, int j)
108 if ((i%2) ? (rr(c, i-2, j) || rr(c, i+2, j))
109 : (rr(c, i, j-2) || rr(c, i, j+2)))
111 if (rr(c, i-1, j-1) || rr(c, i-1, j+1) ||
112 rr(c, i+1, j-1) || rr(c, i+1, j+1))
126 #define MAXSTATES 1000
128 static struct state states[MAXSTATES];
131 static struct state *lookup_direct(conf c)
135 for (int i=0; i<wi; i++)
136 if (!memcmp(states[i].c, n, sizeof(conf)))
141 static struct state *lookup_rot(conf c)
144 memcpy(d[0], c, sizeof(conf));
145 for (int i=0; i<4; i++)
147 struct state *s = lookup_direct(d[i]);
151 rotate(d[i], d[i+1]);
156 static struct state *lookup(conf c)
158 struct state *s = lookup_rot(c);
164 return lookup_rot(d);
170 static void generate(void)
172 conf c = { [2][5] = 1 };
173 norm(c, states[0].c);
174 states[0].matches = 1;
180 struct state *s = &states[ri++];
182 memcpy(to, s->c, sizeof(conf));
183 printf("### State %d (%d matches) ###\n", s->id, s->matches);
185 if (s->matches < MATCHES)
187 for (int i=0; i<SIZE; i++)
188 for (int j=1-(i%2); j<SIZE; j+=2)
189 if (!to[i][j] && has_neighbor(to, i, j))
192 struct state *t = lookup(to);
195 ASSERT(wi < MAXSTATES);
198 t->matches = s->matches+1;
201 if (t->from != s->id)
203 printf("-> %d\n", t->id);
211 printf("Degree: %d in, %d out, from=%d\n", s->indegree, s->outdegree, s->from);
217 static void possible_moves(void)
219 puts("\n=== POSSIBLE MOVES ===\n\n");
221 for (int i=0; i<wi; i++)
224 for (int i=0; i<wi; i++)
226 struct state *s = &states[i];
227 if (s->matches < MATCHES)
230 memcpy(c, s->c, sizeof(conf));
232 printf("### State %d ###\n", s->id);
236 for (int j=0; j<SIZE; j++)
237 for (int k=0; k<SIZE; k++)
241 for (int p=0; p<SIZE; p++)
242 for (int q=0; q<SIZE; q++)
243 if (!c[p][q] && (p != j || q != k) && has_neighbor(c, p, q))
246 struct state *t = lookup(c);
247 if (t && t != s && t->from != s->id)
250 // printf("-> state %d\n", t->id);
259 printf("=> %d neighbors\n\n", neighbors);