⎇ c02fd3a4d4a9b6e3a51ddd2f59112f3584e6ea12
nonet/src/main/java/com/rizoma/nonet/game/Motor.kt
Ñawpa willay
ch'uya
Nonet: 3 variantes de pista externa, dificultad real y menú en páginas
1package com.rizoma.nonet.game
2
3import com.rizoma.nonet.model.Dificultad
4import com.rizoma.nonet.model.Variant
5import java.util.Random
6import kotlin.math.abs
7
8/** Relación entre dos celdas vecinas (consecutivo, sumas XV, desigualdad, orden Rossini). */
9enum class Rel { CONSEC, NO_CONSEC, SUM5, SUM10, NO_5_10, LT, GT }
10
11/** Restricción binaria vista desde una celda: contra [other] debe cumplirse [rel]. */
12class BinPeer(val other: Int, val rel: Rel)
13
14/** Jaula/diagonal con suma. [noRepite] true en Killer; false en Little Killer (admite repes). */
15class Cage(val cells: IntArray, val sum: Int, val noRepite: Boolean = true)
16
17/** Restricción de visibilidad (rascacielos): por [cells] en orden de mirada, se ven [k]. */
18class Vis(val cells: IntArray, val k: Int)
19
20/** Marca a dibujar entre dos celdas adyacentes [a]-[b] (orientada para < >). */
21class Arista(val a: Int, val b: Int, val rel: Rel)
22
23/** Pistas del borde, para dibujar el marco de las variantes con pistas externas. */
24class Borde(
25 val sky: Array<IntArray>? = null, // [lado 0=arr,1=ab,2=izq,3=der][9]; 0 = sin pista
26 val rossini: Array<IntArray>? = null, // [lado][9]; 0=nada, 1=creciente hacia dentro, 2=decreciente
27 val littleKiller: List<LK> = emptyList(), // flechas diagonales ancladas arriba
28)
29
30/** Flecha de Little Killer anclada sobre la columna [col]; dir 0=↘, 1=↗; suma de su diagonal. */
31class LK(val col: Int, val dir: Int, val sum: Int)
32
33/** Todas las restricciones de un puzzle, resueltas para el solver. */
34class Reglas(
35 val groups: List<IntArray>,
36 val peers: Array<IntArray>,
37 val allowed: IntArray,
38 val bin: Array<List<BinPeer>>,
39 val cagesOf: Array<List<Cage>>,
40 val cages: List<Cage>,
41 val visOf: Array<List<Vis>>,
42 val vis: List<Vis>,
43)
44
45/** Un puzzle generado: pistas, solución única, reglas y datos para dibujar. */
46class Puzzle(
47 val variant: Variant,
48 val dificultad: Dificultad,
49 val index: Int,
50 val givens: IntArray,
51 val solution: IntArray,
52 val reglas: Reglas,
53 val regiones: IntArray?, // jigsaw: región (0..8) por celda; null = cajas 3×3
54 val aristas: List<Arista>, // marcas entre celdas (consecutivo/XV/mayor-que)
55 val borde: Borde?, // pistas externas (rascacielos/little killer/rossini)
56) {
57 val peers: Array<IntArray> get() = reglas.peers
58 val id: String get() = "${variant.id}:${dificultad.ordinal}:$index"
59}
60
61/**
62 * Motor unificado de todas las variantes. Genera una solución completa bajo las
63 * regiones de la variante, deriva de ella sus restricciones (paridad, marcas,
64 * jaulas, pistas de borde) y cava celdas mientras la solución siga siendo única;
65 * en fácil/medio, además, exigiendo que se resuelva solo con lógica de singles.
66 */
67object Motor {
68 private const val TODOS = 0x3FE
69 private const val PARES = (1 shl 2) or (1 shl 4) or (1 shl 6) or (1 shl 8)
70 private const val IMPARES = (1 shl 1) or (1 shl 3) or (1 shl 5) or (1 shl 7) or (1 shl 9)
71
72 fun generar(v: Variant, dif: Dificultad, index: Int): Puzzle {
73 val rng = Random(seedFor(v, dif, index))
74
75 val regiones = if (v.tipo == Variant.Tipo.JIGSAW) jigsaw(rng) else null
76 val baseGroups = ArrayList<IntArray>(36)
77 for (r in 0 until 9) baseGroups.add(IntArray(9) { r * 9 + it })
78 for (c in 0 until 9) baseGroups.add(IntArray(9) { it * 9 + c })
79 baseGroups.addAll(regiones?.let { regionGroups(it) } ?: boxes())
80 baseGroups.addAll(v.extraGroups())
81
82 val solution = IntArray(81)
83 fillFull(solution, soloPeers(baseGroups), rng)
84
85 val construido = construir(v, solution, baseGroups, rng)
86
87 val givens = solution.copyOf()
88 dig(givens, construido.reglas, dif.pistasObjetivo, dif.soloLogica, rng)
89
90 return Puzzle(v, dif, index, givens, solution, construido.reglas, regiones, construido.aristas, construido.borde)
91 }
92
93 fun contarSoluciones(grid: IntArray, reglas: Reglas, limite: Int): Int =
94 count(grid.copyOf(), reglas, limite)
95
96 /** Una distribución jigsaw fija (para ilustrar la variante en el menú). */
97 fun jigsawEjemplo(): IntArray = jigsaw(Random(7))
98
99 // ---- Construcción de reglas por variante --------------------------
100
101 private class Construido(val reglas: Reglas, val aristas: List<Arista>, val borde: Borde?)
102
103 private fun construir(v: Variant, sol: IntArray, baseGroups: List<IntArray>, rng: Random): Construido {
104 val allowed = IntArray(81) { TODOS }
105 val bin = Array(81) { ArrayList<BinPeer>() }
106 val aristas = ArrayList<Arista>()
107 var cages = emptyList<Cage>()
108 var vis = emptyList<Vis>()
109 var groups = baseGroups
110 var borde: Borde? = null
111
112 when (v.tipo) {
113 Variant.Tipo.PARIDAD ->
114 for (i in 0 until 81) allowed[i] = if (sol[i] % 2 == 0) PARES else IMPARES
115
116 Variant.Tipo.CONSEC -> adyacentes(true) { a, b ->
117 val consec = abs(sol[a] - sol[b]) == 1
118 val rel = if (consec) Rel.CONSEC else Rel.NO_CONSEC
119 bin[a].add(BinPeer(b, rel)); bin[b].add(BinPeer(a, rel))
120 if (consec) aristas.add(Arista(a, b, Rel.CONSEC))
121 }
122
123 Variant.Tipo.XV -> adyacentes(true) { a, b ->
124 val rel = when (sol[a] + sol[b]) { 5 -> Rel.SUM5; 10 -> Rel.SUM10; else -> Rel.NO_5_10 }
125 bin[a].add(BinPeer(b, rel)); bin[b].add(BinPeer(a, rel))
126 if (rel != Rel.NO_5_10) aristas.add(Arista(a, b, rel))
127 }
128
129 Variant.Tipo.MAYOR -> adyacentes(true, mismaCaja = true) { a, b ->
130 if (sol[a] < sol[b]) {
131 bin[a].add(BinPeer(b, Rel.LT)); bin[b].add(BinPeer(a, Rel.GT)); aristas.add(Arista(a, b, Rel.LT))
132 } else {
133 bin[a].add(BinPeer(b, Rel.GT)); bin[b].add(BinPeer(a, Rel.LT)); aristas.add(Arista(a, b, Rel.GT))
134 }
135 }
136
137 Variant.Tipo.KILLER -> {
138 cages = jaulas(sol, rng)
139 groups = baseGroups + cages.map { it.cells }
140 }
141
142 Variant.Tipo.SKY -> {
143 val vlist = ArrayList<Vis>()
144 val top = IntArray(9); val bot = IntArray(9); val izq = IntArray(9); val der = IntArray(9)
145 for (i in 0 until 9) {
146 val fila = IntArray(9) { i * 9 + it }
147 val col = IntArray(9) { it * 9 + i }
148 izq[i] = visibles(fila.map { sol[it] }); vlist.add(Vis(fila, izq[i]))
149 val filaR = fila.reversedArray(); der[i] = visibles(filaR.map { sol[it] }); vlist.add(Vis(filaR, der[i]))
150 top[i] = visibles(col.map { sol[it] }); vlist.add(Vis(col, top[i]))
151 val colR = col.reversedArray(); bot[i] = visibles(colR.map { sol[it] }); vlist.add(Vis(colR, bot[i]))
152 }
153 vis = vlist
154 borde = Borde(sky = arrayOf(top, bot, izq, der))
155 }
156
157 Variant.Tipo.LITTLE -> {
158 val arrows = ArrayList<LK>()
159 val cs = ArrayList<Cage>()
160 // ↘ desde columnas pares, ↗ desde columnas impares (ancladas arriba).
161 for (c in 0 until 9) {
162 val dir = if (c % 2 == 0) 0 else 1
163 val cells = ArrayList<Int>()
164 var rr = 0; var cc = c
165 while (rr in 0..8 && cc in 0..8) { cells.add(rr * 9 + cc); rr++; cc += if (dir == 0) 1 else -1 }
166 if (cells.size >= 3) {
167 val suma = cells.sumOf { sol[it] }
168 cs.add(Cage(cells.toIntArray(), suma, noRepite = false))
169 arrows.add(LK(c, dir, suma))
170 }
171 }
172 cages = cs
173 borde = Borde(littleKiller = arrows)
174 }
175
176 Variant.Tipo.ROSSINI -> {
177 val ros = Array(4) { IntArray(9) }
178 // lado 0=arr (mira hacia abajo), 1=ab (hacia arriba), 2=izq (derecha), 3=der (izquierda)
179 for (i in 0 until 9) {
180 triple(0, i)?.let { t -> rossiniMarca(sol, t, bin, aristasNo = true)?.let { ros[0][i] = it } }
181 triple(1, i)?.let { t -> rossiniMarca(sol, t, bin)?.let { ros[1][i] = it } }
182 triple(2, i)?.let { t -> rossiniMarca(sol, t, bin)?.let { ros[2][i] = it } }
183 triple(3, i)?.let { t -> rossiniMarca(sol, t, bin)?.let { ros[3][i] = it } }
184 }
185 borde = Borde(rossini = ros)
186 }
187
188 else -> {}
189 }
190
191 val peers = peersOf(groups)
192 val cagesOf = Array(81) { ArrayList<Cage>() }
193 for (c in cages) for (i in c.cells) cagesOf[i].add(c)
194 val visOf = Array(81) { ArrayList<Vis>() }
195 for (vz in vis) for (i in vz.cells) visOf[i].add(vz)
196
197 val reglas = Reglas(
198 groups = groups,
199 peers = peers,
200 allowed = allowed,
201 bin = Array(81) { bin[it] },
202 cagesOf = Array(81) { cagesOf[it] },
203 cages = cages,
204 visOf = Array(81) { visOf[it] },
205 vis = vis,
206 )
207 return Construido(reglas, aristas, borde)
208 }
209
210 /** Las 3 celdas más cercanas a un lado, en orden hacia dentro. */
211 private fun triple(lado: Int, i: Int): IntArray? = when (lado) {
212 0 -> intArrayOf(i, 9 + i, 18 + i) // columna i desde arriba
213 1 -> intArrayOf(72 + i, 63 + i, 54 + i) // columna i desde abajo
214 2 -> intArrayOf(i * 9, i * 9 + 1, i * 9 + 2) // fila i desde izquierda
215 3 -> intArrayOf(i * 9 + 8, i * 9 + 7, i * 9 + 6) // fila i desde derecha
216 else -> null
217 }
218
219 /** Si el triple es estrictamente monótono, añade los binarios y devuelve 1/2 (cre/dec). */
220 private fun rossiniMarca(sol: IntArray, t: IntArray, bin: Array<ArrayList<BinPeer>>, aristasNo: Boolean = false): Int? {
221 val a = sol[t[0]]; val b = sol[t[1]]; val c = sol[t[2]]
222 val creciente = a < b && b < c
223 val decreciente = a > b && b > c
224 if (!creciente && !decreciente) return null
225 val rel = if (creciente) Rel.LT else Rel.GT
226 val inv = if (creciente) Rel.GT else Rel.LT
227 bin[t[0]].add(BinPeer(t[1], rel)); bin[t[1]].add(BinPeer(t[0], inv))
228 bin[t[1]].add(BinPeer(t[2], rel)); bin[t[2]].add(BinPeer(t[1], inv))
229 return if (creciente) 1 else 2
230 }
231
232 private fun visibles(linea: List<Int>): Int {
233 var max = 0; var n = 0
234 for (v in linea) if (v > max) { max = v; n++ }
235 return n
236 }
237
238 // ---- Solver -------------------------------------------------------
239
240 private const val RESUELTO = -2
241 private const val SIN_SALIDA = -1
242
243 private fun candMask(grid: IntArray, c: Int, reglas: Reglas): Int {
244 var m = reglas.allowed[c] and TODOS
245 for (p in reglas.peers[c]) { val v = grid[p]; if (v != 0) m = m and (1 shl v).inv() }
246 for (bp in reglas.bin[c]) { val e = grid[bp.other]; if (e != 0) m = m and permitidosPorRel(e, bp.rel) }
247 return m
248 }
249
250 private fun permitidosPorRel(e: Int, rel: Rel): Int {
251 var m = 0; var d = 1
252 while (d <= 9) {
253 val ok = when (rel) {
254 Rel.CONSEC -> abs(d - e) == 1
255 Rel.NO_CONSEC -> abs(d - e) != 1
256 Rel.SUM5 -> d + e == 5
257 Rel.SUM10 -> d + e == 10
258 Rel.NO_5_10 -> d + e != 5 && d + e != 10
259 Rel.LT -> d < e
260 Rel.GT -> d > e
261 }
262 if (ok) m = m or (1 shl d); d++
263 }
264 return m
265 }
266
267 /** Tras colocar un dígito en [c], ¿siguen viables sus jaulas y visibilidades? */
268 private fun restriccionesOk(grid: IntArray, c: Int, reglas: Reglas): Boolean {
269 for (cage in reglas.cagesOf[c]) {
270 var suma = 0; var llenas = 0
271 for (i in cage.cells) { val v = grid[i]; if (v != 0) { suma += v; llenas++ } }
272 val faltan = cage.cells.size - llenas
273 if (faltan == 0) { if (suma != cage.sum) return false } else {
274 if (suma + faltan > cage.sum) return false
275 val maxAdd = if (cage.noRepite) { var s = 0; var d = 9; repeat(faltan) { s += d; d-- }; s } else faltan * 9
276 if (suma + maxAdd < cage.sum) return false
277 }
278 }
279 for (vz in reglas.visOf[c]) {
280 if (vz.cells.all { grid[it] != 0 }) {
281 if (visibles(vz.cells.map { grid[it] }) != vz.k) return false
282 }
283 }
284 return true
285 }
286
287 private fun fillFull(grid: IntArray, reglas: Reglas, rng: Random): Boolean {
288 val (idx, mask) = mrv(grid, reglas)
289 if (idx == RESUELTO) return true
290 if (idx == SIN_SALIDA) return false
291 val digits = digitsOf(mask).also { shuffle(it, rng) }
292 for (d in digits) {
293 grid[idx] = d
294 if (restriccionesOk(grid, idx, reglas) && fillFull(grid, reglas, rng)) return true
295 grid[idx] = 0
296 }
297 return false
298 }
299
300 private fun count(grid: IntArray, reglas: Reglas, limite: Int): Int {
301 val (idx, mask) = mrv(grid, reglas)
302 if (idx == RESUELTO) return 1
303 if (idx == SIN_SALIDA) return 0
304 var total = 0; var d = 1
305 while (d <= 9) {
306 if (mask and (1 shl d) != 0) {
307 grid[idx] = d
308 if (restriccionesOk(grid, idx, reglas)) total += count(grid, reglas, limite - total)
309 grid[idx] = 0
310 if (total >= limite) break
311 }
312 d++
313 }
314 return total
315 }
316
317 private fun mrv(grid: IntArray, reglas: Reglas): Pair<Int, Int> {
318 var bestIdx = RESUELTO; var bestMask = 0; var bestCount = 10
319 for (c in 0 until 81) {
320 if (grid[c] != 0) continue
321 val cand = candMask(grid, c, reglas)
322 val cnt = Integer.bitCount(cand)
323 if (cnt == 0) return SIN_SALIDA to 0
324 if (cnt < bestCount) { bestCount = cnt; bestIdx = c; bestMask = cand; if (cnt == 1) break }
325 }
326 return bestIdx to bestMask
327 }
328
329 /** ¿Se resuelve solo con singles (desnudos + ocultos)? Mide la dificultad "lógica". */
330 private fun resolublePorSingles(base: IntArray, reglas: Reglas): Boolean {
331 val grid = base.copyOf()
332 while (true) {
333 var avance = false
334 for (c in 0 until 81) if (grid[c] == 0) {
335 val m = candMask(grid, c, reglas)
336 if (m == 0) return false
337 if (Integer.bitCount(m) == 1) { grid[c] = 31 - Integer.numberOfLeadingZeros(m); avance = true }
338 }
339 for (grp in reglas.groups) {
340 var d = 1
341 while (d <= 9) {
342 if (grp.none { grid[it] == d }) {
343 var unico = -1; var cuenta = 0
344 for (cell in grp) if (grid[cell] == 0 && candMask(grid, cell, reglas) and (1 shl d) != 0) { unico = cell; cuenta++ }
345 if (cuenta == 1) { grid[unico] = d; avance = true }
346 }
347 d++
348 }
349 }
350 if (grid.none { it == 0 }) return true
351 if (!avance) return false
352 }
353 }
354
355 private fun dig(grid: IntArray, reglas: Reglas, objetivo: Int, soloLogica: Boolean, rng: Random) {
356 val order = IntArray(81) { it }.also { shuffle(it, rng) }
357 var pistas = 81
358 for (c in order) {
359 if (pistas <= objetivo) break
360 val saved = grid[c]
361 grid[c] = 0
362 val ok = count(grid.copyOf(), reglas, 2) == 1 && (!soloLogica || resolublePorSingles(grid, reglas))
363 if (!ok) grid[c] = saved else pistas--
364 }
365 }
366
367 // ---- Regiones / jaulas --------------------------------------------
368
369 private fun boxes(): List<IntArray> = (0 until 9).map { b ->
370 val r0 = (b / 3) * 3; val c0 = (b % 3) * 3
371 IntArray(9) { i -> (r0 + i / 3) * 9 + (c0 + i % 3) }
372 }
373
374 private fun regionGroups(reg: IntArray): List<IntArray> =
375 (0 until 9).map { id -> (0 until 81).filter { reg[it] == id }.toIntArray() }
376
377 private fun jigsaw(rng: Random): IntArray {
378 repeat(300) {
379 val reg = IntArray(81) { -1 }; val sizes = IntArray(9)
380 val seeds = (0 until 81).toMutableList().also { shuffle2(it, rng) }.take(9)
381 seeds.forEachIndexed { id, cell -> reg[cell] = id; sizes[id] = 1 }
382 var faltan = 81 - 9; var atascado = false
383 while (faltan > 0 && !atascado) {
384 var elegida = -1; var menor = 10
385 for (id in 0 until 9) if (sizes[id] in 1 until 9 && sizes[id] < menor && tieneVecinoLibre(reg, id)) { menor = sizes[id]; elegida = id }
386 if (elegida == -1) { atascado = true; break }
387 val libres = vecinosLibres(reg, elegida)
388 reg[libres[rng.nextInt(libres.size)]] = elegida; sizes[elegida]++; faltan--
389 }
390 if (!atascado && sizes.all { it == 9 }) return reg
391 }
392 return IntArray(81) { (it / 9 / 3) * 3 + (it % 9 / 3) }
393 }
394
395 private fun tieneVecinoLibre(reg: IntArray, id: Int): Boolean {
396 for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) return true
397 return false
398 }
399
400 private fun vecinosLibres(reg: IntArray, id: Int): IntArray {
401 val s = HashSet<Int>()
402 for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) s.add(n)
403 return s.toIntArray()
404 }
405
406 private fun jaulas(sol: IntArray, rng: Random): List<Cage> {
407 val asign = IntArray(81) { -1 }; val cages = ArrayList<Cage>()
408 val order = IntArray(81) { it }.also { shuffle(it, rng) }
409 for (start in order) {
410 if (asign[start] != -1) continue
411 val objetivo = 2 + rng.nextInt(3)
412 val celdas = ArrayList<Int>().apply { add(start) }
413 asign[start] = cages.size
414 val usados = HashSet<Int>().apply { add(sol[start]) }
415 while (celdas.size < objetivo) {
416 val cand = ArrayList<Int>()
417 for (cl in celdas) for (n in ortog(cl)) if (asign[n] == -1 && sol[n] !in usados) cand.add(n)
418 if (cand.isEmpty()) break
419 val n = cand[rng.nextInt(cand.size)]
420 asign[n] = cages.size; celdas.add(n); usados.add(sol[n])
421 }
422 cages.add(Cage(celdas.toIntArray(), celdas.sumOf { sol[it] }, noRepite = true))
423 }
424 return cages
425 }
426
427 // ---- Utilidades ---------------------------------------------------
428
429 private fun peersOf(groups: List<IntArray>): Array<IntArray> {
430 val sets = Array(81) { HashSet<Int>() }
431 for (grp in groups) for (a in grp) for (b in grp) if (a != b) sets[a].add(b)
432 return Array(81) { sets[it].toIntArray() }
433 }
434
435 private fun soloPeers(groups: List<IntArray>) = Reglas(
436 groups, peersOf(groups), IntArray(81) { TODOS },
437 Array(81) { emptyList<BinPeer>() }, Array(81) { emptyList<Cage>() }, emptyList(),
438 Array(81) { emptyList<Vis>() }, emptyList(),
439 )
440
441 private fun ortog(i: Int): IntArray {
442 val r = i / 9; val c = i % 9; val out = ArrayList<Int>(4)
443 if (r > 0) out.add(i - 9); if (r < 8) out.add(i + 9)
444 if (c > 0) out.add(i - 1); if (c < 8) out.add(i + 1)
445 return out.toIntArray()
446 }
447
448 private inline fun adyacentes(soloOrtogonales: Boolean, mismaCaja: Boolean = false, accion: (Int, Int) -> Unit) {
449 for (r in 0 until 9) for (c in 0 until 9) {
450 val a = r * 9 + c
451 if (c < 8 && (!mismaCaja || c % 3 != 2)) accion(a, a + 1)
452 if (r < 8 && (!mismaCaja || r % 3 != 2)) accion(a, a + 9)
453 }
454 }
455
456 private fun seedFor(v: Variant, dif: Dificultad, index: Int): Long {
457 val s = "${v.id}|${dif.ordinal}|$index"
458 var h = 1_125_899_906_842_597L
459 for (ch in s) h = 31 * h + ch.code
460 return h
461 }
462
463 private fun digitsOf(mask: Int): IntArray {
464 val out = ArrayList<Int>(9); var d = 1
465 while (d <= 9) { if (mask and (1 shl d) != 0) out.add(d); d++ }
466 return out.toIntArray()
467 }
468
469 private fun shuffle(a: IntArray, rng: Random) {
470 for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
471 }
472
473 private fun shuffle2(a: MutableList<Int>, rng: Random) {
474 for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
475 }
476}