UAX · Estructura de datos y algoritmos II · backtracking
N reinas, paso a paso
Colocar N reinas en un tablero de N × N sin que ninguna ataque a otra. Una reina por fila: en cada fila se prueban las columnas de izquierda a derecha, se descarta la casilla atacada y, si la fila se queda sin opciones, se vuelve a la anterior.
El tablero
casilla que se prueba reina colocada casilla atacada
Paso 0
Pulsa Ejecutar y avanza solo, o ve paso a paso con Siguiente.
Estado
0llamadas
0casillas podadas
0vueltas atrás
0soluciones
reinas[fila] = columna
columnas ocupadas · índice col
diagonal principal ocupada · índice fila − col
diagonal secundaria ocupada · índice fila + col
El código que se está ejecutando
def coloca(fila): if fila == n: # todas puestas soluciones.append(reinas[:]) return for col in range(n): if col in cols or fila-col in d1 or fila+col in d2: continue # poda reinas[fila] = col; cols.add(col); d1.add(fila-col); d2.add(fila+col) coloca(fila + 1) cols.remove(col); d1.remove(fila-col); d2.remove(fila+col) # vuelta atrás