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