gen.c (10772B)
1 /* gen.c - solver con mascaras de bits, calificador "humano" y generador. */ 2 #include <string.h> 3 #include "gen.h" 4 5 int mini_rand(int n); /* de mini.c */ 6 7 uint8_t su_peer[81][20]; 8 uint8_t su_pc[512]; 9 static uint8_t unit[27][9]; /* 9 filas, 9 columnas, 9 bloques */ 10 static uint8_t box_of[81]; 11 12 static int box_cell(int b, int i) { return ((b / 3) * 3 + i / 3) * 9 + (b % 3) * 3 + i % 3; } 13 14 void su_init(void) 15 { 16 for (int m = 0; m < 512; m++) su_pc[m] = (uint8_t)((m & 1) + su_pc[m >> 1]); 17 for (int u = 0; u < 9; u++) 18 for (int i = 0; i < 9; i++) { 19 unit[u][i] = (uint8_t)(u * 9 + i); 20 unit[9 + u][i] = (uint8_t)(i * 9 + u); 21 unit[18 + u][i] = (uint8_t)box_cell(u, i); 22 box_of[box_cell(u, i)] = (uint8_t)u; 23 } 24 for (int c = 0; c < 81; c++) { 25 int n = 0; 26 for (int j = 0; j < 81; j++) 27 if (j != c && (j / 9 == c / 9 || j % 9 == c % 9 || box_of[j] == box_of[c])) 28 su_peer[c][n++] = (uint8_t)j; 29 } 30 } 31 32 static int low_bit(unsigned m) { int v = 0; while (!(m & 1)) { m >>= 1; v++; } return v; } 33 34 /* ------------------------------------------------------------ solver por fuerza bruta */ 35 36 int su_count(const uint8_t *g, int limit, uint8_t *out, int rnd, int32_t maxnodes) 37 { 38 static uint8_t b[81], scell[81]; 39 static uint16_t scand[81], rowm[9], colm[9], boxm[9]; 40 memcpy(b, g, 81); 41 memset(rowm, 0, sizeof rowm); memset(colm, 0, sizeof colm); memset(boxm, 0, sizeof boxm); 42 for (int c = 0; c < 81; c++) { 43 if (!b[c]) continue; 44 unsigned bit = 1u << (b[c] - 1); 45 if ((rowm[c / 9] | colm[c % 9] | boxm[box_of[c]]) & bit) return 0; /* pistas en conflicto */ 46 rowm[c / 9] |= bit; colm[c % 9] |= bit; boxm[box_of[c]] |= bit; 47 } 48 int d = 0, count = 0; 49 int32_t nodes = 0; 50 bool descend = true; 51 for (;;) { 52 if (descend) { 53 if (++nodes > maxnodes) return -1; 54 int best = -1, bc = 10; 55 unsigned bm = 0; 56 for (int c = 0; c < 81; c++) { 57 if (b[c]) continue; 58 unsigned m = ~(rowm[c / 9] | colm[c % 9] | boxm[box_of[c]]) & 0x1FF; 59 if (su_pc[m] < bc) { bc = su_pc[m]; best = c; bm = m; if (bc <= 1) break; } 60 } 61 if (best < 0) { 62 if (++count == 1 && out) memcpy(out, b, 81); 63 if (count >= limit) return count; 64 } else if (bc > 0) { 65 scell[d] = (uint8_t)best; scand[d] = (uint16_t)bm; d++; 66 } 67 } 68 /* probar el siguiente candidato de la celda de arriba de la pila */ 69 if (d == 0) return count; 70 int c = scell[d - 1]; 71 if (b[c]) { 72 unsigned bit = 1u << (b[c] - 1); 73 rowm[c / 9] &= ~bit; colm[c % 9] &= ~bit; boxm[box_of[c]] &= ~bit; 74 b[c] = 0; 75 } 76 unsigned m = scand[d - 1]; 77 if (!m) { d--; descend = false; continue; } 78 int v; 79 if (rnd) { 80 int k = mini_rand(su_pc[m]); 81 for (v = 0; ; v++) if ((m >> v & 1) && k-- == 0) break; 82 } else v = low_bit(m); 83 scand[d - 1] = (uint16_t)(m & ~(1u << v)); 84 b[c] = (uint8_t)(v + 1); 85 rowm[c / 9] |= 1u << v; colm[c % 9] |= 1u << v; boxm[box_of[c]] |= 1u << v; 86 descend = true; 87 } 88 } 89 90 /* ------------------------------------------------------------ calificador humano */ 91 92 static uint8_t hv[81]; 93 static uint16_t hc[81]; /* candidatos */ 94 static int hleft; 95 96 static void h_place(int c, int v) 97 { 98 hv[c] = (uint8_t)v; hc[c] = 0; hleft--; 99 for (int i = 0; i < 20; i++) hc[su_peer[c][i]] &= (uint16_t)~(1u << (v - 1)); 100 } 101 102 static bool singles(void) 103 { 104 bool any = false; 105 for (int c = 0; c < 81; c++) 106 if (!hv[c] && su_pc[hc[c]] == 1) { h_place(c, low_bit(hc[c]) + 1); any = true; } 107 if (any) return true; 108 for (int u = 0; u < 27; u++) 109 for (int v = 0; v < 9; v++) { 110 int n = 0, at = -1; 111 for (int i = 0; i < 9 && n < 2; i++) 112 if (hc[unit[u][i]] >> v & 1) { n++; at = unit[u][i]; } 113 if (n == 1) { h_place(at, v + 1); any = true; } 114 } 115 return any; 116 } 117 118 /* Saca el digito v de las celdas de la unidad u que no esten en keep (mascara de posiciones). */ 119 static bool strip(int u, int v, unsigned keep) 120 { 121 bool any = false; 122 for (int i = 0; i < 9; i++) { 123 int c = unit[u][i]; 124 if (!(keep >> i & 1) && (hc[c] >> v & 1)) { hc[c] &= (uint16_t)~(1u << v); any = true; } 125 } 126 return any; 127 } 128 129 /* Posiciones (0..8) de la unidad u donde puede ir v. */ 130 static unsigned where(int u, int v) 131 { 132 unsigned m = 0; 133 for (int i = 0; i < 9; i++) if (hc[unit[u][i]] >> v & 1) m |= 1u << i; 134 return m; 135 } 136 137 static bool intersections(void) 138 { 139 bool any = false; 140 for (int b = 0; b < 9; b++) 141 for (int v = 0; v < 9; v++) { 142 unsigned m = where(18 + b, v); 143 if (!m) continue; 144 /* dentro del bloque: posiciones i -> fila i/3, columna i%3 */ 145 unsigned rows = (m & 7 ? 1 : 0) | (m & 070 ? 2 : 0) | (m & 0700 ? 4 : 0); 146 unsigned cols = (m & 0111 ? 1 : 0) | (m & 0222 ? 2 : 0) | (m & 0444 ? 4 : 0); 147 if (su_pc[rows] == 1) { /* apuntando por fila */ 148 int r = (b / 3) * 3 + low_bit(rows); 149 any |= strip(r, v, 7u << ((b % 3) * 3)); 150 } 151 if (su_pc[cols] == 1) { 152 int cc = (b % 3) * 3 + low_bit(cols); 153 any |= strip(9 + cc, v, 7u << ((b / 3) * 3)); 154 } 155 } 156 if (any) return true; 157 for (int l = 0; l < 18; l++) /* fila/columna encerrada en un bloque */ 158 for (int v = 0; v < 9; v++) { 159 unsigned m = where(l, v); 160 if (!m) continue; 161 unsigned seg = (m & 7 ? 1 : 0) | (m & 070 ? 2 : 0) | (m & 0700 ? 4 : 0); 162 if (su_pc[seg] != 1) continue; 163 int b = l < 9 ? (l / 3) * 3 + low_bit(seg) : low_bit(seg) * 3 + (l - 9) / 3; 164 unsigned keep = 0; 165 for (int i = 0; i < 9; i++) { 166 int c = unit[18 + b][i]; 167 if (l < 9 ? c / 9 == l : c % 9 == l - 9) keep |= 1u << i; 168 } 169 any |= strip(18 + b, v, keep); 170 } 171 return any; 172 } 173 174 static bool subsets(void) 175 { 176 bool any = false; 177 for (int u = 0; u < 27; u++) { 178 /* pares y triples desnudos */ 179 for (int i = 0; i < 9; i++) { 180 unsigned a = hc[unit[u][i]]; 181 if (su_pc[a] < 2 || su_pc[a] > 3) continue; 182 for (int j = i + 1; j < 9; j++) { 183 unsigned ab = a | hc[unit[u][j]]; 184 if (!hc[unit[u][j]] || su_pc[ab] > 3) continue; 185 if (su_pc[ab] == 2) { 186 unsigned keep = 1u << i | 1u << j; 187 for (int v = 0; v < 9; v++) if (ab >> v & 1) any |= strip(u, v, keep); 188 continue; 189 } 190 for (int k = j + 1; k < 9; k++) { 191 unsigned abc = ab | hc[unit[u][k]]; 192 if (!hc[unit[u][k]] || su_pc[abc] != 3) continue; 193 unsigned keep = 1u << i | 1u << j | 1u << k; 194 for (int v = 0; v < 9; v++) if (abc >> v & 1) any |= strip(u, v, keep); 195 } 196 } 197 } 198 /* pares ocultos */ 199 unsigned w[9]; 200 for (int v = 0; v < 9; v++) w[v] = where(u, v); 201 for (int v = 0; v < 9; v++) { 202 if (su_pc[w[v]] != 2) continue; 203 for (int x = v + 1; x < 9; x++) { 204 if (w[x] != w[v]) continue; 205 for (int i = 0; i < 9; i++) 206 if (w[v] >> i & 1) { 207 uint16_t *p = &hc[unit[u][i]]; 208 uint16_t nm = (uint16_t)(*p & (1u << v | 1u << x)); 209 if (nm != *p) { *p = nm; any = true; } 210 } 211 } 212 } 213 } 214 if (any) return true; 215 /* X-wing por filas y por columnas */ 216 for (int base = 0; base <= 9; base += 9) 217 for (int v = 0; v < 9; v++) 218 for (int a = 0; a < 9; a++) { 219 unsigned m = where(base + a, v); 220 if (su_pc[m] != 2) continue; 221 for (int b = a + 1; b < 9; b++) { 222 if (where(base + b, v) != m) continue; 223 for (int i = 0; i < 9; i++) { 224 if (!(m >> i & 1)) continue; 225 /* la linea cruzada i: sacar v salvo en a y b */ 226 any |= strip((base ? 0 : 9) + i, v, 1u << a | 1u << b); 227 } 228 } 229 } 230 return any; 231 } 232 233 int su_grade(const uint8_t *g) 234 { 235 hleft = 81; 236 for (int c = 0; c < 81; c++) { hv[c] = 0; hc[c] = 0x1FF; } 237 for (int c = 0; c < 81; c++) if (g[c]) h_place(c, g[c]); 238 int level = 0; 239 while (hleft > 0) { 240 if (singles()) continue; 241 if (intersections()) { if (level < 1) level = 1; continue; } 242 if (subsets()) { if (level < 2) level = 2; continue; } 243 return 3; 244 } 245 return level; 246 } 247 248 /* ------------------------------------------------------------ generador */ 249 250 enum { MAXNODES = 20000 }; 251 252 /* Saca pistas de a pares simetricos mientras la solucion siga unica y la dificultad 253 * no pase de maxg (3: sin limite). Devuelve las pistas que quedan. */ 254 static int carve(uint8_t *g, int maxg, int minclues) 255 { 256 uint8_t order[41]; 257 int clues = 81; 258 for (int i = 0; i < 41; i++) order[i] = (uint8_t)i; 259 for (int i = 40; i > 0; i--) { int j = mini_rand(i + 1); uint8_t t = order[i]; order[i] = order[j]; order[j] = t; } 260 for (int k = 0; k < 41; k++) { 261 int a = order[k], b = 80 - a, n = a == b ? 1 : 2; 262 if (clues - n < minclues) continue; 263 uint8_t va = g[a], vb = g[b]; 264 g[a] = g[b] = 0; 265 int gr = su_grade(g); 266 /* si la logica lo resuelve la solucion es unica; si no, contar */ 267 bool ok = gr < 3 ? gr <= maxg : maxg >= 3 && su_count(g, 2, 0, 0, MAXNODES) == 1; 268 if (ok) clues -= n; 269 else { g[a] = va; g[b] = vb; } 270 } 271 return clues; 272 } 273 274 int su_generate(int level, uint8_t *puzzle, uint8_t *solution) 275 { 276 static const uint8_t MAXG[4] = { 0, 1, 2, 3 }, MINC[4] = { 36, 28, 0, 0 }, TRIES[4] = { 1, 10, 30, 20 }; 277 static uint8_t zero[81], g[81]; 278 int best = -1, clues = 0; 279 for (int t = 0; t < TRIES[level]; t++) { 280 su_count(zero, 1, solution, 1, 100000); 281 memcpy(g, solution, 81); 282 int n = carve(g, MAXG[level], MINC[level]); 283 int gr = su_grade(g); 284 if (gr > best) { best = gr; clues = n; memcpy(puzzle, g, 81); } 285 if (gr >= MAXG[level]) break; 286 } 287 /* la solucion que corresponde al mejor */ 288 su_count(puzzle, 1, solution, 0, 1000000); 289 return clues; 290 }