sergio/humanoid

1package com.rizoma.nonet.game
2
3import com.rizoma.nonet.model.Dificultad
4import com.rizoma.nonet.model.Variant
5import java.util.Random
6
7/** Relación entre dos celdas vecinas (consecutivo, sumas XV, desigualdad). */
8enum class Rel { CONSEC, NO_CONSEC, SUM5, SUM10, NO_5_10, LT, GT }
9
10/** Restricción binaria vista desde una celda: contra [other] debe cumplirse [rel]. */
11class BinPeer(val other: Int, val rel: Rel)
12
13/** Jaula de Killer: un conjunto de celdas que suma [sum] y no repite dígitos. */
14class Cage(val cells: IntArray, val sum: Int)
15
16/** Marca a dibujar entre dos celdas adyacentes [a]-[b] (orientada para < >). */
17class Arista(val a: Int, val b: Int, val rel: Rel)
18
19/**
20 * Todas las restricciones de un puzzle concreto, ya resueltas para el solver:
21 * vecinos de no-repetición, dígitos permitidos por celda (paridad), relaciones
22 * binarias por celda y jaulas. El clásico y las de "región extra" solo usan
23 * [peers] (con [allowed] lleno y sin binarios ni jaulas).
24 */
25class Reglas(
26    val peers: Array<IntArray>,
27    val allowed: IntArray,
28    val bin: Array<List<BinPeer>>,
29    val cagesOf: Array<List<Cage>>,
30    val cages: List<Cage>,
31)
32
33/** Un puzzle generado: pistas, solución única, reglas y datos para dibujar. */
34class Puzzle(
35    val variant: Variant,
36    val dificultad: Dificultad,
37    val index: Int,
38    val givens: IntArray,
39    val solution: IntArray,
40    val reglas: Reglas,
41    val regiones: IntArray?,    // jigsaw: región (0..8) por celda; null = cajas 3×3
42    val aristas: List<Arista>,  // marcas entre celdas (consecutivo/XV/mayor-que)
43) {
44    val peers: Array<IntArray> get() = reglas.peers
45    val id: String get() = "${variant.id}:${dificultad.ordinal}:$index"
46}
47
48/**
49 * Motor unificado de todas las variantes. Genera una solución completa bajo las
50 * regiones de la variante, deriva de ella las restricciones propias (paridad,
51 * marcas, jaulas) y cava celdas mientras la solución siga siendo única.
52 */
53object Motor {
54    private const val TODOS = 0x3FE                 // bits 1..9
55    private const val PARES = (1 shl 2) or (1 shl 4) or (1 shl 6) or (1 shl 8)
56    private const val IMPARES = (1 shl 1) or (1 shl 3) or (1 shl 5) or (1 shl 7) or (1 shl 9)
57
58    fun generar(v: Variant, dif: Dificultad, index: Int): Puzzle {
59        val rng = Random(seedFor(v, dif, index))
60
61        val regiones = if (v.tipo == Variant.Tipo.JIGSAW) jigsaw(rng) else null
62        val baseGroups = ArrayList<IntArray>(36)
63        for (r in 0 until 9) baseGroups.add(IntArray(9) { r * 9 + it })
64        for (c in 0 until 9) baseGroups.add(IntArray(9) { it * 9 + c })
65        baseGroups.addAll(regiones?.let { regionGroups(it) } ?: boxes())
66        baseGroups.addAll(v.extraGroups())
67
68        // Solución completa bajo las regiones (las demás restricciones se derivan).
69        val solution = IntArray(81)
70        fillFull(solution, soloPeers(peersOf(baseGroups)), rng)
71
72        val (reglas, aristas) = construir(v, solution, baseGroups, rng)
73
74        val givens = solution.copyOf()
75        dig(givens, reglas, dif.pistasObjetivo, rng)
76
77        return Puzzle(v, dif, index, givens, solution, reglas, regiones, aristas)
78    }
79
80    /** Cuenta soluciones de [grid] bajo [reglas] hasta [limite]. */
81    fun contarSoluciones(grid: IntArray, reglas: Reglas, limite: Int): Int =
82        count(grid.copyOf(), reglas, limite)
83
84    // ---- Construcción de reglas por variante --------------------------
85
86    private fun construir(
87        v: Variant,
88        sol: IntArray,
89        baseGroups: List<IntArray>,
90        rng: Random,
91    ): Pair<Reglas, List<Arista>> {
92        val allowed = IntArray(81) { TODOS }
93        val bin = Array(81) { ArrayList<BinPeer>() }
94        val aristas = ArrayList<Arista>()
95        var cages = emptyList<Cage>()
96        var groups = baseGroups
97
98        when (v.tipo) {
99            Variant.Tipo.PARIDAD ->
100                for (i in 0 until 81) allowed[i] = if (sol[i] % 2 == 0) PARES else IMPARES
101
102            Variant.Tipo.CONSEC -> adyacentes(soloOrtogonales = true) { a, b ->
103                val consec = kotlin.math.abs(sol[a] - sol[b]) == 1
104                bin[a].add(BinPeer(b, if (consec) Rel.CONSEC else Rel.NO_CONSEC))
105                bin[b].add(BinPeer(a, if (consec) Rel.CONSEC else Rel.NO_CONSEC))
106                if (consec) aristas.add(Arista(a, b, Rel.CONSEC))
107            }
108
109            Variant.Tipo.XV -> adyacentes(soloOrtogonales = true) { a, b ->
110                val s = sol[a] + sol[b]
111                val rel = when (s) { 5 -> Rel.SUM5; 10 -> Rel.SUM10; else -> Rel.NO_5_10 }
112                bin[a].add(BinPeer(b, rel)); bin[b].add(BinPeer(a, rel))
113                if (rel != Rel.NO_5_10) aristas.add(Arista(a, b, rel))
114            }
115
116            Variant.Tipo.MAYOR -> adyacentes(soloOrtogonales = true, mismaCaja = true) { a, b ->
117                // a<b: a lleva LT contra b; b lleva GT contra a. Arista orientada a→b.
118                if (sol[a] < sol[b]) {
119                    bin[a].add(BinPeer(b, Rel.LT)); bin[b].add(BinPeer(a, Rel.GT))
120                    aristas.add(Arista(a, b, Rel.LT))
121                } else {
122                    bin[a].add(BinPeer(b, Rel.GT)); bin[b].add(BinPeer(a, Rel.LT))
123                    aristas.add(Arista(a, b, Rel.GT))
124                }
125            }
126
127            Variant.Tipo.KILLER -> {
128                cages = jaulas(sol, rng)
129                // El no-repetir de cada jaula se enforza vía peers.
130                groups = baseGroups + cages.map { it.cells }
131            }
132
133            else -> {} // REGION / JIGSAW: solo regiones
134        }
135
136        val peers = peersOf(groups)
137        val cagesOf = Array(81) { ArrayList<Cage>() }
138        for (c in cages) for (i in c.cells) cagesOf[i].add(c)
139        val reglas = Reglas(
140            peers = peers,
141            allowed = allowed,
142            bin = Array(81) { bin[it] },
143            cagesOf = Array(81) { cagesOf[it] },
144            cages = cages,
145        )
146        return reglas to aristas
147    }
148
149    // ---- Solver (peers + allowed + binarios + jaulas) -----------------
150
151    private const val RESUELTO = -2
152    private const val SIN_SALIDA = -1
153
154    /** Candidatos válidos de la celda [c]: permitidos − usados por peers − binarios. */
155    private fun candMask(grid: IntArray, c: Int, reglas: Reglas): Int {
156        var m = reglas.allowed[c] and TODOS
157        for (p in reglas.peers[c]) { val v = grid[p]; if (v != 0) m = m and (1 shl v).inv() }
158        for (bp in reglas.bin[c]) {
159            val e = grid[bp.other]
160            if (e != 0) m = m and permitidosPorRel(e, bp.rel)
161        }
162        return m
163    }
164
165    /** Máscara de dígitos d que cumplen rel(d, [e]) contra el vecino con valor [e]. */
166    private fun permitidosPorRel(e: Int, rel: Rel): Int {
167        var m = 0
168        var d = 1
169        while (d <= 9) {
170            val ok = when (rel) {
171                Rel.CONSEC -> kotlin.math.abs(d - e) == 1
172                Rel.NO_CONSEC -> kotlin.math.abs(d - e) != 1
173                Rel.SUM5 -> d + e == 5
174                Rel.SUM10 -> d + e == 10
175                Rel.NO_5_10 -> d + e != 5 && d + e != 10
176                Rel.LT -> d < e
177                Rel.GT -> d > e
178            }
179            if (ok) m = m or (1 shl d)
180            d++
181        }
182        return m
183    }
184
185    /** ¿Las jaulas que tocan [c] siguen siendo viables tras colocar un dígito? */
186    private fun cagesOk(grid: IntArray, c: Int, reglas: Reglas): Boolean {
187        for (cage in reglas.cagesOf[c]) {
188            var suma = 0; var llenas = 0
189            for (i in cage.cells) { val v = grid[i]; if (v != 0) { suma += v; llenas++ } }
190            val faltan = cage.cells.size - llenas
191            if (faltan == 0) {
192                if (suma != cage.sum) return false
193            } else {
194                // Cota: cada celda restante aporta ≥1 distinto y ≤ (9,8,…).
195                if (suma + faltan > cage.sum) return false
196                var maxAdd = 0; var d = 9
197                repeat(faltan) { maxAdd += d; d-- }
198                if (suma + maxAdd < cage.sum) return false
199            }
200        }
201        return true
202    }
203
204    private fun fillFull(grid: IntArray, reglas: Reglas, rng: Random): Boolean {
205        val (idx, mask) = mrv(grid, reglas)
206        if (idx == RESUELTO) return true
207        if (idx == SIN_SALIDA) return false
208        val digits = digitsOf(mask).also { shuffle(it, rng) }
209        for (d in digits) {
210            grid[idx] = d
211            if (cagesOk(grid, idx, reglas) && fillFull(grid, reglas, rng)) return true
212            grid[idx] = 0
213        }
214        return false
215    }
216
217    private fun count(grid: IntArray, reglas: Reglas, limite: Int): Int {
218        val (idx, mask) = mrv(grid, reglas)
219        if (idx == RESUELTO) return 1
220        if (idx == SIN_SALIDA) return 0
221        var total = 0
222        var d = 1
223        while (d <= 9) {
224            if (mask and (1 shl d) != 0) {
225                grid[idx] = d
226                if (cagesOk(grid, idx, reglas)) total += count(grid, reglas, limite - total)
227                grid[idx] = 0
228                if (total >= limite) break
229            }
230            d++
231        }
232        return total
233    }
234
235    private fun mrv(grid: IntArray, reglas: Reglas): Pair<Int, Int> {
236        var bestIdx = RESUELTO; var bestMask = 0; var bestCount = 10
237        for (c in 0 until 81) {
238            if (grid[c] != 0) continue
239            val cand = candMask(grid, c, reglas)
240            val cnt = Integer.bitCount(cand)
241            if (cnt == 0) return SIN_SALIDA to 0
242            if (cnt < bestCount) { bestCount = cnt; bestIdx = c; bestMask = cand; if (cnt == 1) break }
243        }
244        return bestIdx to bestMask
245    }
246
247    private fun dig(grid: IntArray, reglas: Reglas, pistasObjetivo: Int, rng: Random) {
248        val order = IntArray(81) { it }.also { shuffle(it, rng) }
249        var pistas = 81
250        for (c in order) {
251            if (pistas <= pistasObjetivo) break
252            val saved = grid[c]
253            grid[c] = 0
254            if (count(grid.copyOf(), reglas, 2) != 1) grid[c] = saved else pistas--
255        }
256    }
257
258    // ---- Regiones -----------------------------------------------------
259
260    private fun boxes(): List<IntArray> = (0 until 9).map { b ->
261        val r0 = (b / 3) * 3; val c0 = (b % 3) * 3
262        IntArray(9) { i -> (r0 + i / 3) * 9 + (c0 + i % 3) }
263    }
264
265    private fun regionGroups(reg: IntArray): List<IntArray> =
266        (0 until 9).map { id -> (0 until 81).filter { reg[it] == id }.toIntArray() }
267
268    /** 9 regiones conexas de 9 celdas (jigsaw), creciendo la más pequeña con vecino libre. */
269    private fun jigsaw(rng: Random): IntArray {
270        repeat(300) {
271            val reg = IntArray(81) { -1 }
272            val sizes = IntArray(9)
273            val seeds = (0 until 81).toMutableList().also { shuffle2(it, rng) }.take(9)
274            seeds.forEachIndexed { id, cell -> reg[cell] = id; sizes[id] = 1 }
275            var faltan = 81 - 9
276            var atascado = false
277            while (faltan > 0 && !atascado) {
278                // región más pequeña (<9) con algún vecino libre
279                var elegida = -1; var menor = 10
280                for (id in 0 until 9) if (sizes[id] in 1 until 9 && sizes[id] < menor && tieneVecinoLibre(reg, id)) {
281                    menor = sizes[id]; elegida = id
282                }
283                if (elegida == -1) { atascado = true; break }
284                val libres = vecinosLibres(reg, elegida)
285                val cell = libres[rng.nextInt(libres.size)]
286                reg[cell] = elegida; sizes[elegida]++; faltan--
287            }
288            if (!atascado && sizes.all { it == 9 }) return reg
289        }
290        // Fallback improbable: cajas 3×3.
291        val reg = IntArray(81); for (i in 0 until 81) reg[i] = (i / 9 / 3) * 3 + (i % 9 / 3)
292        return reg
293    }
294
295    private fun tieneVecinoLibre(reg: IntArray, id: Int): Boolean {
296        for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) return true
297        return false
298    }
299
300    private fun vecinosLibres(reg: IntArray, id: Int): IntArray {
301        val s = HashSet<Int>()
302        for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) s.add(n)
303        return s.toIntArray()
304    }
305
306    // ---- Jaulas (Killer) ----------------------------------------------
307
308    private fun jaulas(sol: IntArray, rng: Random): List<Cage> {
309        val asign = IntArray(81) { -1 }
310        val cages = ArrayList<Cage>()
311        val order = IntArray(81) { it }.also { shuffle(it, rng) }
312        for (start in order) {
313            if (asign[start] != -1) continue
314            val objetivo = 2 + rng.nextInt(3) // 2..4
315            val celdas = ArrayList<Int>().apply { add(start) }
316            asign[start] = cages.size
317            val usados = HashSet<Int>().apply { add(sol[start]) }
318            while (celdas.size < objetivo) {
319                // vecino libre de cualquier celda de la jaula cuyo dígito no se repita
320                val cand = ArrayList<Int>()
321                for (cl in celdas) for (n in ortog(cl)) if (asign[n] == -1 && sol[n] !in usados) cand.add(n)
322                if (cand.isEmpty()) break
323                val n = cand[rng.nextInt(cand.size)]
324                asign[n] = cages.size; celdas.add(n); usados.add(sol[n])
325            }
326            cages.add(Cage(celdas.toIntArray(), celdas.sumOf { sol[it] }))
327        }
328        return cages
329    }
330
331    // ---- Utilidades ---------------------------------------------------
332
333    private fun peersOf(groups: List<IntArray>): Array<IntArray> {
334        val sets = Array(81) { HashSet<Int>() }
335        for (grp in groups) for (a in grp) for (b in grp) if (a != b) sets[a].add(b)
336        return Array(81) { sets[it].toIntArray() }
337    }
338
339    /** Reglas con solo peers (allowed lleno, sin binarios ni jaulas): para generar la solución. */
340    private fun soloPeers(peers: Array<IntArray>) =
341        Reglas(peers, IntArray(81) { TODOS }, Array(81) { emptyList<BinPeer>() }, Array(81) { emptyList<Cage>() }, emptyList())
342
343    /** Vecinos ortogonales (arriba/abajo/izq/der) de una celda. */
344    private fun ortog(i: Int): IntArray {
345        val r = i / 9; val c = i % 9
346        val out = ArrayList<Int>(4)
347        if (r > 0) out.add(i - 9); if (r < 8) out.add(i + 9)
348        if (c > 0) out.add(i - 1); if (c < 8) out.add(i + 1)
349        return out.toIntArray()
350    }
351
352    /** Recorre cada par adyacente una vez (derecha y abajo), opcionalmente solo dentro de caja. */
353    private inline fun adyacentes(soloOrtogonales: Boolean, mismaCaja: Boolean = false, accion: (Int, Int) -> Unit) {
354        for (r in 0 until 9) for (c in 0 until 9) {
355            val a = r * 9 + c
356            if (c < 8) { val b = a + 1; if (!mismaCaja || c % 3 != 2) accion(a, b) }
357            if (r < 8) { val b = a + 9; if (!mismaCaja || r % 3 != 2) accion(a, b) }
358        }
359    }
360
361    private fun seedFor(v: Variant, dif: Dificultad, index: Int): Long {
362        val s = "${v.id}|${dif.ordinal}|$index"
363        var h = 1_125_899_906_842_597L
364        for (ch in s) h = 31 * h + ch.code
365        return h
366    }
367
368    private fun digitsOf(mask: Int): IntArray {
369        val out = ArrayList<Int>(9)
370        var d = 1
371        while (d <= 9) { if (mask and (1 shl d) != 0) out.add(d); d++ }
372        return out.toIntArray()
373    }
374
375    private fun shuffle(a: IntArray, rng: Random) {
376        for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
377    }
378
379    private fun shuffle2(a: MutableList<Int>, rng: Random) {
380        for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
381    }
382}