Lección 19 · 19 de 20
Recursión y vuelta atrás · C
Resuelva el problema de las N reinas en C con recursión y vuelta atrás (backtracking): probar una opción, seguir y deshacerla si no lleva a nada.
El problema de las N reinas consiste en colocar N reinas en un tablero de N×N sin que ninguna ataque a otra: ni en la misma fila, ni en la misma columna, ni en la misma diagonal. Como cada fila lleva exactamente una reina, basta guardar en col[r] la columna de la reina de la fila r.
safe comprueba si una reina puede ir en la columna c de la fila row mirando solo las filas anteriores. Hay ataque si comparten columna (col[r] == c) o diagonal: en una diagonal, la distancia entre columnas es igual a la distancia entre filas, abs(col[r] - c) == row - r.
place es recursiva y aplica la vuelta atrás (*backtracking*): prueba cada columna de la fila actual; si es segura, coloca la reina y se llama a sí misma para la fila siguiente. Cuando esa llamada termina, haya encontrado algo o no, el bucle pasa a la columna siguiente, y el valor de col[row] se sobrescribe: así se deshace la elección sin código extra.
El caso base es row == N: todas las filas tienen reina, así que es una solución. Se cuentan todas y solo se dibuja la primera. Para 6 reinas hay 4 soluciones; para 8, el tablero de ajedrez, 92.
La vuelta atrás sirve para cualquier problema de «elegir, comprobar y retroceder»: sudokus, laberintos, horarios o permutaciones. Las ramas que no son seguras se abandonan pronto, y por eso es mucho más rápida que probar todas las combinaciones.
Código · main.c
#include <stdio.h>#include <stdlib.h>#define N 6int col[N], solutions = 0; // col[r]: the column of the queen in row r// Can a queen go at (row, c) without attacking the rows above?int safe(int row, int c) { for (int r = 0; r < row; r++) if (col[r] == c || abs(col[r] - c) == row - r) return 0; // column or diagonal return 1;}void place(int row) { if (row == N) { // all rows filled: a solution if (++solutions == 1) // draw only the first one for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) printf(c == col[r] ? " Q" : " ."); printf("\n"); } return; } for (int c = 0; c < N; c++) if (safe(row, c)) { col[row] = c; // try this column... place(row + 1); // ...solve the rest recursively... } // ...and backtrack: the loop tries the next one}int main(void) { place(0); printf("%d queens on a %dx%d board: %d solutions\n", N, N, N, solutions); return 0;}Salida · cc main.c -o main && ./main
. Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q . 6 queens on a 6x6 board: 4 solutions
Para recordar
- Recursión: una función que se llama a sí misma con un problema menor.
- Siempre hace falta un caso base que detenga la recursión.
- Vuelta atrás: elegir, seguir y deshacer la elección.
- Descartar pronto las ramas imposibles ahorra casi todo el trabajo.
Ejercicio
Cambie N a 8 y compruebe que salen 92 soluciones; después cuente también cuántas veces se llama a safe y compárelo con las 8⁸ formas de poner una reina por fila.