Un sitio personal para aprender desarrollo web

Sudoku: Fish

Sudoku Fish

El grupo Fish de técnicas de resolución de un Sudoku se basa en una rejilla de n×n celdas que comprende 'n' conjuntos fila × 'n' conjuntos columna, o viceversa. En las intersecciones entre filas y columnas hemos de encontrar un disponible al menos en dos de ellas. Uno de los conjuntos se denomina conjunto base y el otro conjunto cobertura.

Estas son las técnicas que he implementado:

Sudoku: Unicidad

Sudoku con 2 soluciones

Un verdadero Sudoku es aquel tablero inicial que conduce a una única solución. Muchos tableros iniciales conducen a resultados con más de una solución. E incluso algunos no tienen solución. El problema de resolver un Sudoku con técnicas de profundizado y sin usar el último recurso del vuelta atrás parte de la base de que el tablero inicial conduce a una única solución. Y esto puede aprovecharse para crear un nuevo conjunto de técnicas que se agrupan dentro del termino Unicidad (Uniqueness).

El tablero del ejemplo en la imagen adjunta muestra el momento en que hay sólo cuatro celdas que llenar, todas con los mismos diponibles '69'. Si en una ponemos '6', en la otra en la misma fila hemos de poner '9'. Y sus opuestos en la otra fila. Esto conduce a obtener dos soluciones para el Sudoku. Por lo tanto para ese tablero no aplica el concepto de unicidad, pues tiene dos soluciones. Pero cuando aplicamos las técnicas de resolución partimos de la base de que el Sudoku se planteó en un tablero inicial para que tuviera solución única. El rectángulo de NO unicidad formado por las cuatro celdas sin llenar que se observa en la Figura no puede darse nunca en un verdadero Sudoku. Ese rectángulo que debemos evitar se suele denominar patrón mortal o deadly pattern en la terminología en inglés. En lo que sigue veremos como aprovechar estos conceptos para encontrar y borrar números disponibles, para lo cual hemos de evitar que aparezca un rectángulo de no unicidad.

Basándonos en estos conceptos aplicaremos las técnicas de unicidad rectángulos únicos, ocultos y evitables (unique, hidden and avoidable rectangles) así como la técnica BUG+1:

Esquema Ala WXYZ fila tipo I Esquema Ala WXYZ fila tipo II

La técnica de resolución o profundizado de un Sudoku denominada Ala WXYZ (WXYZ Wing) se basa en cuatro celdas y cuatro números W, X, Y, Z. Hay dos tipos I y II de Ala WXYZ. En los esquemas adjuntos se observan ambos tipos. La celda WXYZ puede contener entre 2 y 4 números W, X, Y o Z, pero al menos debe contener W o Z necesariamente. A continuación encontraremos una celda con los disponibles WZ, que para el tipo I estará en la misma caja y para el tipo II en la misma fila. Finalmente econtraremos dos celdas con XYZ, que puede tener entre 2 y 3 números de valores X, Y o Z, sin que puedan contener W. Para el tipo I estarán en la misma fila que WXYZ. Y para el tipo II en la misma caja que WXYZ.

Si se cumplen las condiciones anteriores podemos eliminar hasta dos disponibles z en las celdas resaltadas.

Sudoku: Esquema Ala XYZ (XYZ-wing scheme)

La técnica de resolución (o profundizado) de un Sudoku denominada Ala XYZ (XYZ-Wing) se basa en tres celdas que contengan los disponibles (pencil marks) XYZ, XZ e YZ. En una caja encontraremos XYZ e YZ en distintas filas y en cualquier columna dentro de esa caja. En la otra caja, contigua a la derecha en el caso del esquema adjunto, encontraremos XZ en la misma fila que XYZ. En estas condiciones el número z puede ser eliminado de las dos celdas de la fila dentro de la caja donde se encuentra XYZ.

Sudoku: Esquema Ala W (W-wing scheme)

Por otro lado la técnica Ala W (W-Wing) involucra dos cajas, una fila o columna y dos números W y P. Según su disposición pueden dar lugar seis posibles casos según que las cajas con WP estén situadas en la misma o distintas bandas y pilas, así como la disposición de fila o columna donde encontraremos los números W.

Sudoku: Ala X (X-wing)

El grupo de técnicas de profundizado Wing comprende muchas de ellas. En alguna documentación sobre esto las separa en dos grupos: Fish y el propio Wing, estableciendo que X-wing pertenezca Fish y XY-wing a Wing. Sin embargo no me voy a liar con esto y las agruparé todas en Wing. En este tema sólo voy a presentar en este grupo las básicas X-wing y XY-wing que se traduce como Ala X y Ala XY.

En la imagen puede ver un X-wing en filas primera y sexta, en las posiciones del rectángulo que forman las celdas [1, 4], [1, 7], [6, 4] y [6, 7]. En este caso es un disponible '9' único en esas filas. Por lo tanto podemos eliminar los diponibles '9' en otras celdas de las columnas cuarta y séptima, encontrándonos con '9' a eliminar en las celdas [2, 7], [4, 4] y [4, 7].

Sudoku: único solitario (naked single)

Las técnicas de resolución de un Sudoku son aquellas que consiguen una solución sin necesidad de utilizar el último recurso del vuelta atrás (backtracking). En estos temas también las denomino técnicas de profundizado pues nos ayudan a profundizar en el árbol de resolución.

En este tema expondré las técnicas básicas: únicos solitarios y ocultos, parejas solitarias y ocultas, trios solitarios y ocultos y bloqueados. En inglés se les denomina naked and hidden singles, naked and hidden pairs, naked and hidden trios y locked.

Son muchas las técnicas pero sólo dos de ellas sirven para descubrir nuevos números. Son los únicos solitarios u ocultos. En la imagen vemos una captura de la aplicación para la gestión de Sudokus, aplicación que nos descubre pistas para resolver el Sudoku, descubriendo un único solitario (naked single) en la celda [1, 6].

Aplicación Sudoku

Sudoku simétrico

Un Sudoku es un juego consistente en un tablero de 9×9 celdas con las restricciones de colocar un número del conjunto {1,2,3,4,5,6,7,8,9} en cada celda debiendo aparecer sólo uno de ellos en cada fila, columna y caja. Una caja es cada uno de los rectángulos de 3×3 celdas. Las cajas se agrupan en filas denominadas bandas y columnas denominadas pilas. El objetivo del juego es rellenar todas las celdas respetando esas restricciones.

En este tema se expone una aplicación para resolver y gestionar Sudokus. Contempla la generación aleatoria así como una utilidad para estudiar las técnicas de resolución como naked and hidden singles, naked and hidden pairs, naked and hidden trios, locked, X Wing, XY Wing.

Ramificación árbol Sudoku

El algoritmo recursivo de vuelta atrás (backtracking) tiene por objetivo recorrer una estructura de árbol para encontrar uno o más nodos que cumplan determinados requisitos. En el tema sobre recursivos vuelta atrás expuse algunos ejemplos de uso. Es adecuado para resolver un Sudoku, donde podemos asimilar cada combinación posible de números en el tablero como un nodo del árbol.

Instancia 0 de un componente

Un componente web es la programación de una utilidad para insertar en una página y reutilizar en otras páginas. Cabe la posibilidad de que se inserten múltiples instancias del mismo componente en una página. Pueden programarse usando POO (Programación Orientada a Objetos). Pero usando la capacidad de encapsulamiento de los closures en JavaScript podemos montar módulos que consigan los mismos objetivos que los originados con POO.

Supongamos que hemos de realizar un componente como el de la imagen. Se trata de insertar en una página web una o más instancias de una interfaz de usuario que lleven a cabo operaciones usando los valores que el usuario introduce en los elementos de control. Usaremos este ejemplo muy simple para exponer los detalles de implementación de módulos de múltiples instancias sin usar POO.

Importar HTML+CSS en WXTABLE

Mejora en el Gestor de tablas WXTABLE para importar una tabla HTML incluyendo el CSS en atributos style y también ubicado en un elemento STYLE.

Hasta ahora se podía copiar el código HTML de una tabla importándose también el estilo que portaban los elementos en sus atributos style. Ahora también puede pasarse el código de un elemento <style> importándose ese CSS. En la imagen se observa una importación de una tabla de ejemplo que contiene ambos estilos en línea al elemento y a la página.

Exportando a XLSX

Exportando a XLSX

Cuando hice el Gestor de tablas WXTABLE incluí varios formatos de exportación a falta del formato XLSX. Ahora se incluye este nuevo formato tras estudiar previamente un par de cosas necesarias para llevarlo a cabo. Una de ellas es saber cómo crear un ZIP, puesto que un XLSX es en esencia un ZIP con los datos en archivos XML empaquetados en un archivo ZIP. Antes de eso necesité saber cómo generar un CRC puesto que es imprescindible para crear un ZIP.

En esta serie de doce temas se explican detalles con los que tuve que lidiar para conseguir exportar desde HTML+CSS a XLSX con cierto éxito. No hay que olvidar que la aplicación que gestiona las tablas lo hace con elementos HTML y CSS. Así que lo que se explica en esos temas también sirve para adquirir conocimiento de la experiencia de exportación desde HTML+CSS a XLSX.

Aparte del tema introductorio podrá encontrar temas que exponen un XLSX básico, contenidos de celdas, referencias, fórmulas, fórmulas matriz, características estructurales, estilos, columnas, formatos, validaciones e imágenes.

Exportador XLSX

Trazado de la exportación a XLSX

La herramienta Exportador XLSX nos permite trazar el proceso de ejecución del módulo xlsx.js para exportar a XLSX contenidos creados en HTML+CSS en formato WXTABLE. Este formato es el que se usa en el Gestor de tablas para exportar su contenido.

En la serie de temas que se inicia en Exportando a XLSX se explican los detalles del proceso de exportación. En este tema nos dedicaremos a explicar como funciona la herramienta para trazar el proceso.


...Ver más en el histórico