Tamaño del tablero
Soluciones totales para 6 reinas: 4
Tablero
🔍 Probando: Probar una reina en columna 1, fila 1.
Intentos1
Retrocesos0
Reinas colocadas0 / 6
Paso 1 de 368
350 ms
Cargando aplicación...
Preparando tu experiencia meskeIA
Observa el algoritmo de vuelta atrás resolviendo el problema de las N reinas: prueba una casilla, descarta las atacadas, coloca la reina y retrocede cuando se queda sin opciones.
Vuelta atrás, poda y el problema de las N reinas
| Técnica | Idea | Cuándo encaja |
|---|---|---|
| Fuerza bruta | Genera todas las combinaciones y filtra al final | Espacios muy pequeños |
| Backtracking | Construye y poda en cuanto algo es inválido | Restricciones que descartan pronto |
| Voraz (greedy) | Elige lo mejor en cada paso sin deshacer | Cuando la decisión local es óptima global |
| Programación dinámica | Reutiliza subproblemas solapados | Subestructura óptima + solapamiento |
| Ramificación y poda | Backtracking + cotas para podar más | Optimización combinatoria |
Podar es abandonar una rama del árbol de búsqueda en cuanto se sabe que no puede llevar a una solución válida. En las N reinas, si una casilla está atacada no se explora qué pasaría colocando ahí la reina: se descarta de inmediato. Cuanto antes podas, menos trabajo haces.
En el simulador, cada "conflicto" es una poda.
Porque garantiza que nunca habrá dos reinas en la misma columna, así que solo hay que comprobar filas y diagonales. Reduce el problema a elegir una fila por columna, lo que hace el backtracking mucho más eficiente que probar todas las casillas del tablero.
Es una forma de simetría que simplifica el espacio de búsqueda.
Si existe, sí: el backtracking es completo, explora sistemáticamente todo el espacio salvo las ramas podadas (que por definición no contienen soluciones). Si no hay solución, lo acabará confirmando tras agotar todas las ramas. Otra cosa es el tiempo que tarde.
Para tableros grandes, el tiempo puede dispararse: es exponencial en el peor caso.
En el peor caso es exponencial, porque el árbol de posibilidades crece muy rápido. La poda y un buen orden de exploración reducen drásticamente las ramas visitadas, pero no cambian la cota teórica. Por eso, para problemas grandes, se combinan con heurísticas o cotas (ramificación y poda).
Compara intentos para 4, 6 y 8 reinas: el crecimiento es claro.
El backtracking es esencialmente una búsqueda en profundidad (DFS) sobre el árbol de soluciones parciales, con la diferencia clave de que poda ramas inválidas y deshace la última decisión al retroceder. Todo backtracking es un DFS, pero no todo DFS poda.
La "vuelta atrás" es el deshacer del DFS al salir de una rama.
¿Qué construyes paso a paso? En las N reinas, una reina colocada por columna.
Itera las opciones de la decisión actual (cada fila posible de la columna).
Si el candidato viola una restricción, descártalo sin explorar más allá.
Si es válido, añádelo a la solución parcial y resuelve el resto recursivamente.
Si la recursión falla, quita el candidato (vuelta atrás) y prueba el siguiente.
Comprobar la validez lo antes posible elimina ramas enteras y acelera todo.
Probar primero las opciones más prometedoras (heurísticas) encuentra la solución antes.
Al retroceder, revierte el estado al de antes de la decisión, sin dejar rastro.
Una reina por columna o fijar la primera fila reduce mucho el espacio de búsqueda.
Si el espacio es enorme, combina con cotas (ramificación y poda) o heurísticas.
4 reinas → 2 soluciones; 8 reinas → 92. Si no te salen, hay un bug.