El Blog de Gualtrysoft

Windows 2000/2003/2008, Active Directory, VBScript, Hyper-V, PowerShell y todo aquello interesante a la hora de usar, configurar y administrar Windows Server. También tenemos longanizas…

Oracle 11gR2 y la query del sudoku

Posted by calabuch en Miércoles 11 \11\UTC agosto \11\UTC 2010

Es raro encontrar  código de Oracle que se pueda aplicar inmediatamente al mundo de la no-informática, en este caso hemos encontrado una query que resuelve un sudoku. Lo mejor de esta consulta es que cumple la máxima : “No hagas en un bloque (pl/sql) lo que puedas resolver en una sola consulta.”, bueno, decir que la cumple es poco, realmente es un ejemplo excelente de esta directriz.

Antes de empezar recordemos que el uso de WITH antes de la claúsula SELECT permite obtener un grupo de registros una vez para luego ser filtrados y/o manipulados posteriormente en la claúsula SELECT, es como una subquery que se ejecuta una – y sólo una – vez,  independientemente de cómo se use después.

La query del sudoku se puede hacer en la versión 11g R2 de Oracle, que trae consigo la llamada “Recursive Subquery Factoring”, que es una nueva forma de hacer consultas recursivas, es decir, generar registros a partir de otros registros que se traen con la propia consulta.

La estructura externa básica de la query del sudoku es :

WITH x(s, ind) as
    (SELECT ...   /* registro padre */
     UNION ALL
     SELECT ...   /* registros hijos */
    )
SELECT ...
  FROM x
...

Esta estructura produce el siguiente comportamiento :

  • WITH x(s, ind) ” :  se generará una tabla temporal de nombre “x”, que contiene las columnas “s” e “ind”
  • (SELECT…” :  la tabla temporal se llena inicialmente con la query que produce los registros padre, por eso en esta parte no se puede referenciar a la tabla temporal “x”.
  • UNION ALL” :  el nexo de las consultas de la claúsula WITH puede ser UNION, UNION ALL, INTERSECT o MINUS
  • SELECT…” :  se ejecuta la query de los registros hijos, la cual trabajará con los registros que ya existen en la tabla temporal haciendo referencia a “x” y sus columnas, por esta razón se dice que puede ser recursiva, se generarán otros registros finales a partir de registros finales que ya se han traído.
  • SELECT … FROM x” :  se obtienen todos o parte de los registros manipulados o no de la tabla temporal una vez que esta está completa

Esta es la query del sudoku, a continuación vamos a comentarla :

1  WITH x(s, ind) as
2     (SELECT sud, instr(sud, ' ')
3        FROM (SELECT '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28'||
                      '    419  5    8  79' sud
4                FROM dual)
5       UNION ALL
6      SELECT substr(s, 1, ind - 1) || z || substr(s, ind + 1) , instr(s, ' ', ind + 1)
7        FROM x, (SELECT to_char(rownum) z
8                   FROM dual
9                 CONNECT BY rownum <= 9) z
10      WHERE ind > 0
11        AND not exists (SELECT null
12                          FROM (SELECT rownum lp
13                                  FROM dual
14                                CONNECT BY rownum <= 9
15                               )
16                         WHERE z = substr(s, trunc((ind - 1) / 9) * 9 + lp, 1)
17                            OR z = substr(s, mod(ind - 1, 9) - 8 + lp * 9, 1)
18                            OR z = substr(s, mod(trunc( (ind - 1) / 3), 3) * 3
19                                             + trunc((ind - 1) / 27) * 27 + lp
20                                             + trunc((lp - 1) / 3) * 6
21                                             , 1 )
22                       )
23    )
24 SELECT s
25   FROM x
26  WHERE ind = 0;
Nota : la línea 3 ha sido dividida sólo para poder publicarla correctamente, de ahí 
que la línea siguiente no tenga número de orden.

Con lo que ya sabemos podemos deducir que en las líneas 2,3 y 4 la tabla temporal “x” se rellena inicialmente con la columna “sud”, que contiene la cadena de números y espacios del sudoku planteado en orden de casillas de izquierda a derecha y de arriba a abajo, como la lectura habitual de un texto, y la columna “ind”, que  tiene la posición del primer espacio dentro de la cadena obtenida. Este será el registro inicial de nuestra tabla temporal a partir del cual generaremos todos los demás en la SELECT siguiente.

En las líneas 6 a 22 se trabaja con el registro ya existente en la tabla temporal y se ejecutará la consulta para alimentar la tabla temporal. En esta parte se utiliza la tabla temporal “x” y los registros de “z” (los dígitos de 1 al 9) para generar todos los dígitos del 1 al 9 en el espacio que estamos tratando

     substr(...) || z || substr(...)

y localizar el siguiente espacio en la cadena “s”

     instr(s, ' ', ind + 1)

De esta manera se van probando todos los dígitos posibles en todos los espacios mientras haya espacios en las cadenas generadas (condición de línea 10), y se cumplan las condiciones ya conocidas en un sudoku :
– en cada línea horizontal del sudoku sólo pueden aparecer los números del 1 al 9 una vez, ninguno se repite y aparecen todos (condición indicada en la línea 16).
– en cada columna ocurre lo mismo (línea 17)
– en cada grupo de 9 celdas (3 por 3) se cumple la misma condición (líneas 18 a 21).

Estas 3 condiciones se pueden escribir de varias maneras, y sin duda esto es complicado de simplificar, se ha necesitado la columna “lp” (entiendo que es abreviación de loop) que son las veces o iteraciones necesarias para ejecutar las condiciones. Personalmente, me ha costado un tiempo analizarlas pero es un buen ejercicio de aprendizaje.

Por lo tanto la tabla temporal “x” tiene los registros de la cadena con todos los dígitos posibles en todos los espacios menos los que no cumplen las condiciones de sudoku (que el “z” (dígitos del 1 al 9) no exista ya en la línea, la columna o el cuadrante de 3×3) pero los registros sí tendrán espacios ya que el espacio es distinto que cualquier valor de “z”, esto permite guardar registros con espacios que sabemos que no son los buenos, pero que necesitamos para generar más registros hasta llegar a la meta.

Habrá un momento en que la SELECT de la línea 6 trate el último espacio del sudoku, entonces dejará la cadena con todos los dígitos posibles en ese espacio (realmente solo un dígito posible, un registro) y el valor de “ind” quedará como 0 porque se acaba de rellenar el último espacio. Este es el registro que buscamos, el que no tiene espacios, por eso es el único que obtenemos con el filtro de la línea 26 : no tiene espacios y cumple con las 3 reglas del sudoku, objetivo cumplido.

Referencias :

La query la hallé en : esta entrada del blog Weblog for the AMIS Technology corner

Mas info de Recursive Subquery Factoring : esta sección de Oracle® Database SQL Language Reference 11g Release 2 (11.2)

Una respuesta to “Oracle 11gR2 y la query del sudoku”

  1. […] https://urpiano.wordpress.com/2010/08/11/oracle-11gr2-y-la-query-del-sudoku/ August 12, 2010   //   Oracle   //   No Comments   //   […]

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
A %d blogueros les gusta esto: