sábado, noviembre 29, 2008

Antes de empezar con las 8 damas...

Advertencia: Es muy importante que no busquéis la solución. Hay que conseguirla sin ser contaminado por estructuras de datos y programas (algoritmos) de otros.

Yo hace muchos años que no he visto la solución y aún así creo que ya no es lo mismo. Ver el programa que lo resuelve es como cuando te explican un truco de magia. Ya no tiene ningún interés.

Además hay otra cosa:

Gauss, el más grande entre los grandes no consiguió dar con el método para obtener todas las soluciones.

En un primer momento presentó 72 casos de éxito que luego amplió a 76.

Sería muy interesante encontrar el fallo de Gauss. No somos tan grandes como él, pero tenemos alguna ventaja como el conocimiento la programación estructurada y un ordenador.

Después de todo este rollo voy a entrar en materia.

Un tablero de ajedrez es así.
De esos tableros que ha encontrado Google, muchos están mal colocados. Aunque no importe para este problema, si puede influenciar en otros, y es muy importante en el juego del ajedrez:

Siempre que veais un tablero, en la primera fila (la más cercana a vosotros) el cuadro más a la izquierda debe ser una casilla negra. Luego la dama va en la casilla de su color.

Volvamos al problema.

El tablero de ajedrez tiene 8 filas y 8 columnas. Queremos colocar 8 damas. Cómo las damas se amenazan vertical, horizontal y diagonalmente, está claro que en todas las soluciones sólo puede haber una dama en cada fila y una dama en cada columna.

Esto nos da un inicio. Para ver mejor las explicaciones voy a dibujar el cuadro:

Empezamos fila a fila. Lógicamente da igual columna a columna pero psicológicamente es como más sencillo ya que normalmente trabajamos así (leyendo fila a fila).

Empezamos por la fila de arriba (la A y vamos hacia la H). Sólo puede haber una dama en cada fila.

Colocamos la primera en la primera columna. Por lo tanto está en A1.

Ahora tenemos que anular las casillas amenazadas por esa dama. O sea, anulamos toda la columna 1, toda la fila A, y la diagonal B2, C3, D4, etc.

Vamos a la fila 2 y ponemos la siguiente dama en la primera columna donde podamos: B3.

Igual que antes hay que anular las casillas amenazadas y etc. etc. hasta llegar a colocar las 8 damas.

De esta forma encontramos una solución.

Ahora hay que pensar la forma de proseguir. O sea, una vez encontrada una solución ¿cómo seguimos buscando?

¿Parece un programa recursivo?

Saludos.

No hay comentarios: