Serie ficheros virtuales



VBA. Ficheros virtuales




VBA Ficheros virtuales. Sudokus en Excell


  1 Introducción

  2 Cuadrados latinos y mágicos

  3 Algoritmo para construir cuadrados mágicos

  4 Sudokus

 5 Algoritmo para construir sudokus

  6 Ejemplo de paso de los sudokus triviales a los usuales

  7 Implementación

  8 Código agregado para presentación lúdica

 

                                                                                                                  _______


1 Introducción



En el blog hermano C Ficheros virtuales se introdujo un programa para generar cuadrados mágicos y sodokus. Este programa se encapsuló como una DLL a la que se le dotó de interfaces COM y Net. Ahora se desarrolla el mismo programa en VBA para Excell.

 

Aquí, los servicios centrales de generación de sudokus y cuadrados mágicos se implementan como complemento excell y la presentación visual se deja a una hoja como la siguiente

 



Se ha implementado la opción de autorrelleno automático, que se activa al pulsar el botón AUTO y hace evolucionar la presentación como sigue



que va rellenando las celdas hasta llegar a completarlas como en el ejemplo

 


El fuente base de la hoja y del complemento se puede encontrar en el libro Magic. Los archivos relacionados son

- El libro Excell "Magic.xls" propiamente dicho que contiene la hoja Sudoku de presentación

- El complemento Excell "Sudoku.xla" que contiene la algorítmica para sudokus y cuadrados mágicos

- El complemento Excell "W.xla" soporte de los ficheros virtuales

 

 

Los fuentes completos del desarrollo se presentan en el enlace VBA. Fuentes, mientras que en Instalación de Componentes, se muestran los pasos a seguir en la instalación de complementos Excell.


                                                                                                                 _______


 

En los siguientes epígrafes de este capítulo presentaremos:

 

 La definición de cuadrados latinos y mágicos con ejemplos y métodos para construirlos.

 

 A continuación contemplaremos los sudokus presentando ejemplos e introduciendo métodos para construirlos partiendo de un cuadrado latino.

 

 Luego acometeremos su implementación, así se definirá una base de datos virtual que servirá de soporte del código para generar cuadrados latinos, al que le agregaremos la codificación de replicación que genera sudokus triviales y el código de transformación para obtener los sudokus no triviales.

 

 

El capítulo sirve para introducir el principio básico de la implementación del resto de ejemplos, conforme al siguiente esquema genérico:

   

Diseño de base de datos, algorítmica, codificación núcleo sintetizada en los servicios de un complemento Excell, y codificación de las hojas de presentación.

 

 

                                                                                                                 _______

 

 

2 Cuadrados latinos y mágicos

 

 Un cuadrado latino es una matriz  N * N, en la cual los enteros  1, 2, .. N^2 aparecen todos exactamente una vez.

 

 Un cuadrado mágico es un cuadrado latino con N impar en el que todas las filas, columnas y diagonales principales suman lo mismo.

 

 

Veamos un ejemplo

 



 

Y un ejemplo extremo

 

 

 

 

 

Si se prescinde de la propiedad de la igualdad de suma para las diagonales tendríamos ejemplos de cuadrados latinos como los siguientes

 

 

 

 

o en el ejemplo extremo    

  

 

                                                                                                                 _______


  

3 Algoritmo para construir cuadrados mágicos

 

 

Un algoritmo para construir un cuadrado mágico es el siguiente

 

  Se coloca 1 en el medio de la fila superior

 

 

  Después de colocar el entero K (K=1,2,...,N*N), hay que moverse una fila hacia arriba y una columna hacia la derecha para colocar el siguiente entero K+1

 

 

 Esta regla general tiene las siguientes excepciones de desbordamiento:

 

  Si un movimiento lleva por encima de la primera fila, hay que colocar K+1 abajo del todo de la columna destino

 

  Si un movimiento se sale por la derecha, hay que colocar K+1 en esa fila por la izquierda

 

 

Por último, si un movimiento lleva a una celda ya ocupada o si el movimiento se sale por arriba y por la derecha, K+1 se coloca justo debajo de donde estuviera K

 

 

                                                                                                                 _______

 

Sudokus

 

 La resolución del algoritmo de cuadrados mágicos por series parecería natural, moviéndonos por los índices (i,j).

 

 El problema se complica cuando se desea una solución general para N genérico y aún más cuando partiendo del cuadrado mágico origen o de un cuadrado latino en general le aplicamos reglas de transformación para conseguir un Sudoku.

 

Pues si replicamos manteniendo la seriación unívoca en 1...N y la suma constante por filas y columnas, mediante el procedimiento que se explica en el epígrafe siguiente, lograremos un sudoku similar a los que se muestran a continuación.

 

De tamaño 9:

 

 

 

y de tamaño 25:

 

 

 

Con la aplicación de ficheros virtuales la resolución del problema del cuadrado mágico origen es tan sencilla como con series de un tamaño dado, pero permite su extensión a problemas ampliados como el del sudoku de una forma natural.

 

 

                                                                                                                 _______

 

 

5 Algoritmo para generar sudokus

 

El procedimiento se resume en  los siguientes pasos:

 

                                                                                 __

1) Construir un cuadrado latino de tamaño n = \/ N, esto es una matriz  n * n, en la cual los enteros 1, 2 … n * n aparecen todos exactamente una vez.

 

 

 

2) Expandirlo a un sudoku trivial, desplegando filas y columnas y evitando repeticiones.

 

 

    Para ello se sigue el esquema:

 

    La expansión de arriba abajo despliega las columnas empezando por ejemplo por la nº 2 y colocándola debajo de la nº 1, la 3 debajo de la 2, la N bajo la N-1 y por último la 1 bajo la N.

     

    La expansión de izquierda a derecha sigue un mecanismo similar pero para las filas, así, se toma  la 1ª y se coloca a continuación de la 2ª, etc.

 

    Más adelante se presenta un ejemplo numérico detallado de la aplicación de este esquema

 

 

3) Transformar el sudoku aplicando intercambios de parejas de cifras encolumnadas, comenzando un ciclo de intercambios entre las columnas y filas que mantengan bien la suma en filas, o bien la de columnas, y que acabe al reencontrar la posición de partida, consiguiéndose un sudoku equivalente pero con cifras distintas de las de comienzo.

 

 

Veámoslo con un ejemplo numérico de transformación de filas:

 

 

Punto de partida:             2  7  9    8  4  5    1  3  6        Suma  45

                              4  5  8    3  6  1    7  9  2              45

 

 

Ciclo de progreso mediante permutaciones que mantienen la suma por columna, buscando una combinación con las mismas sumas por filas de partida, expulsando en cada paso la repetición que se crea hasta que deja de producirse:

 

 

                                                                          4  7  9    8  4  5    1  3  6        Suma  47

                              2  5  8    3  6  1    7  9  2              43

 

                              4  7  9    8  6  5    1  3  6        Suma  49

                              2  5  8    3  4  1    7  9  2              41

 

                              4  7  9    8  6  5    1  3  6        Suma  49

                              2  5  8    3  4  1    7  9  2              41

 

Punto final:

                              4  7  9    8  6  5    1  3  2        Suma  45

                              2  5  8    3  4  1    7  9  6              45

 

 

Por tanto hemos pasado de:

 

                              2  7  9    8  4  5    1  3  6        Suma  45

                              4  5  8    3  6  1    7  9  2              45

                          a:

                              4  7  9    8  6  5    1  3  2        Suma  45 

                              2  5  8    3  4  1    7  9  6              45

 

 

proceso con el que vamos rompiendo poco a poco la fácil predicción de las cifras de partida.

 

 

El ciclo de búsqueda es cerrado debido a las restricciones de unicidad en filas y columnas, lo que garantiza que si se parte de una cifra, se acabará alcanzando en la otra fila la misma cifra en una columna distinta.

 

 

4) Revisar el sudoku obtenido y rechazar alternativamente los que presenten parejas repetidas en filas o columnas posteriores, pues de conocerse a priori que no se eluden son de fácil predicción.  

 

     Se deja un porcentaje de escape libre principalmente para prevenir entrada en bucle o degradación del tiempo de respuesta.

    Concretamente, en la implementación utilizada se ha utilizado el 10%; pero debe entenderse como resultado medio, pues se aplica utilizando un generador de números al azar.

 

    Además, al dejar este porcentaje de alternancia bajo dependencia aleatoria, también aumenta la variabilidad de la respuesta.

 

 

   Se rechazarían normalmente entonces resultados parciales como los siguientes:

 

   6  5  1    2  3  8

2  3  7    4  5  9   . . .

9  4  8    7  1  6

 

   ó

 

  6  5  1

2  3  7     

  9   4  8  

 

1  3  4

6  7

  5   2  9 

 

  . . .

  

                                                                                                                  _______



 

 

6 Ejemplo de paso de los sudokus triviales a los usuales

 

 

Se toma un cuadrado latino base con n = 3 = raíz(9)

 

        4  9  2

  8   1  6

        3   5  7

 

Se replica como primera fila una cualquiera de las filas distinta de la primera

 

        4  9  2      3  5  7

  8   1  6     

        3   5  7

 

Se toma como segunda fila una de las otras dos restantes

 

        4  9  2      3  5  7

        8  1  6      4  9  2

        3   5  7

 

Termina la replicación del segundo cuadrado añadiendo la fila final que queda

 

        4  9  2      3  5  7

        8  1  6      4  9  2

3  5  7      8  1  6

 

Para el tercer cuadrado se toman las filas alternas que completan la replicación

 

        4  9  2      3  5  7     8  1  6

        8  1  6      4  9  2     3  5  7

3  5  7      8  1  6     4  9  2

  

 

 La replicación puede continuar de la misma forma por columnas hasta completar el desarrollo, como se muestra en la imagen

 

 

 

 

Se trata por construcción de un sudoku pero su adivinación es inmediata.

 

 

Variantes simples de este mismo procedimiento consisten en girar las cifras al replicar como se ha hecho en las columnas del ejemplo y que detallamos ahora

 

 

1er.Cuadrado izquierdo superior origen

 

        4  9  2        4  9  2        4  9  2        4  9  2          

8  1  6        8  1  6        8  1  6        8  1  6         

3  5  7        3  5  7        3  5  7        3  5  7         

                

                  ->             ->             ->             

 

2do.Cuadrado izquierdo superior que se va construyendo

 

                       7              7  3           7  3  5

        2              2              2  4           2  4  9         

6              6              6  8           6  8  1         

 

Resultando entonces de esta nueva forma de replicar los dos cuadrados superiores izquierdos siguientes:

 

       4  9  2

       8   1  6

       6   5  7

 

                |

                    

 7   3  5

       2   4  9

       6   8  1

     

 

Con esta técnica, se sigue obteniendo un sudoku algo menos trivial pero sigue siendo muy fácil de adivinar.

 

 

Para evolucionar a un sudoku usual hay que aplicar transformaciones de intercambio de ítems particulares que mantengan las condiciones globales que se han indicado antes.

 

Entonces, en el programa se implementará el desarrollo de un cuadrado latino para lograr un sudoku trivial de partida utilizando los métodos que se acaban de comentar y a continuación se le aplicará una transformación de intercambio de parejas, aceptándose el resultado si el sudoku resultante no es del tipo fácil que se ha mostrado, repitiéndose las transformaciones de intercambio de parejas mientras sea necesario.



 

El siguiente tamaño adecuado para un sudoku completo sería n = 5, de presentación n^2 = 25, como en la imagen que sigue en donde ya se ha aplicado la transformación.

 

 

 

Si la pantalla no permite alcanzar el siguiente tamaño de base 7, que se expandiría a 49 columnas, se pueden construir seudo sudokus como el que se muestra a continuación

 

en donde se conjugan 3 cuadrados seudomágicos en vez de los 7 necesarios por falta de espacio en pantalla

 

                                                                                                                  _______

 

7 Implementación


La rutina de generación principal condensa el código en un par de procedimientos:

 La construcción del tapiz de números y el refinado de visualización.


La construcción del tapiz sigue las reglas expuestas anteriormente y las repasaremos ahora en el código principal.

El refinado para dejar entrever sin mostrar es ya más bien una cuestión artística y consiste en aplicar apagados de visualización que dejen suficientes ítems vistos como para deducir pero no tantos como para mostrar el conjunto. Para ello se seguirán las siguientes reglas:
 
 No permitir filas ni columnas nulas
 No permitir sucesiones incompletas 1...N
 Procurar subcubos no nulos pero poco densos
 Tender a que el conjunto tenga un 25% de ítems vistos

Y todo ello bajo un control aleatorio.



Al final resulta un código incluso más grande que el dedicado a la construcción del tapiz y que puede encontrarse en el libro Magic.



Volviendo al código de construcción del tapiz de números, comencemos por la rutina de generación principal 

'//-----------------------------------------------------------------------------
'// Rutina de generación principal
'//-----------------------------------------------------------------------------
Sub S_Gen(Sudoku As Integer, N As Long)

 Dim Er As Integer ' Control de errores intermedios


 ' Construye un nuevo cuadrado o sudoku del tamaño solicitado

 If Sudoku > 0 Then
    Er = PrGeneraSudoku(N)
 Else
    Er = PrGeneraMagic(N)
 End If


 ' Refina visualización
 
 Er = PrRefinoActivas(N)


End Sub


 

El código maestro de la construcción del tapiz de datos se centra en la rutina PrGeneraSudoku que sigue a continuación

 

'//-----------------------------------------------------------------------------
'// Rutina de generación de sudokus
'//-----------------------------------------------------------------------------
Private Function PrGeneraSudoku(N As Long) As Integer

 Dim Er As Integer     ' Control de errores intermedios
 Dim iFacil As Integer ' 0/1 El sudoku generado es de tipo fácil, con parejas repetidas obvias
 Dim lResul As Long    ' Control de resultados intermedios
 Dim nn As Long        ' sqr(N), total de supercubos, dimensión local

 
 ' Inz
 
 PrGeneraSudoku = 1
 
 nn = S_Raiz(N)

 iFacil = 1
 


 ' Ciclo de proceso
 
 Do While iFacil = 1

 
  ' Generación del cuadrado latino subcubo base
 
  Er = PrGenSudoku(nn)
  If Er > 0 Then Exit Function


  ' Rutina de expansión del núcleo Sudoku, con intercambio de filas-columnas y refinado

  Er = PrSudoku(nn)                 ' Expansión del núcleo
  If Er > 0 Then Exit Function

  Er = PrSwap(N, 1)                 ' Intercambio base de filas-columnas como pretratamiento a la pérdida de trivialidad
  If Er > 0 Then Exit Function

  Er = PrSudokuRefino(N, iFacil)    ' Refinado por permutaciones
  If Er > 0 Then Exit Function


  ' Una de cada 10 veces en media no discrimina resultado fácil

  lResul = R_LRnd(100)
  If (lResul <= 10) Then Exit Do
 
 ' Reintenta hasta conseguir uno + difícil

 Loop

 
 ' Fin de proceso satisfactorio

 PrGeneraSudoku = NO_ERRO

End Function

 

                                                                                                                  _______



8 Código agregado para presentación lúdica

El módulo de juego se centra en un nuevo botón que invoca a un formulario en donde poder probar fortuna.  En caso de acierto se activa la visión del elemento. El aspecto visual es

 

El código asociado a la gestión del formulario emergente es más sencillo que el algorítmico o el de semiocultación del tapiz y también se encuentra en la hoja excell Magic citada.

                                                                                                                  _______

 

Puede compararse la presentación en VBA con la presentación en otros lenguajes que se muestra en la página base de la serie; por ejemplo con el desarrollo paralelo en javascript, que se materializa en la página sudoku.ficherosvirtuales.com

                                                                                                                  _______