Kakuro - Kakuro

Un sencillo rompecabezas de Kakuro
Solución para el rompecabezas anterior

Kakuro o Kakkuro o Kakoro ( japonés :カ ッ ク ロ) es una especie de acertijo de lógica que a menudo se conoce como una transliteración matemática del crucigrama . Los acertijos de Kakuro son características habituales en muchas publicaciones de acertijos matemáticos y lógicos en todo el mundo. En 1966, el canadiense Jacob E. Funk, un empleado de Dell Magazines , inventó el nombre original en inglés Cross Sums y también se han utilizado otros nombres como Cross Addition , pero el nombre japonés Kakuro, abreviatura del japonés kasan kurosu (加 算 ク ロ ス, "cruz de adición"), parece haber ganado aceptación general y los acertijos parecen titularse de esta manera ahora en la mayoría de las publicaciones. La popularidad de Kakuro en Japón es inmensa, sólo superada por Sudoku entre las famosas ofertas de acertijos lógicos de Nikoli .

El rompecabezas canónico de Kakuro se juega en una cuadrícula de celdas llenas y barradas, "negras" y "blancas" respectivamente. Los rompecabezas suelen tener un tamaño de 16 × 16, aunque estas dimensiones pueden variar ampliamente. Aparte de la fila superior y la columna más a la izquierda, que son completamente negras, la cuadrícula está dividida en "entradas", líneas de celdas blancas, por celdas negras. Las celdas negras contienen una barra diagonal de la parte superior izquierda a la inferior derecha y un número en una o ambas mitades, de modo que cada entrada horizontal tiene un número en la media celda negra a su izquierda inmediata y cada entrada vertical tiene un número en la media celda negra inmediatamente encima. Estos números, tomando prestada terminología de crucigramas, se denominan comúnmente "pistas".

El objetivo del rompecabezas es insertar un dígito del 1 al 9 inclusive en cada celda blanca para que la suma de los números en cada entrada coincida con la pista asociada con ella y que no se duplique ningún dígito en ninguna entrada. Es esa falta de duplicación lo que hace posible la creación de rompecabezas de Kakuro con soluciones únicas. Al igual que el Sudoku, resolver un rompecabezas de Kakuro implica investigar combinaciones y permutaciones . Existe una regla no escrita para hacer acertijos de Kakuro que dice que cada pista debe tener al menos dos números que se sumen, ya que incluir solo un número es matemáticamente trivial al resolver acertijos de Kakuro.

Al menos un editor incluye la restricción de que una combinación determinada de números solo se puede usar una vez en cada cuadrícula, pero aún comercializa los rompecabezas como Kakuro simple.

Algunos editores prefieren imprimir sus cuadrículas de Kakuro exactamente como cuadrículas de crucigramas, sin etiquetas en las celdas negras y en su lugar numerando las entradas, proporcionando una lista separada de las pistas similar a una lista de pistas de crucigramas. (Esto elimina la fila y la columna que son completamente negras). Esto es puramente una cuestión de imagen y no afecta ni a la solución ni a la lógica requerida para resolver.

Al discutir los acertijos y las tácticas de Kakuro, la forma abreviada típica para referirse a una entrada es "(pista, en números) -en- (número de celdas en la entrada, deletreadas)", como "16 en dos" y "25 -en cinco". La excepción es lo que de otro modo se llamaría el "45 en nueve"; simplemente se usa "45", ya que el "-en-nueve" está implícito matemáticamente (nueve celdas es la entrada más larga posible, y dado que no puede duplicar un dígito debe constar de todos los dígitos del 1 al 9 una vez). Curiosamente, tanto "43 en ocho" como "44 en ocho" todavía se llaman con frecuencia como tales, a pesar de que el sufijo "-en-ocho" está igualmente implícito.

Técnicas de resolución

Técnicas combinatorias

Aunque es posible adivinar por fuerza bruta, un enfoque más eficiente es la comprensión de las diversas formas combinatorias que pueden adoptar las entradas para varios pares de pistas y longitudes de entrada. El espacio de la solución se puede reducir resolviendo las intersecciones permitidas de sumas horizontales y verticales, o considerando los valores necesarios o faltantes.

Aquellas entradas con pistas suficientemente grandes o pequeñas para su longitud tendrán menos combinaciones posibles para considerar y, al compararlas con las entradas que las cruzan, se puede derivar la permutación adecuada, o parte de ella. El ejemplo más simple es donde un 3 en dos se cruza con un 4 en dos: el 3 en dos debe consistir en "1" y "2" en algún orden; el 4 en dos (ya que "2" no se puede duplicar) debe constar de "1" y "3" en algún orden. Por lo tanto, su intersección debe ser "1", el único dígito que tienen en común.

Al resolver sumas más largas, existen formas adicionales de encontrar pistas para localizar los dígitos correctos. Uno de esos métodos sería observar dónde unos pocos cuadrados juntos comparten valores posibles, eliminando así la posibilidad de que otros cuadrados en esa suma puedan tener esos valores. Por ejemplo, si dos pistas 4 en dos se cruzan con una suma más larga, entonces el 1 y el 3 en la solución deben estar en esos dos cuadrados y esos dígitos no se pueden usar en otra parte de esa suma.

Al resolver sumas que tienen un número limitado de conjuntos de soluciones, eso puede conducir a pistas útiles. Por ejemplo, una suma de 30 en siete solo tiene dos conjuntos de soluciones: {1,2,3,4,5,6,9} y {1,2,3,4,5,7,8}. Si uno de los cuadrados en esa suma solo puede tomar los valores de {8,9} (si la pista de cruce es una suma de 17 en dos, por ejemplo), entonces eso no solo se convierte en un indicador de qué conjunto de soluciones se ajusta a este suma, elimina la posibilidad de que cualquier otro dígito en la suma sea cualquiera de esos dos valores, incluso antes de determinar cuál de los dos valores encaja en ese cuadrado.

Otro enfoque útil en acertijos más complejos es identificar en qué cuadrado entra un dígito eliminando otras ubicaciones dentro de la suma. Si todas las pistas de cruce de una suma tienen muchos valores posibles, pero se puede determinar que solo hay un cuadrado que podría tener un valor particular que debe tener la suma en cuestión, entonces cualesquiera otros valores posibles que permita la suma de cruce, esa intersección debe ser el valor aislado. Por ejemplo, una suma de 36 en ocho debe contener todos los dígitos excepto 9. Si solo uno de los cuadrados puede tomar el valor de 2, entonces esa debe ser la respuesta para ese cuadrado.

Técnica de caja

Una "técnica de caja" también se puede aplicar en ocasiones, cuando la geometría de los glóbulos blancos vacíos en cualquier etapa dada de la resolución se presta a ello: sumando las pistas para una serie de entradas horizontales (restando los valores de cualquier dígito ya agregado a esas entradas) y restando las pistas para una serie de entradas verticales que se superponen en su mayoría, la diferencia puede revelar el valor de una entrada parcial, a menudo una sola celda. Esta técnica funciona porque la suma es asociativa y conmutativa .

Es una práctica común marcar los valores potenciales para las celdas en las esquinas de las celdas hasta que se haya demostrado que todos menos uno son imposibles; para acertijos particularmente desafiantes, a veces los solucionadores anotan rangos completos de valores para celdas con la esperanza de encontrar eventualmente restricciones suficientes para esos rangos, desde entradas cruzadas para poder reducir los rangos a valores únicos. Debido a las limitaciones de espacio, en lugar de dígitos, algunos solucionadores usan una notación posicional, donde un valor numérico potencial se representa mediante una marca en una parte particular de la celda, lo que facilita la colocación de varios valores potenciales en una sola celda. Esto también hace que sea más fácil distinguir los valores potenciales de los valores de la solución.

Algunos solucionadores también usan papel cuadriculado para probar varias combinaciones de dígitos antes de escribirlas en las cuadrículas del rompecabezas.

Como en el caso del Sudoku, solo los rompecabezas de Kakuro relativamente fáciles se pueden resolver con las técnicas mencionadas anteriormente. Los más difíciles requieren el uso de varios tipos de patrones de cadena, los mismos que aparecen en el Sudoku (consulte Satisfacción de restricciones basada en patrones y Rompecabezas lógicos ).

Matemáticas de Kakuro

Matemáticamente, los acertijos de Kakuro se pueden representar como problemas de programación de números enteros y son NP-completos . Véase también Yato y Seta, 2004.

Hay dos tipos de simetría matemática fácilmente identificables en los acertijos de Kakuro: las restricciones mínimas y máximas son duales, al igual que los valores faltantes y requeridos.

Todas las combinaciones de suma se pueden representar mediante una representación de mapa de bits. Esta representación es útil para determinar valores faltantes y requeridos mediante operaciones lógicas bit a bit .

Popularidad

Los rompecabezas de Kakuro aparecen en casi 100 revistas y periódicos japoneses. Kakuro siguió siendo el acertijo de lógica más popular en la prensa impresa japonesa hasta 1992, cuando Sudoku ocupó el primer lugar. En el Reino Unido, aparecieron por primera vez en The Guardian con The Telegraph y el Daily Mail como seguidores.

Ver también

  • Killer Sudoku , una variante del Sudoku que se resuelve utilizando técnicas similares.

Referencias

enlaces externos