package com.rizoma.nonet.game

import com.rizoma.nonet.model.Dificultad
import com.rizoma.nonet.model.Variant
import java.util.Random

/** Relación entre dos celdas vecinas (consecutivo, sumas XV, desigualdad). */
enum class Rel { CONSEC, NO_CONSEC, SUM5, SUM10, NO_5_10, LT, GT }

/** Restricción binaria vista desde una celda: contra [other] debe cumplirse [rel]. */
class BinPeer(val other: Int, val rel: Rel)

/** Jaula de Killer: un conjunto de celdas que suma [sum] y no repite dígitos. */
class Cage(val cells: IntArray, val sum: Int)

/** Marca a dibujar entre dos celdas adyacentes [a]-[b] (orientada para < >). */
class Arista(val a: Int, val b: Int, val rel: Rel)

/**
 * Todas las restricciones de un puzzle concreto, ya resueltas para el solver:
 * vecinos de no-repetición, dígitos permitidos por celda (paridad), relaciones
 * binarias por celda y jaulas. El clásico y las de "región extra" solo usan
 * [peers] (con [allowed] lleno y sin binarios ni jaulas).
 */
class Reglas(
    val peers: Array<IntArray>,
    val allowed: IntArray,
    val bin: Array<List<BinPeer>>,
    val cagesOf: Array<List<Cage>>,
    val cages: List<Cage>,
)

/** Un puzzle generado: pistas, solución única, reglas y datos para dibujar. */
class Puzzle(
    val variant: Variant,
    val dificultad: Dificultad,
    val index: Int,
    val givens: IntArray,
    val solution: IntArray,
    val reglas: Reglas,
    val regiones: IntArray?,    // jigsaw: región (0..8) por celda; null = cajas 3×3
    val aristas: List<Arista>,  // marcas entre celdas (consecutivo/XV/mayor-que)
) {
    val peers: Array<IntArray> get() = reglas.peers
    val id: String get() = "${variant.id}:${dificultad.ordinal}:$index"
}

/**
 * Motor unificado de todas las variantes. Genera una solución completa bajo las
 * regiones de la variante, deriva de ella las restricciones propias (paridad,
 * marcas, jaulas) y cava celdas mientras la solución siga siendo única.
 */
object Motor {
    private const val TODOS = 0x3FE                 // bits 1..9
    private const val PARES = (1 shl 2) or (1 shl 4) or (1 shl 6) or (1 shl 8)
    private const val IMPARES = (1 shl 1) or (1 shl 3) or (1 shl 5) or (1 shl 7) or (1 shl 9)

    fun generar(v: Variant, dif: Dificultad, index: Int): Puzzle {
        val rng = Random(seedFor(v, dif, index))

        val regiones = if (v.tipo == Variant.Tipo.JIGSAW) jigsaw(rng) else null
        val baseGroups = ArrayList<IntArray>(36)
        for (r in 0 until 9) baseGroups.add(IntArray(9) { r * 9 + it })
        for (c in 0 until 9) baseGroups.add(IntArray(9) { it * 9 + c })
        baseGroups.addAll(regiones?.let { regionGroups(it) } ?: boxes())
        baseGroups.addAll(v.extraGroups())

        // Solución completa bajo las regiones (las demás restricciones se derivan).
        val solution = IntArray(81)
        fillFull(solution, soloPeers(peersOf(baseGroups)), rng)

        val (reglas, aristas) = construir(v, solution, baseGroups, rng)

        val givens = solution.copyOf()
        dig(givens, reglas, dif.pistasObjetivo, rng)

        return Puzzle(v, dif, index, givens, solution, reglas, regiones, aristas)
    }

    /** Cuenta soluciones de [grid] bajo [reglas] hasta [limite]. */
    fun contarSoluciones(grid: IntArray, reglas: Reglas, limite: Int): Int =
        count(grid.copyOf(), reglas, limite)

    // ---- Construcción de reglas por variante --------------------------

    private fun construir(
        v: Variant,
        sol: IntArray,
        baseGroups: List<IntArray>,
        rng: Random,
    ): Pair<Reglas, List<Arista>> {
        val allowed = IntArray(81) { TODOS }
        val bin = Array(81) { ArrayList<BinPeer>() }
        val aristas = ArrayList<Arista>()
        var cages = emptyList<Cage>()
        var groups = baseGroups

        when (v.tipo) {
            Variant.Tipo.PARIDAD ->
                for (i in 0 until 81) allowed[i] = if (sol[i] % 2 == 0) PARES else IMPARES

            Variant.Tipo.CONSEC -> adyacentes(soloOrtogonales = true) { a, b ->
                val consec = kotlin.math.abs(sol[a] - sol[b]) == 1
                bin[a].add(BinPeer(b, if (consec) Rel.CONSEC else Rel.NO_CONSEC))
                bin[b].add(BinPeer(a, if (consec) Rel.CONSEC else Rel.NO_CONSEC))
                if (consec) aristas.add(Arista(a, b, Rel.CONSEC))
            }

            Variant.Tipo.XV -> adyacentes(soloOrtogonales = true) { a, b ->
                val s = sol[a] + sol[b]
                val rel = when (s) { 5 -> Rel.SUM5; 10 -> Rel.SUM10; else -> Rel.NO_5_10 }
                bin[a].add(BinPeer(b, rel)); bin[b].add(BinPeer(a, rel))
                if (rel != Rel.NO_5_10) aristas.add(Arista(a, b, rel))
            }

            Variant.Tipo.MAYOR -> adyacentes(soloOrtogonales = true, mismaCaja = true) { a, b ->
                // a<b: a lleva LT contra b; b lleva GT contra a. Arista orientada a→b.
                if (sol[a] < sol[b]) {
                    bin[a].add(BinPeer(b, Rel.LT)); bin[b].add(BinPeer(a, Rel.GT))
                    aristas.add(Arista(a, b, Rel.LT))
                } else {
                    bin[a].add(BinPeer(b, Rel.GT)); bin[b].add(BinPeer(a, Rel.LT))
                    aristas.add(Arista(a, b, Rel.GT))
                }
            }

            Variant.Tipo.KILLER -> {
                cages = jaulas(sol, rng)
                // El no-repetir de cada jaula se enforza vía peers.
                groups = baseGroups + cages.map { it.cells }
            }

            else -> {} // REGION / JIGSAW: solo regiones
        }

        val peers = peersOf(groups)
        val cagesOf = Array(81) { ArrayList<Cage>() }
        for (c in cages) for (i in c.cells) cagesOf[i].add(c)
        val reglas = Reglas(
            peers = peers,
            allowed = allowed,
            bin = Array(81) { bin[it] },
            cagesOf = Array(81) { cagesOf[it] },
            cages = cages,
        )
        return reglas to aristas
    }

    // ---- Solver (peers + allowed + binarios + jaulas) -----------------

    private const val RESUELTO = -2
    private const val SIN_SALIDA = -1

    /** Candidatos válidos de la celda [c]: permitidos − usados por peers − binarios. */
    private fun candMask(grid: IntArray, c: Int, reglas: Reglas): Int {
        var m = reglas.allowed[c] and TODOS
        for (p in reglas.peers[c]) { val v = grid[p]; if (v != 0) m = m and (1 shl v).inv() }
        for (bp in reglas.bin[c]) {
            val e = grid[bp.other]
            if (e != 0) m = m and permitidosPorRel(e, bp.rel)
        }
        return m
    }

    /** Máscara de dígitos d que cumplen rel(d, [e]) contra el vecino con valor [e]. */
    private fun permitidosPorRel(e: Int, rel: Rel): Int {
        var m = 0
        var d = 1
        while (d <= 9) {
            val ok = when (rel) {
                Rel.CONSEC -> kotlin.math.abs(d - e) == 1
                Rel.NO_CONSEC -> kotlin.math.abs(d - e) != 1
                Rel.SUM5 -> d + e == 5
                Rel.SUM10 -> d + e == 10
                Rel.NO_5_10 -> d + e != 5 && d + e != 10
                Rel.LT -> d < e
                Rel.GT -> d > e
            }
            if (ok) m = m or (1 shl d)
            d++
        }
        return m
    }

    /** ¿Las jaulas que tocan [c] siguen siendo viables tras colocar un dígito? */
    private fun cagesOk(grid: IntArray, c: Int, reglas: Reglas): Boolean {
        for (cage in reglas.cagesOf[c]) {
            var suma = 0; var llenas = 0
            for (i in cage.cells) { val v = grid[i]; if (v != 0) { suma += v; llenas++ } }
            val faltan = cage.cells.size - llenas
            if (faltan == 0) {
                if (suma != cage.sum) return false
            } else {
                // Cota: cada celda restante aporta ≥1 distinto y ≤ (9,8,…).
                if (suma + faltan > cage.sum) return false
                var maxAdd = 0; var d = 9
                repeat(faltan) { maxAdd += d; d-- }
                if (suma + maxAdd < cage.sum) return false
            }
        }
        return true
    }

    private fun fillFull(grid: IntArray, reglas: Reglas, rng: Random): Boolean {
        val (idx, mask) = mrv(grid, reglas)
        if (idx == RESUELTO) return true
        if (idx == SIN_SALIDA) return false
        val digits = digitsOf(mask).also { shuffle(it, rng) }
        for (d in digits) {
            grid[idx] = d
            if (cagesOk(grid, idx, reglas) && fillFull(grid, reglas, rng)) return true
            grid[idx] = 0
        }
        return false
    }

    private fun count(grid: IntArray, reglas: Reglas, limite: Int): Int {
        val (idx, mask) = mrv(grid, reglas)
        if (idx == RESUELTO) return 1
        if (idx == SIN_SALIDA) return 0
        var total = 0
        var d = 1
        while (d <= 9) {
            if (mask and (1 shl d) != 0) {
                grid[idx] = d
                if (cagesOk(grid, idx, reglas)) total += count(grid, reglas, limite - total)
                grid[idx] = 0
                if (total >= limite) break
            }
            d++
        }
        return total
    }

    private fun mrv(grid: IntArray, reglas: Reglas): Pair<Int, Int> {
        var bestIdx = RESUELTO; var bestMask = 0; var bestCount = 10
        for (c in 0 until 81) {
            if (grid[c] != 0) continue
            val cand = candMask(grid, c, reglas)
            val cnt = Integer.bitCount(cand)
            if (cnt == 0) return SIN_SALIDA to 0
            if (cnt < bestCount) { bestCount = cnt; bestIdx = c; bestMask = cand; if (cnt == 1) break }
        }
        return bestIdx to bestMask
    }

    private fun dig(grid: IntArray, reglas: Reglas, pistasObjetivo: Int, rng: Random) {
        val order = IntArray(81) { it }.also { shuffle(it, rng) }
        var pistas = 81
        for (c in order) {
            if (pistas <= pistasObjetivo) break
            val saved = grid[c]
            grid[c] = 0
            if (count(grid.copyOf(), reglas, 2) != 1) grid[c] = saved else pistas--
        }
    }

    // ---- Regiones -----------------------------------------------------

    private fun boxes(): List<IntArray> = (0 until 9).map { b ->
        val r0 = (b / 3) * 3; val c0 = (b % 3) * 3
        IntArray(9) { i -> (r0 + i / 3) * 9 + (c0 + i % 3) }
    }

    private fun regionGroups(reg: IntArray): List<IntArray> =
        (0 until 9).map { id -> (0 until 81).filter { reg[it] == id }.toIntArray() }

    /** 9 regiones conexas de 9 celdas (jigsaw), creciendo la más pequeña con vecino libre. */
    private fun jigsaw(rng: Random): IntArray {
        repeat(300) {
            val reg = IntArray(81) { -1 }
            val sizes = IntArray(9)
            val seeds = (0 until 81).toMutableList().also { shuffle2(it, rng) }.take(9)
            seeds.forEachIndexed { id, cell -> reg[cell] = id; sizes[id] = 1 }
            var faltan = 81 - 9
            var atascado = false
            while (faltan > 0 && !atascado) {
                // región más pequeña (<9) con algún vecino libre
                var elegida = -1; var menor = 10
                for (id in 0 until 9) if (sizes[id] in 1 until 9 && sizes[id] < menor && tieneVecinoLibre(reg, id)) {
                    menor = sizes[id]; elegida = id
                }
                if (elegida == -1) { atascado = true; break }
                val libres = vecinosLibres(reg, elegida)
                val cell = libres[rng.nextInt(libres.size)]
                reg[cell] = elegida; sizes[elegida]++; faltan--
            }
            if (!atascado && sizes.all { it == 9 }) return reg
        }
        // Fallback improbable: cajas 3×3.
        val reg = IntArray(81); for (i in 0 until 81) reg[i] = (i / 9 / 3) * 3 + (i % 9 / 3)
        return reg
    }

    private fun tieneVecinoLibre(reg: IntArray, id: Int): Boolean {
        for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) return true
        return false
    }

    private fun vecinosLibres(reg: IntArray, id: Int): IntArray {
        val s = HashSet<Int>()
        for (i in 0 until 81) if (reg[i] == id) for (n in ortog(i)) if (reg[n] == -1) s.add(n)
        return s.toIntArray()
    }

    // ---- Jaulas (Killer) ----------------------------------------------

    private fun jaulas(sol: IntArray, rng: Random): List<Cage> {
        val asign = IntArray(81) { -1 }
        val cages = ArrayList<Cage>()
        val order = IntArray(81) { it }.also { shuffle(it, rng) }
        for (start in order) {
            if (asign[start] != -1) continue
            val objetivo = 2 + rng.nextInt(3) // 2..4
            val celdas = ArrayList<Int>().apply { add(start) }
            asign[start] = cages.size
            val usados = HashSet<Int>().apply { add(sol[start]) }
            while (celdas.size < objetivo) {
                // vecino libre de cualquier celda de la jaula cuyo dígito no se repita
                val cand = ArrayList<Int>()
                for (cl in celdas) for (n in ortog(cl)) if (asign[n] == -1 && sol[n] !in usados) cand.add(n)
                if (cand.isEmpty()) break
                val n = cand[rng.nextInt(cand.size)]
                asign[n] = cages.size; celdas.add(n); usados.add(sol[n])
            }
            cages.add(Cage(celdas.toIntArray(), celdas.sumOf { sol[it] }))
        }
        return cages
    }

    // ---- Utilidades ---------------------------------------------------

    private fun peersOf(groups: List<IntArray>): Array<IntArray> {
        val sets = Array(81) { HashSet<Int>() }
        for (grp in groups) for (a in grp) for (b in grp) if (a != b) sets[a].add(b)
        return Array(81) { sets[it].toIntArray() }
    }

    /** Reglas con solo peers (allowed lleno, sin binarios ni jaulas): para generar la solución. */
    private fun soloPeers(peers: Array<IntArray>) =
        Reglas(peers, IntArray(81) { TODOS }, Array(81) { emptyList<BinPeer>() }, Array(81) { emptyList<Cage>() }, emptyList())

    /** Vecinos ortogonales (arriba/abajo/izq/der) de una celda. */
    private fun ortog(i: Int): IntArray {
        val r = i / 9; val c = i % 9
        val out = ArrayList<Int>(4)
        if (r > 0) out.add(i - 9); if (r < 8) out.add(i + 9)
        if (c > 0) out.add(i - 1); if (c < 8) out.add(i + 1)
        return out.toIntArray()
    }

    /** Recorre cada par adyacente una vez (derecha y abajo), opcionalmente solo dentro de caja. */
    private inline fun adyacentes(soloOrtogonales: Boolean, mismaCaja: Boolean = false, accion: (Int, Int) -> Unit) {
        for (r in 0 until 9) for (c in 0 until 9) {
            val a = r * 9 + c
            if (c < 8) { val b = a + 1; if (!mismaCaja || c % 3 != 2) accion(a, b) }
            if (r < 8) { val b = a + 9; if (!mismaCaja || r % 3 != 2) accion(a, b) }
        }
    }

    private fun seedFor(v: Variant, dif: Dificultad, index: Int): Long {
        val s = "${v.id}|${dif.ordinal}|$index"
        var h = 1_125_899_906_842_597L
        for (ch in s) h = 31 * h + ch.code
        return h
    }

    private fun digitsOf(mask: Int): IntArray {
        val out = ArrayList<Int>(9)
        var d = 1
        while (d <= 9) { if (mask and (1 shl d) != 0) out.add(d); d++ }
        return out.toIntArray()
    }

    private fun shuffle(a: IntArray, rng: Random) {
        for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
    }

    private fun shuffle2(a: MutableList<Int>, rng: Random) {
        for (i in a.indices.reversed()) { val j = rng.nextInt(i + 1); val t = a[i]; a[i] = a[j]; a[j] = t }
    }
}