<< Llenando el tablero en otros ordenes>>

Lecciones anteriores:

Memorizando Respuestas (Algunas mejoras importantes al programa original)

El problema original:

En la primera lección de esta serie analizamos el siguiente problema:

Se tiene un tablero de 4x4 en el que se anota un dígito en cada casilla. En cada fila y en cada columna se forma un número de cuatro dígitos. Un tablero de este tipo es legal si los ocho números que se forman así son múltiplos de 17. ¿Cuántos tableros legales distintos hay?

Probamos diferentes formas de hacer un programa que lo resuelva, para poder comparar algunos métodos, pero todos los programas tardaban más de 5 horas en una Pentium ~100 Mhz. En la segunda lección vimos algunas mejoras que llevaban el tiempo a media hora. Ahora vamos a tratar de mejorar esto cambiando la forma en que elegimos los números.

Llenando el tablero

Para poder hablar cómodamente de los casilleros vamos nombrarlos como en la batalla naval, o sea a las columnas les asignamos letras y a las filas números. La misma notación se usa en las variables del programa

En las lecciones anteriores no se van eligiendo las cifras una por una, sino que se eligen las primeras tres de cada fila al mismo tiempo, pero si uno lo piensa un poco es como si se fueran llenando en cada fila de izquierda a derecha, en general la primera esta fija pero la tercera varia muy rápidamente. Dibujándolo queda el siguiente orden de llenado.

Lo que tiene de malo es que al llenar el noveno casillero(A3), puede ser que no haya ninguna forma de llenar A4 de manera que la columna A tenga un múltiplo de 17. Pero eso recién lo vamos a ver en el 13avo paso de llenado después de probar todos los llenados posibles de B3, C3 y D3 que son completamente inútiles si no es posible llenar A4. Esto hace perder tiempo y se repite con las otras columnas. Así que sería mejor si cada vez que tenemos tres números de una fila buscamos completarla inmediatamente. Esto da el siguiente orden de llenado:

De todas maneras se puede ganar un poco de tiempo intercalando el llenado de una horizontal y una vertical. La diferencia es poca y no me queda muy claro el motivo (quizás tenga que ver con que al estar fijada ya la primera columna se tiene que llenar un cuadradito de 3x3 que es mas chico y así es necesario repetir los cálculos para D4 menos veces(?)). Esto corresponde al siguiente orden que es el que se usa en el programa.

El programa:

Aprovecha la idea de la lección pasada y guarda los resultados de CompletarNumero en una matriz. Sin embargo como llenamos las cifras en el tablero una por una no necesitamos la función Cifras.

Declare Sub IniciarMatrices ()

Declare Function CompletarNumero% (N1 As Integer, N2 As Integer, N3 As Integer) 'As Integer

Const C9999D17 = 9999 \ 17

Dim Shared MatCompletarNumero(0 To 9, 0 To 9, 0 To 9) As Integer





Dim A1 As Integer, A2 As Integer, A3 As Integer, A4 As Integer

Dim B1 As Integer, B2 As Integer, B3 As Integer, B4 As Integer

Dim C1 As Integer, C2 As Integer, C3 As Integer, C4 As Integer

Dim D1 As Integer, D2 As Integer, D3 As Integer, D4 As Integer



Dim Contador As Long



Dim Inicio As Single

Dim Tiempo As Single

Dim Pasos As Single



Inicio = Timer

IniciarMatrices

Print

Print "Tiempo", "Tiempo", "Tableros", "Valor"

Print "Trans.(s)", "Estimado(H)", "Encontrados", "L1"

For A1 = 0 To 9

  For B1 = 0 To 9

    For C1 = 0 To 9

      D1 = MatCompletarNumero(A1, B1, C1)

      If D1 >= 0 Then



        Tiempo = Timer - Inicio

        Pasos = A1 * 1000 + B1 * 100 + C1 * 10 + D1 + 0.1 ' "+.1" porque sino empieza de Cero

        Print Tiempo, Tiempo / Pasos * 10000 / 3600, Contador, Pasos - 0.1



        For A2 = 0 To 9

          For A3 = 0 To 9

            A4 = MatCompletarNumero(A1, A2, A3)

            If A4 >= 0 Then



              For B2 = 0 To 9

                For C2 = 0 To 9

                  D2 = MatCompletarNumero(A2, B2, C2)

                  If D2 >= 0 Then



                    For B3 = 0 To 9

                      B4 = MatCompletarNumero(B1, B2, B3)

                      If B4 >= 0 Then



                        For C3 = 0 To 9

                          D3 = MatCompletarNumero(A3, B3, C3)

                          If D3 >= 0 Then

                            C4 = MatCompletarNumero(C1, C2, C3)

                            If C4 >= 0 Then

                              D4 = MatCompletarNumero(D1, D2, D3)

                              If D4 >= 0 Then



                                If D4 = MatCompletarNumero(A4, B4, C4) Then

                                  Contador = Contador + 1

                                End If 'D4=D4'



                              End If 'D4

                            End If 'C4

                          End If 'D3

                        Next C3

                          

                      End If 'B4

                    Next B3



                  End If 'D2

                Next C2

              Next B2



              

            End If 'A4

          Next A3

        Next A2



      End If 'D1

    Next C1

  Next B1

Next A1



Tiempo = Timer - Inicio

Pasos = L1 + 0.1 ' "+.1" porque sino empieza de Cero

Print Tiempo, Tiempo / 3600, Contador, "Fin"



Function CompletarNumero%(N1 As Integer, N2 As Integer, N3 As Integer) 'AS Integer

  Dim Valor As Integer

  Dim Sobra As Integer

  Dim Falta As Integer

  Valor = N1 * 1000 + N2 * 100 + N3 * 10

  Sobra = Valor Mod 17

  If Sobra <> 0 Then

    Falta = 17 - Sobra

    If Falta >= 10 Then

      Falta = -1 'ERROR

    End If

  Else

    Falta = 0

  End If

  CompletarNumero = Falta

  'Return Falta

End Function



Sub IniciarMatrices()

  Dim X1 As Integer

  Dim X2 As Integer

  Dim X3 As Integer

  Dim X4 As Integer



  For X1 = 0 To 9

    For X2 = 0 To 9

      For X3 = 0 To 9

        MatCompletarNumero(X1, X2, X3) = CompletarNumero(X1, X2, X3)

      Next X3

    Next X2

  Next X1



End Sub

La parte principal del programa tiene demasiados For e If anidados, por eso cada vez que cerramos uno dejamos indicado a cual corresponde para facilitar la búsqueda y corrección de errores.

(Quizás habría que cambiar A1, A2, ... ,D4 por una matriz de 4x4. Creo que sería un poquito más lento el programa. si alguno lo prueba nos puede mandar sus resultados.)

Comparando los tiempos:

Al correr los programas con cada orden de llenado obtenemos los valores de la siguiente tabla.

En las dos últimas filas comparamos los distintos ordenes de llenado cuando no utilizamos la idea de la lección pasada, o sea que cada vez que necesitamos el valor de CompletarNumero llamamos a la función para que lo calcule. En estos ejemplo se ve que el método que usamos en esta lección es independiente del método de la anterior, y puede haber casos en que se pueda usar uno pero no el otro. Sin embargo los mejores resultados se obtienen (obviamente) aprovechando ambos.

Hay algunos otros órdenes de llenado posibles, pero no creo que mejoren mucho el tiempo de ejecución. Si alguno tiene ganas de probar un poco nos interesaría conocer sus resultados. Acuérdense de incluir en sus pruebas el tercer orden propuesto para poder eliminar (o tratar de eliminar) las diferencias entre una computadora y otra.

Ejercicios:

1. Probar otros ordenes de llenado y tratar de entender por que funcionan mejor o peor.
   
2. Pasar las variables A1, ... , D4 a una matriz de 4x4 y comparar el tiempo de ejecución.
   
3. Escribir un programa que calcule de cuántas formas se puede llenar un tablero de nxn con los números desde 1 hasta n² sin repetir de manera que todas las filas y columnas sumen lo mismo. ¿En cuántos de ellos las dos diagonales principales (las dos más largas) también suman lo mismo que las filas y columnas? ¿Hasta que valor de n se puede ejecutar el programa en un tiempo razonable?
   

Lecciones siguientes:

ninguna por ahora

La idea es que hagan los ejercicios y piensen que otras cosas interesantes se pueden hacer relacionadas con estos temas. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es cym98@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Les pedimos que se tomen unos instantes y contesten estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

OmaNet   Curso CyM98	OmaNet - Educación Interactiva    www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes: webmaster@oma.org.ar