Serie ficheros virtuales

 



C Ficheros virtuales

 

 

A.II  Ejemplos

 

A.II.1 Cuadrados mágicos y Sudokus

  A.II.1.0 Introducción

  A.II.1.1 Cuadrados latinos y mágicos

  A.II.1.2 Algoritmo para construir cuadrados mágicos

  A.II.1.3 Sudokus

  A.II.1.4 La estructura de soporte

  A.II.1.5 La implementación núcleo de los cuadrados latinos y mágicos

  A.II.1.6 La implementación específica de los cuadrados mágicos

  A.II.1.7 Resumen del procedimiento sudoku

  A.II.1.8 Ejemplo de paso de los sudokus triviales a los usuales

  A.II.1.9 Implementación

  A.II.1.10 Código agregado para presentación lúdica

 

Ver también

(B.II.3 La clase CMagic para cuadrados mágicos y sudokus)

(VBA Ficheros virtuales para Excell. Sudokus)

                                                                                                          ________

A.II.1.0 Introducción

 Este capítulo se dedicará a desarrollar un programa de generación de cuadrados latinos, cuadrados mágicos y sudokus.

 Concretamente, 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 y 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.

La implementación que se presenta en este capítulo se desarrollará para un programa de pantalla MsVisual C++.

 

En la segunda zona del libro, se sintetizará la programación en una DLL que servirá para la pantalla y para el modelo COM y NET, y se desarrollarán interfaces en Visual Basic Net. Aquí se presentará una codificación extractada que se retomará posteriormente bajo el enfoque de esta evolución.

 

Puede consultarse el resultado en el enlace B.II.3 La clase CMagic para cuadrados mágicos y sudokus.

También puede acudirse al blog hermano VBA Ficheros virtuales para excell. Sudokus, para ver una implementación nativa en VBA para excell.

 

 

 

 

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 una DLL, y codificación de los interfaces de presentación.

 

 

En los dos primeros ejemplos la síntesis de la codificación núcleo a una DLL se hará paso a paso, en los siguientes se introducirán las DLL’s núcleo directamente.

 

 

                                                                                                          ________

 

A.II.1.1 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    

 


  
                                                                                                         
________

 A.II.1.2 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

 

                                                                                                          ________

 

A.II.1.3 Sudokus

Un sudoku es una matriz  N * N, con N = n * n y n impar, en la cual los enteros  1, 2, .. N aparecen todos exactamente una vez en cada fila y en cada columna y en cada subcubo n * n.

 

Veamos un ejemplo de tamaño N = 9 = 3*3:



 


 

 

  Y uno de 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 problema ampliados como el del sudoku de una forma natural.

                                                                                                          ________

A.II.1.4 La estructura de soporte

La definición de la estructura de soporte del fichero virtual puntal del desarrollo es muy sencilla

 

Consiste de una parte de clave [en índices de filas y columnas (i,j)] y una parte de datos asociados, que guarda el valor del nodo:

 

 

 

   // Estructura de claves del fichero de soporte del cuadrado mágico

   struct sDsK   // Estructura de claves de acceso a nodos (i,j)

   {

    long li;     // Índice i del nodo

    long lj;     // Índice j del nodo

   };    

 

 

  

 // Estructura de datos del fichero de soporte del cuadrado

   struct sDsD   // Estructura de datos asociados

   {

    long lk;     // Valor de k del nodo

    char ck[4];  // k en formato alfanumérico para presentación

   }; 

 

 

 

 

 

 

 

 

 

  // Estructura conjunta del fichero de soporte del cuadrado

   static struct sDsKD

   {

    struct sDsK DK; // Clave

    struct sDsD DD; // Datos

   } DSc;           // Work paso de datos PrChain

 

  Con la que se crea el fichero virtual “PMAGIC” al iniciar la aplicación ejecutando SRRCW_NEW:

     . . .

   lNID = SRRCW_NEW("PMAGIC", sizeof(sDsK), sizeof(sDsKD));

   . . .

  y al que se irán incorporando los distintos valores de cada posición (i,j).

                                                                                                           ________

 

A.II.1.5 La implementación núcleo de los cuadrados latinos y mágicos

 

En este capítulo nos centraremos en la codificación núcleo de la pantalla que genera cuadrados mágicos, cuadrados latinos y sudokus. Estas rutinas principales se convertirán en servicios de una DLL que se aplicará a la pantalla origen y los modelos COM y NET.

 

 Las rutinas auxiliares se transcribirán sin apenas cambios como rutinas internas de la DLL. Al retomar en la segunda zona del libro la DLL se presentarán las rutinas internas y externas y su interrelación.

 

Este detalle se elude ahora, presentándose tan solo los aspectos centrales de la codificación empleada para dar respuesta a la algorítmica introducida en los epígrafes anteriores.

 

En esta línea, veamos ahora el código principal utilizado para generar los ejemplos de cuadrado mágico que se han mostrado:

 

   . . .

 

   // Genera un tamaño de cuadrado mágico aleatorio, de tamaño impar 

   m_N = 1 + 2 * (PrRand(NMAX) / 2);   [Nota: PrRand se verá en B.I

 

   // Construye un nuevo cuadrado mágico de ese tamaño 

   er = PrGen(m_N); 

  

   // Bucle de permutaciones de filas y columnas opcional  

   // (Pasando de cuadrado mágico a cuadrado latino) 

   if (m_Reorden == "S" || m_Reorden == "s")  

                                 

    for (i=1;i<=m_N;++i) er = PrSWAP(m_N); 

 

   . . . 

 

                                                                                                          ________

 

A.II.1.6 La implementación específica de los cuadrados mágicos 

 

El código de la propia generación del cuadrado mágico, transposición del algoritmo citado previamente, sería

 

   //-------------------------------------------------------------------- 

   // Rutina auxiliar de generación de muestras de cuadrados mágicos 

   //-------------------------------------------------------------------- 

   short int PrGen(long N) 

  

    long i = 0; // Índice i en curso 

    long i1= 0; // Índice i+1 en curso 

    long j = 0; // Índice j en curso 

    long j1= 0; // Índice j+1 en curso 

    long k = 0; // Índice 1..N*N    

    short int er = 0; // Control de errores 

    long lresul = 0;  // Resultados SRRCW 

  

    // Inicia un nuevo fichero virtual de soporte  

    er = SRRCW_CLRF("PMAGIC"); 

 

    // 1er.ítem Fila 1, columna N/2 + 1 

    i = 1; 

    j = N/2 + 1; 

    lresul = PrWrite(i, j, 1); 

 

    // Filtro de proceso no trivial 

    if (N <= 1) return NO_ERRO; 

 

    // Ciclo de proceso 

    for (k=2;k<=N*N;++k) 

   

   

     // Movimiento  

     er = PrIJ(N, i, j, &i1, &j1); 

     // Si un movimiento lleva a una celda ocupada, se pondrá k+1 en    

     // (i+1, j) 

     lresul = PrSeteq(i1, j1); 

     if (lresul)  

    

      i1 = i+1; 

      j1 = j; 

    

     // Graba movimiento en curso 

     lresul = PrWrite(i1, j1, k); 

     // Actualiza contadores 

     i = i1; 

     j = j1; 

   

    return NO_ERRO

  

 

Que se complementa con las siguientes rutinas auxiliares 

 

   //-------------------------------------------------------------------- 

   // Rutina auxiliar de generación de un movimiento de colocación de 1 

   // ítem de cuadrado mágico de posición origen (i,j) --> a posición  

   // destino según algoritmo de cuadrado mágico, que se devuelve como (i1, j1) 

   //-------------------------------------------------------------------- 

   short int PrIJ(long N, long i, long j, long *i1, long *j1) 

   {   

    // Si parte del extremo más superior, se coloca en su celda inferior 

    if ( (i == 1) && (j == N) ) 

   

     *i1 = 2; 

     *j1 = N; 

     return NO_ERRO; 

   

 

    // Se mueve una fila hacia arriba 

 

    *i1 = i - 1; 

 

 

    // Si se sale del cuadro se ubica en la posición inferior de la columna 

  

    if (*i1 <= 0) *i1 = N; 

 

 

    // Se mueve una columna a la derecha 

 

    *j1 = j + 1; 

 

 

    // Si se sale del cuadro se coloca en esa fila por la izquierda 

  

    if (*j1 > N) *j1 = 1; 

  

    return NO_ERRO; 

  

 

 

PrSeteq y prWrite son interfaces operativos a las correspondientes funciones de SRRCW: 

 

   //-------------------------------------------------------------------- 

   // Rutina auxiliar de determinación de si una celda está ya ocupada 

   //-------------------------------------------------------------------- 

   long PrSeteq(long i, long j)  

  

    // Clave de acceso  

    DSc.DK.li = i;    

    SRRCAL_lLexi(&DSc.DK.li);  // Conversor de valor a peso. Ver capítulo estructuras  

    DSc.DK.lj = j; 

    SRRCAL_lLexi(&DSc.DK.lj); 

 

    // Evaluación 

    return SRRCW_SETEQ("PMAGIC", &DSc); 

  

 

 

En cuanto a la rutina de reordenación de la matriz, tendríamos

 

   //-------------------------------------------------------------------- 

   // Rutina auxiliar de intercambio de filas y columnas 

   //-------------------------------------------------------------------- 

   short int PrSWAP(long N) 

  

    short int er = 0; // Control de errores 

    long i1 = 0;      // Contador de for. Origen 

    long i2 = 0;      // Contador de for. Destino 

    long j1 = 0;      // Contador de for. Origen 

    long j2 = 0;      // Contador de for. Destino 

  

    // Swap de filas 

    i1 = PrRand(N); // Nº aleatorio 1..

    i2 = 2*i1; 

    if (i2 > N) i2 -= N; 

  

    er = PrSWAPF(N, i1, i2); // Intercambia las filas i1 e i2 

  

    // Swap de columnas 

    j1 = PrRand(N); 

    j2 = 2*j1; 

    if (j2 > N) j2 -= N; 

  

    er = PrSWAPC(N, j1, j2); // Intercambia las columnas j1 y j2 

  

    return NO_ERRO

  

 

 

Para intercambiar filas y columnas se emplean las rutinas PrSWAPC & PrSWAPF, veamos PrSWAPC

 

   //----------------------------------------------------------------------------- 

   // Rutina auxiliar de intercambio de columnas  

   //----------------------------------------------------------------------------- 

   short int PrSWAPC(long N, long j1, long j2) 

  

    long i = 0;      // Contador de for 

    long lresul = 0; // Control de resultados 

  

    // Ciclo de proceso 

    for (i=1;i<=N;++i) lresul = PrSwapIJ(N, i, j1, i, j2); 

  

    return NO_ERRO

  

 

 

Que finalmente llaman a la rutina de intercambio de ítems PrSwapIJ

 

   //----------------------------------------------------------------------------- 

   // Rutina auxiliar para intercambiar un ítem ij-1-  por un ij-2- 

   //----------------------------------------------------------------------------- 

   short int PrSwapIJ(long N, long i1, long j1, long i2, long j2) 

  

    long lresul=0;  // Control resultados SRRCW 

  

    sDsKD DS1, DS2; // DS origen y destino 

 

    // Recupera y elimina importe destino 

    lresul = PrChain(i2, j2); 

    memcpy(&DS2, &DSc, sizeof(DSc)); 

    lresul = PrDelete(i2, j2); 

 

    // Recupera y elimina importe origen 

    lresul = PrChain(i1, j1); 

    memcpy(&DS1, &DSc, sizeof(DSc)); 

    lresul = PrDelete(i1, j1); 

 

    // Graba origen como destino y viceversa 

    lresul = PrWrite(i2, j2, DS1.DD.lk, DS1.DD.a); 

    lresul = PrWrite(i1, j1, DS2.DD.lk, DS2.DD.a); 

 

    return NO_ERRO

  

 

PrChain y prDelete son interfaces operativos a las correspondientes funciones de SRRCW, al igual que PrWrite que se presentó antes. 

 

                                                                                                          ________

 

A.II.1.7 Resumen del procedimiento sudoku

 

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, siguiendo el siguiente esquema, del que más adelante se presenta un

    ejemplo detallado:

 

    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.

 

 

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 partida.

 

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 usa el 1%; pero debe entenderse como resultado medio, pues se aplica como resultado de 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.

    Alternativamente puede codificarse un mecanismo de control por lapso horario, especialmente en lenguajes interpretados (VBS, javascript) que son mucho más lentos.

 

   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

 7

 5    9 

 . . .

 

 

Veamos ahora algunas pantallas y desarrollos ejemplo

                                                                                                          ________

 

A.II.1.8 Ejemplo de paso de los sudokus y seudosudokus triviales a los usuales

Partiendo de la implementación inicial se puede agregar algo más de código al programa base y desarrollar el punto 2 del procedimiento que se acaba de indicar obteniendo un generador de SUDOKUS triviales como en la figura que se muestra, de tamaño base 3 y de presentación 3^2=9:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Conseguido mediante la replicación de cada subfila y cada subcolumna de un cuadrado latino base. En nuestro caso se ha replicado como sigue

 

Se toma el cuadrado latino base

 

        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 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. Se trata por construcción de un sudoku pero su adivinación es inmediata.

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.

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 preciso.

                                                                                                          ________

 

El siguiente tamaño adecuado para un sudoku completo sería 5, de presentación 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




                                                                                                          ________

A.II.1.9 Implementación

 El código a añadir se cimenta en la codificación presentada antes, a la que se  añadirá aproximadamente un tercio más de sentencias, obteniéndose el código principal que sigue, que se presenta extractado:

    void CPmagicDlg::OnButtonok()

   {

    short int er = 0;  // Control de errores

    long i = 0, j = 0; // Contadores de for

    long k = 0;        // Importe recuperado

    long lNMAX = 0;    // NMAX s/parámetros

 

   // Actualiza el contador de muestras

    ++m_Contador;

 

    // Inicializa variables de soporte

    for (i=0;i<=NMAX+1;++i) PrLimp(cLIST[i]);

 

    // Ajusta tamaño máximo general entre el ordinario y el de sudoku (que se multiplica luego por replicación * 3)

    lNMAX = NMAX;

    if (m_Sudoku == "S") lNMAX = 3 * NMAX3;

 

    // Genera un tamaño de cuadrado mágico aleatorio, de tamaño impar

    m_N = 1 + 2 * (PrRand(lNMAX) / 2);

 

    // Para el sudoku lo toma de una tabla con los tamaños 9, 21, 25 y 27

    if (m_Sudoku == "S") m_N = SD[PrRand(NMAX2)-1];

 

    // Construye un nuevo cuadrado mágico de ese tamaño, en su caso, si m_Sudoku = S,

    // servirá de base de partida del sudoku

    if (m_Sudoku == "S")

    if   (m_N == 25) er = PrGen(m_N/5); // Sudoku completo de orden 5

    else             er = PrGen(m_N/3); // Sudokus & seudosudokus

    else  er = PrGen(m_N);              // Cuadrados mágicos

 

    // Bucle de permutaciones de filas y columnas opcional

    if (m_Reorden == "S")

    {

     if (m_Sudoku == "S")

      if (m_N == 25) for (i=1;i<=m_N;++i) er = PrSWAP(m_N/5, 0);

      else           for (i=1;i<=m_N;++i) er = PrSWAP(m_N/3, 0);

      else           for (i=1;i<=m_N;++i) er = PrSWAP(m_N, 0);

     }

 

    // Rutina de ajuste Sudoku (Ver código más adelante)

    if (m_Sudoku == "S") er = PrGeneraSudoku(m_N);

 

    // Restaura los datos de pantalla

    m_LISTH0.ResetContent();

    . . .

    m_LISTH32.ResetContent();

 

    // Vuelca datos a pantalla

    for (i=1;i<=m_N;++i)

    {

     // Nºlínea

     er = PrPasNsecLISTH(i, cLIST[0]);

 

     // Importe de cada columna

     for (j=1;j<=lNMAX;++j) k += PrPasImpoLISTH(i, j, cLIST[j]);

 

     // Importe de suma de la fila

     er = PrPasSumaLISTH(k, cLIST[NMAX+1]);

  

     // Pasa a campos de pantalla

     m_LISTH0.AddString(cLIST[0]);

     . . .

     m_LISTH32.AddString(cLIST[32]);

 

     m_Suma = k;

     k = 0;

    }

 

    // Pasa resultados a pantalla

    UpdateData(false);

 

    return;

   }

 

Según el parámetro m_Sudoku, la generación construirá un cuadrado mágico como hemos visto antes, o un sudoku con una codificación más compleja, cuyo control se centra en las sentencias siguientes:

    short int PrGeneraSudoku(long N)

  {

    short int er = 0;      // Control de errores

    short int iFacil = 0;  // 0/1 el sudoku generado es de fácil predicción, tiene parejas repetidas

    long lResul = 0;       // Resultado de Srmagic_ramdon

 

    long n = (long) sqrt((double)N); // Total de supercubos, dimensión local

 

    // Rutina de expansión del cuadrado latino núcleo del Sudoku y evaluación del resultado

 

    er = PrSudoku(n); // Expansión

    if (er) return er;

 

    er = PrSudokuRefino(N, &iFacil); // Refinado y evaluación

    if (er) return er;

 

    // Una de cada 100 veces en media no discrimina resultado fácil

   lResul = SRmagic_Random(100);

    if (lResul <= 1) return NO_ERRO;

 

    // Reintenta hasta conseguir uno + difícil

    if (iFacil) return PrGeneraSudoku(N);

 

    // Fin de proceso

    return NO_ERRO;

  }

 

 Código desde donde se controla la llamada a las rutinas auxiliares específicas que se muestran a continuación

   //-----------------------------------------------------------------------------

   // Rutina de expansión sudoku. Toma un cuadrado latino y lo replica trivialmente

   //-----------------------------------------------------------------------------

   short int PrSudoku(long N)

   {

    short int er = 0; // Control de errores

    long c = 3;        // Nºcolumnas replicadas(Para sudokus ó seudosudokus -3 columnas-)

    long i = 0;        // Contador de superfilas de cubos

    long j = 0;        // Contador de supercolumnas cúbicas

    long k = 0;       // Contador 1..N diagonal

 

    if (N == 5) c = 5;

 

    // Se parte del cuadrado origen y se extienden sus filas y columnas hasta c*N

    // Construye la L principal

 

    // Expande columnas del cubo 1,1 a su derecha

    for (j=1;j<=PrMin(N,c);++j) er = PrSudokuJI(N, 1, j, c);

 

 

 

 

Esta es la codificación que sustenta la expansión indicada antes: 

 

        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

 

    

      

      // Similarmente, se expanden las filas del cubo 1,1 hacia abajo

     for (i=1;i<=N;++i) er = PrSudokuIJ(N, i, 1, c);

    

     // Construye las L's encajadas, rellenando los huecos de forma similar

     for (k=1;k<=N;++k)

     {

      // Expande filas de la k,k hacia abajo

      for (i=1;i<=N;++i) er = PrSudokuIJ(N, i, k, c);

     

      // Expande columnas de k,k a su derecha

      for (j=k;j<PrMin(N,c);++j) er = PrSudokuJI(N, k, j, c);

     }

 

     // Cierra la L final, expandiendo filas de la N,1 hacia abajo

     for (i=1;i<=N;++i) er = PrSudokuIJ(N, i, N, c);

   

     return NO_ERRO;

   }

                                                                                                           ________

 

    //-----------------------------------------------------------------------------

   // Rutina de refinado de un Sudoku trivial para obtener otro usual equivalente

   //-----------------------------------------------------------------------------

   short int PrSudokuRefino(long N, short int *iFacil)

   {

    short int er = 0;  // Control de resultados

    long i = 0;        // Contador de for en filas

    long j = 0;        // Contador de for en columnas

    long n = (long) sqrt((double)N); // Total de supercubos, dimensión local

   

    // Ciclo de refinado en i

    for (i=1;i<=n;++i)

    {

     er = PrSudokuRefinoi(N, 1 + n * (i-1));

     if (er) return er;

    }

    

    // Ciclo de refinado en j

    for (j=1;j<=n;++j)

    {

     er = PrSudokuRefinoj(N, 1 + n * (j-1));

     if (er) return er;

    }

   

    // Evaluación del tipo resultante.

   

    // Si hay parejas repetidas, con un Sudoku de fácil predicción, se rechazará

    *iFacil = PrVerFacil(N);

   

     return NO_ERRO;

   }

                                                                                                          ________

 

La rutina de refinado en i, algo resumida, se muestra a continuación; el refino en j es similar:

    //-----------------------------------------------------------------------------

   // Subrutina de refinado. Fila i < N

   //-----------------------------------------------------------------------------

   short int PrSudokuRefinoi(long N, long i)

   {

    long lresul = 0;   // Control de resultados

    long vo = 0;       // Valor origen/destino

    long va = 0;       // Valor actual

    long  j = 0;       // Contador de for en columnas

 

     long n = (long) sqrt((double)N); // Total de supercubos, dimensión local

 

     // Filtro

    if ((i <= 0) || (i > N-n+1) ) return 1;

  

    // Valor origen

    lresul = PrChain(i, 1);

    vo = DSc.DD.lk;

  

    // Valor de intercambio actual inicial

    lresul = PrChain(i+n-1, 1);

    va = DSc.DD.lk;

  

    // Intercambio inicial

    lresul = PrSwapIJ(N, i, 1, i+n-1, 1);

  

    // Bucles de refino

    do

    {

     for (j=2;j<=N;++j)

     {

      lresul = PrChain(i, j);

     

      // Intercambio actual

      if (DSc.DD.lk == va)

      {

       lresul = PrChain(i+n-1, j);

       va = DSc.DD.lk;

       lresul = PrSwapIJ(N, i+n-1, j, i, j);

       if (va == vo) break;

      }

     }

 

    } while (vo != va);

   

    return NO_ERRO;

   }

                                                                                                          ________

 

En cuanto a la rutina de evaluación de parejas repetidas, consiste en grabar las parejas del primer subcubo en un fichero virtual de parejas y repasar el resto frente al mismo. Veamos el fragmento dedicado a las filas

    //---------------------------------------------------------------------------------

   // Rutina auxiliar para determinar si el sudoku generado es fácil por tener parejas repetidas

   //---------------------------------------------------------------------------------

   short int PrVerFacil(long N)

   {

    short int er = 0;  // Control de errores

    long lresul = 0;   // Control de resultados intermedios

    long i = 0, j = 0; // Contadores de for. Filas, columnas

    long vi = 0;       // Valor de pareja i

    long vj = 0;       // Valor de pareja j

    long k = 0;        // Importe recuperado

 

    long n = (long) sqrt((double)N); // Total de supercubos, dimensión local

 

  

    // Inz.Fichero de parejas

    er = SRRCW_CLRF("PMAGICP");

 

 

 

    En SRmagic_Open “PMAGICP” se crea como

    

         lNID = SRRCW_NEW("PMAGICP", sizeof(sDsK));

      donde sDsK es la estructura común de claves para nodos (i,j) que vimos antes:

 

         struct sDsK   // Estructura de claves de acceso a nodos (i,j)

         {

          long li;     // Índice i del nodo

          long lj;     // Índice j del nodo

         };

   

      // 1er.Ciclo de evaluación (Por filas)

     

      // Carga parejas del 1er.subcubo

       for (i=1;i<=n;++i)

       {

        lresul = PrChain(i, 1);

        vi = DSc.DD.lk;

        lresul = PrChain(i, 2);

        vj = DSc.DD.lk;

 

        lresul = PrWriteP(vi, vj);

 

 

        lresul = PrChain(i, 2);

        vi = DSc.DD.lk;

        lresul = PrChain(i, 3);

        vj = DSc.DD.lk;

 

        lresul = PrWriteP(vi, vj);

       }

    

       // Evalúa parejas de los siguientes subcubos

       for (i=1;i<=n;++i)

       {

        lresul = PrChain(i, n+1);

        vi = DSc.DD.lk;

        lresul = PrChain(i, n+2);

        vj = DSc.DD.lk;

        lresul = PrChainP(vi, vj);

        if (lresul > 0) return 1;

    

        lresul = PrChain(i, n+2);

        vi = DSc.DD.lk;

        lresul = PrChain(i, n+3);

        vj = DSc.DD.lk;

        lresul = PrChainP(vi, vj);

        if (lresul > 0) return 1;

    

        lresul = PrChain(i, 2*n+1);

        vi = DSc.DD.lk;

        lresul = PrChain(i, 2*n+2);

        vj = DSc.DD.lk;

        lresul = PrChainP(vi, vj);

        if (lresul > 0) return 1;

    

        lresul = PrChain(i, 2*n+2);

        vi = DSc.DD.lk;

        lresul = PrChain(i, 2*n+3);

        vj = DSc.DD.lk;

        lresul = PrChainP(vi, vj);

        if (lresul > 0) return 1;

       }

  

      // 2do.Ciclo de evaluación (Por columnas)

    

      // Reinicia fichero de parejas

       er = SRRCW_CLRF("PMAGICP");

  

       . . . (Código similar para columnas)

  

     // Si llega aquí, el sudoku no tiene parejas repetidas evidentes

     return 0;

   }

                                                                                                          ________

 

En esta rutina se utilizan las rutinas auxiliares de grabación/recuperación desde el fichero virtual de parejas, muy similares a las utilizadas para el propio fichero virtual soporte del sudoku, de las que pueden considerarse versiones resumidas y que exponemos a continuación:

   //-----------------------------------------------------------------------------

   // Rutina auxiliar de recuperación de un ítem de parejas

   //-----------------------------------------------------------------------------

   long PrChainP(long i, long j)

   {

    long lresul = 0; // Control de resultados

    sDsK DsK;        // Ds work paso de datos

 

    // Clave de acceso

    DsK.li = i;  

    SRRCAL_lLexi(&DsK.li);  // Pasa valor a peso

    DsK.lj = j;

    SRRCAL_lLexi(&DsK.lj);

 

    // Recupera importe

    lresul = SRRCW_CHAIN("PMAGICP", &DsK);

 

    return lresul;

   }

 

      //-----------------------------------------------------------------------------

   // Rutina auxiliar de grabación de un ítem pareja

   //-----------------------------------------------------------------------------

   long PrWriteP(long i, long j)

   {

    long lresul = 0; // Control de resultados

    sDsK DsK;        // Ds work paso de datos

 

    // Elimina previo si existe

    lresul = PrDeleteP(i, j);

 

    // Clave & datos

    DsK.li = i;

    SRRCAL_lLexi(&DsK.li); // Paso de valor a peso

    DsK.lj = j;

    SRRCAL_lLexi(&DsK.lj);

 

    // Graba ítem

    return SRRCW_WRITE("PMAGICP", &DsK);

   }

                                                                                                          ________

 

 

Esta codificación se verá bajo una perspectiva diferente al extraerla y convertirla en un servicio externo para poder utilizarla en un interfaz NET, objeto de la segunda zona del libro. Entonces retomaremos el detalle de la codificación que convertiremos en una DLL central y la aplicaremos para su utilización en programas de presentación separada escritos tanto en C como en Visual Basic.

 

                                                                                                          ________

 

A.II.1.10 Código agregado para presentación lúdica

Para que tenga un carácter lúdico, se agrega visualización discrecional, botones de prueba y resultados estadísticos asociados como se muestra en la imagen del interfaz siguiente 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

esta implementación se apoya en una pequeña ampliación de la base de datos virtual en la que incorpora la marca de visualización, como sigue

 

 

   // Ds de datos del fichero de soporte del cuadrado

   struct sDsD   // Estructura de datos asociados

   {

    long lk;     // Valor de k del nodo

    char ck[4];  // k en formato alfanumérico para presentación

    short int a; // 0,1 Visualmente activo

   }; 

 

 

 partiendo de la nueva definición, se pueden añadir al programa funciones para activar, desactivar y controlar la visualización; funciones cuyo detalle examinaremos en la DLL que se construirá en la segunda zona del libro.

 

Este es un buen ejemplo de la potencia y versatilidad de la herramienta, pues en él se ve como permite el soporte del desarrollo de ideas nuevas sobre edificios antiguos simplemente ampliando los diseños de las estructuras en que se basan para dar cabida a nuevas algorítmicas, y a continuación añadiendo la codificación que utilice los nuevos campos, permitiendo un desarrollo modular.

 

En próximos ejemplos veremos que no sólo se puede ampliar el diseño de la parte de datos, si no que si el desarrollo lo precisa también es muy fácil incorporar nuevas vías de acceso sobre los mismos datos de soporte.

 

El código completo de esta serie se encuentra en el apéndice

"C5 Relación de programas de muestra desarrollados en el libro"

 

 

                                                                                                          ________