Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Backtracking Visualizer

N-Queens

Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Recursion Depth 0
Pruned Branches 0
Status Ready
Empty
Placing / Active
Conflict / Pruned
Solution
Placed
Step Explanation

Select an algorithm and press Play to watch the search tree explore and backtrack.

—
Pseudocode 
 
 
 
 
  
 
 
N-Queens Problem
  
 
  Intermediate (3/5)
 
~1 hora   Place N queens on N×N board  Backtracking: try position, recurse, undo  Constraint: no two queens attack  N-Queens count vs single solution  
Prereqs: Backtracking, Recursión  
 
Quick Reference
N-Queens
N-Queens places n queens on an n×n board so that no two queens attack each other (no shared row, column, or diagonal). Backtracking places queens row by row and undoes placements that lead to dead ends.

Difficulty: Intermediate (3/5)
backtracking
Complexity
Best Time
O(n!)
Average Time
O(n!)
Worst Time
O(n!)
Space
O(n)
When to Use
Use N-Queens to learn backtracking, constraint satisfaction, and the classic board-search pattern that generalizes to scheduling and puzzle solving.
Pros
  • Clean demonstration of the backtracking pattern
  • The board makes every prune/backtrack visible
  • Pruning via precomputed attack sets speeds it up massively
Cons
  • Exponential worst case O(n!)
  • Simple solver returns only the first solution
  • Checking diagonals naively is O(n) per move
History
The n-queens problem was first posed by Max Bezzel in 1848 and solved for n=8 by Franz Nauck in 1850. It became a classic programming exercise in the early days of computer science.
 
 
N-Queens Problem es el problema clásico de backtracking: coloca N reinas en un tablero N×N de forma que ninguna se ataquen entre sí (no compartan fila, columna, ni diagonal).


Es el problema introductorio por excelencia para entender backtracking: prueba una posición, avanza recursivamente, y deshace (backtrack) si la posición no lleva a una solución válida.


Cómo Funciona


    

  1. Inicializa tablero vacío N×N.
    2. 

  2. Coloca una reina en la fila actual (por filas para evitar conflicts en fila).
    3. 

  3. Prueba cada columna de la fila:

      

    • Si es segura (no hay otra reina en columna ni diagonales): colócala y avanza a la siguiente fila.
      • 

    • Si no es segura: prueba la siguiente columna.
      • 

    

    4. 

  4. Backtrack: si ninguna columna funciona en la fila actual, deshace la última colocación y prueba otra opción.
    5. 

  5. Termina cuando todas las N reinas están colocadas (solución) o cuando todas las opciones se agotan (sin solución).
    6. 



Idea Clave


Backtracking es DFS con poda: exploras el espacio de soluciones de forma sistemática, pero descartas ramas enteras cuando una decisión parcial viola una restricción.


La clave de eficiencia es la pruning: si colocas una reina en (row, col) y hay un ataque, no sigas explorando esa rama.


Ejemplo Trabajado


N = 4. Busca una solución.


Proceso:


    

  • Fila 0: prueba col 0 → segura. Coloca Q en (0,0).
    • 

  • Fila 1: prueba col 0 (ataca), col 1 (ataca diagonal), col 2 → segura. Coloca Q en (1,2).
    • 

  • Fila 2: prueba col 0 (ataca), col 1 (segura). Coloca Q en (2,1).
    • 

  • Fila 3: prueba col 0 (ataca), col 1 (ataca), col 2 (ataca), col 3 (segura). Coloca Q en (3,3).
    • 



Solución: [1, 3, 0, 2] (columna de reina en cada fila).


Representación:


. Q . .
. . . Q
Q . . .
. . Q .


Casos Extremos y Trampas


    

  • N = 1 — trivial, una solución.
    • 

  • N = 2, 3 — no tienen solución (imposible colocar sin ataque).
    • 

  • N = 4 — 2 soluciones.
    • 

  • Contar todas — no pares en la primera; explora todas las ramas.
    • 



Variantes



























ProblemaObjetivoComplejidad
N-QueensUna soluciónO(N!) backtrack
N-Queens CountTodas las solucionesO(N!) backtrack
N-Queens BitmaskOptimizadaO(N!) pero rápida


Aplicaciones


    

  • SAT solving — N-Queens es NP-completo
    • 

  • Asignación de recursos — scheduling sin conflictos
    • 

  • Criptografía — diseño de sistemas sin colisiones
    • 

  • Enseñanza — ejemplo canónico de backtracking
    • 



Trayectoria de Práctica


    

  1. Implementa N-Queens backtracking; encuentra una solución para N=8.
    2. 

  2. Extiende para contar todas las soluciones.
    3. 

  3. Optimiza con bitmask: representa columnas y diagonales como bits.
    4. 

  4. ¿Por qué N=2 y N=3 no tienen solución? Demuéstralo.
    5. 

  5. Investiga N-Queens como grafo: ¿cuántos movimientos de un caballo para resolver?
    6.