martes, febrero 23, 2010

Programita de las 8 reinas con programación estructurada


El problema de las ocho reinas lo presenté a finales de 2008 aunque entonces lo llamé de las ocho damas.

Es un problema que vamos a utilizar para comparar una programación estructurada con la programación funcional.

Importante: Como lenguaje de programación estructurada he elegido visual basic.net por claridad. Podría haber cogido cualquier otro, y también, aún en visual basic podría haber elegido la programación orientada a objetos.

Para la programación funcional elijo el típico lisp. Pero cuidado, puedes utilizar lisp como si fuera un lenguaje de programación estrucuturada, y eso sería un error porque no veríamos diferencias entre uno y otro.

Os recuerdo la historia de este problema: Es un problema que planteó un ajedrecista al gran Gauss. Éste encontró 76 soluciones por lo que no llegó a las 92 soluciones que encuentra el programa.

Se trata de encontrar las 92 formas diferentes de colocar 8 reinas en un tablero de ajedrez sin que se amenacen entre ellas.

SOLUCIÓN

Lo vamos a hacer a lo bruto. A base de estructuras "FOR" encadenadas recorremos todas las posibilidades.

La variable A representa la columna 1, la B la columna 2, y así hasta la 8.
Si A=1 significa que la reina está en la primera fila de la columna 1.
Si A=2, la reina está en la segunda fila de la columna 1.

Lo primero es evitar que las diferentes columnas puedan tener los mismos valores. Esto es, A tiene que ser diferente de B, y de C, etc. Así evitamos que las reinas estén en la misma fila.

Cada letra (o sea cada columna) sólo tiene un valor. Así se asegura que en cada columna sólo hay una reina.

Por último tenemos que saber si en la combinación que obtenemos tenemos alguna amenaza de reinas en diagonal. Esta es la parte más difícil del algoritmo.

Hay que mirar un tablero y ver qué se cumple cuando dos reinas están en diagonal, y qué se incumple cuando no están.

Pues resulta que aquellas reinas que se amenazan en diagonal están a la misma distancia en horizontal que en vertical. Si esto no se cumple no se amenazan.

Llevado al algoritmo sería algo así como:

Por cada reina que tenemos colocada, comparamos con el resto de reinas y vemos si la distancia entre las columnas es igual que la distancia entre las filas. Cuidado, la distancia se mide en valor absoluto.
Así queda el programita en vb.net:






RESULTADO:


Y el código fuente para un cómodo copy-paste:

Module Module1
Sub Main()
Dim a, b, c, d, e, f, g, h, i As Integer
Dim resultado(8) As Integer
Dim numResultados, columna As Integer
numResultados = 0
For a = 1 To 8
For b = 1 To 8
If a <> b Then
For c = 1 To 8
If c <> a And c <> b Then
For d = 1 To 8
If d <> a And d <> b And d <> c Then
For e = 1 To 8
If e <> a And e <> b And e <> c And e <> d Then
For f = 1 To 8
If f <> a And f <> b And f <> c And f <> d And f <> e Then
For g = 1 To 8
If g <> a And g <> b And g <> c And g <> d And g <> e And g <> f Then
For h = 1 To 8
If h <> a And h <> b And h <> c And h <> d And h <> e And h <> f And h <> g Then
resultado(1) = a
resultado(2) = b
resultado(3) = c
resultado(4) = d
resultado(5) = e
resultado(6) = f
resultado(7) = g
resultado(8) = h
If Not coincide_diagonal(resultado) Then
numResultados = numResultados + 1
imprimir(resultado)
Console.Write(" ")
End If
End If
Next
End If
Next
End If
Next
End If
Next
End If
Next
End If
Next
End If
Next
Next
Console.WriteLine()
Console.Write("Número total de soluciones :" & numResultados.ToString)
Console.ReadKey()
End Sub

Function coincide_diagonal(ByVal propuesta() As Integer) As Boolean
Dim i, j As Integer
coincide_diagonal = False
For i = 1 To 7
For j = i + 1 To 8
If Math.Abs(i - j) = Math.Abs(propuesta(i) - propuesta(j)) Then
coincide_diagonal = True
End If
Next
Next
End Function
Sub imprimir(ByVal res() As Integer)
Dim i As Integer
For i = 1 To 8
Console.Write(res(i))
Next
End Sub
End Module

2 comentarios:

Anónimo dijo...

valioso el aporte ahora que estoy viendo analisis de algoritmos y este es el problema final de curso, gracias no habia entendido como solucinarlo y ahora tengo una base para pensar mi propia respuesta

Aitor Iriarte dijo...

Hola, ¿que tal?
Ya que hablamos de un curso ten en cuenta dos cosas:

1.-No sé si yo al final hice la programación de la variante recursiva. Echa un vistazo con Google porque lo más probable es que sea una solución más elegante que esta.

2.-Hay una complicación extra del problema que consiste en encontrar las 12 soluciones originales. Aquí expuse el problema. La solución del Argentino Eduardo Perez en este otro post.

Saludos y "viva la programación".