¿Has jugado alguna vez al ajedrez? Si es así, ya sabes que la reina es la pieza más importante y que puede mover cualquier número de casillas en vertical, horizontal o diagonal. Si no lo has hecho, no te preocupes: hoy sólo aprenderemos a colocar 8 reinas en el tablero de ajedrez de forma que ninguna reina pueda moverse a una casilla ocupada por otra reina. En la jerga del ajedrez, decimos que las reinas no podrán atacarse entre sí. ¿Cómo lo hacemos? Usamos el backtracking.
El algoritmo de backtracking encuentra una solución a problemas en los que se deben respetar algunas restricciones. Prueba todas las soluciones posibles hasta encontrar la correcta. Probemos un ejemplo, con cuatro reinas y un tablero pequeño. Empezaremos colocando la primera reina:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. También te mostrará muchas otras estrategias computacionales que te ayudarán a resolver problemas interesantes!
Ahora que sabes cómo funciona el backtracking, podemos resolver el problema de las 8 reinas a tamaño completo. A continuación, hay un tablero de ajedrez con el que puedes jugar para practicar tus habilidadesy encontrar una solución. Empieza por colocar la primera reina haciendo clic en la casilla superior izquierda del tablero. Verás que la reina que has colocado aparecerá en la lista de «Reinas actuales».
Reinas actuales
Ahora puedes colocar otra reina en una posición que impida que se ataquen entre sí. Nuestra primera reina está en a8, la segunda, por ejemplo, puede colocarse en c7. Sigue colocando reinas hasta que no quede ninguna casilla segura en el tablero. En ese momento, es el momento de retroceder haciendo clic en «deshacer». Esto borrará la última reina que hayas colocado y te permitirá elegir otra casilla para colocarla. También puedes eliminar una reina del tablero haciendo clic directamente sobre ella.
Al jugar al juego interactivo, puedes empezar a tener una sensación de retroceso. Como humanos, nos puede resultar difícil llevar la cuenta de todas las colocaciones de reinas anteriores. ¡Aquí es donde la programación ayuda! A continuación, puedes encontrar una animación generada por un programa que demuestra sus impecables habilidades de backtracking:
Pseudocódigo:
- Comienza colocando la primera reina en la casilla superior izquierda del tablero.
- Si hemos colocado las 8 reinas, hemos terminado. Si no, ¿es posible colocar otra reina en una posición segura?
- Si la respuesta es afirmativa, entonces marcamos esto como parte de la solución, y volvemos al punto 2.
- Si la respuesta es negativa, entonces cambiamos la posición de la reina anterior (retroceso) y volvemos al punto 2.
.