Sudoku

Sudoku (en japonés: 数独, sūdoku) es un pasatiempo popular que se popularizó en Japón en 1986, y se dio a conocer en el ámbito internacional en 2005. El objetivo es rellenar una cuadrícula de 9 × 9 celdas (81 casillas) dividida en subcuadrículas de 3 × 3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas. Aunque se podrían usar colores, letras, figuras, se conviene en usar números para mayor claridad. Lo que importa, en todo caso, es que sean nueve elementos diferenciados. No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. Un sudoku está bien planteado si la solución es única. La resolución del problema requiere paciencia y ciertas dotes lógicas.

Ejemplo de sudoku.

La solución de un sudoku siempre es un cuadrado latino, aunque el recíproco en general no es cierto ya que el sudoku establece la restricción añadida de que no se puede repetir un mismo número en una región.

Numerosos periódicos han empezado a publicar el sudoku desde el 2005 en su sección de pasatiempos.

Historia

Este rompecabezas numérico puede haberse originado en Nueva York en 1979. Entonces, la empresa Dell Magazines publicó este juego, ideado por Howard Garns, bajo el nombre de Number Place (el lugar de los números).

Es muy probable que el sudoku se crease a partir de los trabajos de Leonhard Euler, famoso matemático suizo del siglo XVIII.​ Dicho matemático no creó el juego en sí, sino que utilizó el sistema llamado «cuadrado latino» para realizar cálculos de probabilidades.

Posteriormente, la editorial Nikoli lo exportó a Japón, publicándolo en el periódico Monthly Nikolist en abril de 1984 bajo el título Sūji wa dokushin ni kagiru (数字は独身に限る), que se puede traducir como ‘los números deben estar solos’ (独身 significa literalmente ‘soltero’). Kaji Maki (鍜治 真起), presidente de Nikoli, fue quien le puso el nombre. Posteriormente, el nombre se abrevió a sūdoku (数独; siendo sū: ‘número’ y doku: ‘solo’); ya que es práctica común en japonés tomar el primer kanji de palabras compuestas para abreviarlas.

En 1986, Nikoli introdujo dos innovaciones que garantizarían la popularidad del rompecabezas: el número de cifras que venían dadas estaría restringida a un máximo de 30 y sería «simétrico» (es decir, las celdas con cifras dadas estarían dispuestas de manera rotacionalmente simétrica). Esto no siempre se cumple en los sudokus actuales. En 1997 Wayne Gould preparó algunos sudokus para el diario The Times, que los publicó bastante más tarde, en diciembre de 2004. Tres días después, The Daily Mail publicó sus sudokus con el nombre Codenumber. En 2005 muchos otros periódicos de todo el mundo empezaron a incluir sudokus a diario en sus páginas.

En el año 2005, la ICPC (International Collegiate Programming Contest) incluyó entre sus 9 problemas el sudoku.

En el año 2005 también ve a la luz Los mejores sudokus (el primer libro sobre sudokus escrito por un español), con 200 sudokus agrupados en 4 niveles de dificultad, con una extensa descripción de la historia de este pasatiempo así como de sus reglas y un ejemplo paso a paso para su resolución. A este primero le siguieron 3 volúmenes más, así como un libro sobre kakuros, otro sobre cuadrados mágicos, y uno más sobre el cuboku.

Popularidad en los medios de comunicación

En 1997, el juez jubilado de Hong-Kong Wayne Gould, de 59 años de edad, un neozelandés, vio un rompecabezas parcialmente completado en una librería japonesa. Durante unos 6 años desarrolló un programa de ordenador para producir rompecabezas rápidamente. Sabiendo que los periódicos del Reino Unido tienen una larga tradición en cuanto a la publicación de crucigramas y otros rompecabezas, promovió el sudoku en The Times en Gran Bretaña, publicándolo el 12 de noviembre de 2004 (llamándolo Su Doku). Los rompecabezas de Pappocom, empresa de software de Gould, se han impreso diariamente en el Times desde entonces.

Un sudoku publicado en un periódico español.

Tres días más tarde, The Daily Mail comenzó a publicar el rompecabezas bajo el nombre de Codenumber. The Daily Telegraph introdujo su primer sudoku de Michael Mepham el 19 de enero de 2005 y otros periódicos del Telegraph Group lo incluyeron rápidamente.

Nationwide News Pty Ltd comenzó a publicar el rompecabezas en The Daily Telegraph de Sydney el 20 de mayo de 2005; se imprimieron cinco rompecabezas con soluciones ese día. La gran popularidad alcanzada por el sudoku en los periódicos británicos e internacionalmente ha hecho que lo apodaran en los medios de comunicación mundiales en 2005 «el rompecabezas con un crecimiento más rápido en el mundo».

¿Por qué es tan adictivo?

La escritora Carol Vorderman, en su libro Carol Vorderman’s how to do sudoku explica por qué ella y muchas otras personas disfrutan resolviendo sudokus.

Simplicidad de las reglas del juego

Esto lo hace fácil para los principiantes.

Por ejemplo, el sudoku no necesita aritmética mental, por lo que uno no tiene por qué ser bueno en matemáticas para lograr ser bueno resolviendo sudokus.

La satisfacción de completar un rompecabezas

Los rompecabezas sudoku son compulsivos, desafiantes y absorbentes.

Rápida mejora de las habilidades

Completando unos pocos rompecabezas de principiantes, uno puede mejorar sus habilidades resolviendo sudokus, y resolver más tarde rompecabezas más complejos.

Fácil de guardar y continuar

Se puede empezar un rompecabezas un día y continuarlo y acabarlo cualquier otro día.

Fácil de llevar consigo

Se puede recortar un sudoku de un periódico y afrontarlo en cualquier momento.

Reglas y terminología

El sudoku se presenta normalmente como una tabla de 9 × 9, compuesta por subtablas de 3 × 3 denominadas "regiones" (también se le llaman "cajas" o "bloques"). Algunas celdas ya contienen números, conocidos como "números dados" (o a veces "pistas"): El objetivo es rellenar las celdas vacías, con un número en cada una de ellas, de tal forma que cada columna, fila y región contenga los números 1–9 sólo una vez. Además, cada número de la solución aparece sólo una vez en cada una de las tres "direcciones", de ahí el "los números deben estar solos" que evoca el nombre del juego.

Métodos de resolución

La región 3 × 3 de la esquina superior izquierda debe contener un 7. Rastreando a lo largo y ancho los sietes localizados en cualquier lugar de la rejilla, el jugador puede eliminar todas las celdas vacías de la esquina superior izquierda que no pueden contener un 7. Esto deja sólo una celda posible (remarcada en verde).

La estrategia para resolver este rompecabezas se puede considerar como la combinación de tres procesos: escaneo, marcado y análisis.

Escaneo

El escaneo se realiza desde el principio y periódicamente, durante toda la resolución. El escaneo puede tener que ser ejecutado varias veces entre periodos de análisis. El escaneo consta de dos técnicas básicas: trama cruzada y recuento, que pueden usarse alternativamente.

• Trama cruzada Se trata del escaneo de filas (o columnas) para identificar qué línea en una región particular puede contener un número determinado mediante un proceso de eliminación. Este proceso se repite entonces con las columnas (o filas). Para obtener resultados más rápidos, los números son escaneados de forma ordenada, según su frecuencia de aparición. Es importante realizar este proceso sistemáticamente, comprobando todos los dígitos del 1 al 9.
• Recuento 1-9 por regiones, filas y columnas para identificar números perdidos. El recuento basado en el último número descubierto puede aumentar la velocidad.
• El primer escaneo debería consistir en revisar que columna, renglón o cuadrado de 3 × 3 cuenta con la mayor cantidad de números. Así si en un cuadrado de 3 × 3 existen 4 números y queremos ubicar otro al centro (por ejemplo), solo hacemos desde esa ubicación una revisión horizontal, vertical y tomando en cuenta los de ese mismo cuadrado de 3 × 3, para ver que números aparecen y no debo poner. Este proceso permite asegurar una menor cantidad de números candidatos a esa posición.

Marcado

El escaneo viene a interrumpirse cuando no pueden descubrirse nuevos números. En este punto es necesario centrarse en algún análisis lógico. La mayoría encuentra útil guiar este análisis mediante el marcado de números candidatos en las celdas vacías. Hay dos notaciones populares: subíndices y puntos.

En la notación de subíndice, los números candidatos se escriben en pequeño en las celdas. La desventaja es que los puzles originales se publican en periódicos que habitualmente no dejan demasiado espacio para acomodar más que unos pocos dígitos. Si se usa esta notación, los resolutores crean, a menudo, una copia más grande del puzzle y emplean un lápiz afilado.

La segunda notación es un patrón de puntos con un punto en la esquina superior izquierda representando un 1 y un punto en la esquina inferior derecha representando un 9. Esta notación tiene como ventaja que puede usarse en el puzle original. Se requiere destreza para el emplazamiento de los puntos, porque la existencia de puntos desplazados o marcas inadvertidas lleva, inevitablemente, a confusión y no son fáciles de borrar sin añadir más confusión.

Análisis

Hay dos aproximaciones principales:

• En eliminación, el progreso se realiza mediante la sucesiva eliminación de números candidatos para una o más celdas, hasta dejar sólo una elección. Después de lograr cada respuesta, debe realizarse un nuevo escaneo (habitualmente comprobando el efecto del último número). Hay una serie de tácticas de eliminación. Una de las más comunes es el "borrado del candidato no coincidente". Las celdas con idéntica configuración de números candidatos se dice que coinciden si la cantidad de números candidatos en cada una es igual al número de celdas que los contienen. Por ejemplo, se dice que celdas coinciden con una particular fila, columna o región si dos celdas contienen el mismo par de números candidatos (p, q) y no otros, o si tres celdas contienen el mismo triplete de números candidatos (p, q, r) y no otros. Estas son, esencialmente, contingencias coincidentes. Estos números (p, q, r) que aparecen como candidatos en cualquier lugar en la misma fila, columna o región en celdas no coincidentes, pueden ser borrados.
• En la aproximación "¿y si...?", se selecciona una celda con sólo dos números candidatos y se realiza una conjetura. Las etapas de arriba se repiten a menos que se encuentre una duplicación, en cuyo caso el candidato alternativo es la solución. En términos lógicos este método se conoce como reducción al absurdo. Nishio es una forma limitada de esta aproximación: para cada candidato para una celda, la cuestión que se plantea: ¿entrará un número particular de una configuración en otro emplazamiento? Si la respuesta es sí, entonces ese candidato puede ser eliminado. La aproximación "¿y si...?" requiere un lápiz y una goma. Esta aproximación puede ser desaprobada por puristas lógicos por demasiado ensayo y error pero puede llegar a soluciones clara y rápidamente.

Idealmente, se necesita encontrar una combinación de técnicas que eviten alguno de los inconvenientes de los elementos de arriba. El recuento de regiones, filas y columnas puede resultar aburrido. Escribir números candidatos en celdas vacías puede consumir demasiado tiempo. La aproximación "y-si" puede ser confusa a menos que se sea bien organizado. El quid de la cuestión es encontrar una técnica que minimice el recuento, el marcado y el borrado.

Resolución por ordenador

Para los programadores es relativamente sencillo construir una búsqueda por el método de backtracking o "vuelta atrás". Ésta asignaría, típicamente, un valor (supongamos que 1, o el más cercano a 1 disponible) a la primera celda disponible (supongamos que la superior izquierda) y entonces continuar asignando el siguiente valor disponible (supongamos que 2) a la siguiente celda disponible. Esto continuaría hasta que se descubriera una duplicación, en cuyo caso, el siguiente valor alternativo se colocaría en el primer campo alterado. En el caso de que ningún valor cumpliera la restricción se retrocedería hasta la casilla anterior y se probarían los siguientes números.

Aunque lejos de la eficiencia computacional, este método encontrará la solución si se permite el suficiente tiempo de computación. Un programa más eficiente podría dejar una huella de valores potenciales para las celdas, eliminando valores imposibles hasta que sólo un valor quedase para una celda determinada. Entonces se rellenaría esa celda y se usaría esa información para más eliminaciones y así, sucesivamente hasta el final. Esto emularía más exactamente lo que un resolutor humano haría sin el método de ensayo y error.

Codificar la búsqueda para imposibilidades basadas en contingencias e incluso múltiples contingencias (como sería requerido para los sudoku más difíciles) es bastante complejo de construir a mano. De cualquier modo, tales complicaciones son innecesarias si todo lo que el programador desea hacer es encontrar una solución eficientemente. Una forma más eficiente de construir soluciones involucra herramientas de programación más avanzadas.

Algunos programas así construidos, que emulan la resolución humana, permiten estimar la dificultad que tendrá un humano para encontrar la solución.

Implementación de un sudoku solver

Los resolvedores de sudokus que se implementarán seguidamente resolverán sudokus que serán codificados como "-" los caracteres a rellenar y como un número los prefijados, aquí se muestra un ejemplo de una entrada válida por el canal de entrada estándar del programa.

1 8: -: -:: -
- 6 7 2: 8:: -
-: 5: -: -: -

- 2: 1: -:: 7
-: 6 3: 9 5: -
- 9: 8 7 2: 4 -

-: 2 9:: 8: -
4: -:: 1:: 2
-: -: -: -: 5

En C++

Para la implementación del resolvedor de sudokus utilizaremos la clase vector (fácilmente transformable en un array clásico) y tres funciones:

• Una llamada inicial: simplemente se encarga de llamar a la función recursiva. Para darle más utilidad retornará un booleano que indicará si se ha encontrado alguna solución al sudoku.
• Una función recursiva: se encarga del proceso de ir probando números. Incluye un parámetro de entrada/salida que indica si se ha encontrado alguna solución.
• El comprobador de validez: simplemente es una función que retorna un booleano indicando si un valor puede estar en un sitio indicado.

El vector contendrá enteros codificando como "0" los lugares a rellenar (los "-") y como su propio valor numérico los valores preestablecidos. Al final de la implementación del resolvedor se propone una acción que lee un sudoku como el propuesto arriba y lo transforma en la matriz numérica.

Además, utilizaremos las siguientes definiciones y constantes:

const int FILS = 9; // Filas de un sudoku
const int COLS = 9; // Columnas de un sudoku

typedef vector< vector<int> > Matriz; // Definición de Matriz

Llamada inicial:

bool rellenar(Matriz& v) {
bool tr = false;
rellenar(v, 0, 0, tr); // V y TR són parámetros de E/S
return tr;
}

Función recursiva:

void rellenar(Matriz& v, int fil, int col, bool& tr) {
if (v[fil][col]==0) {
v[fil][col] = 1;
while (not tr and v[fil][col] <= 9) {
bool OK = correcto(v, fil, col);
if (OK) {
if (fil==8 and col==8) tr = true;
else if (col==8) rellenar(v, fil + 1, 0, tr);
else rellenar(v, fil, col + 1, tr);
}
if (not tr) ++v[fil][col];
}
if (v[fil][col] > 9) v[fil][col] = 0;
}
else {
if (fil==8 and col==8) tr = true;
else if (col==8) rellenar(v, fil + 1, 0, tr);
else rellenar(v, fil, col + 1, tr);
}
}

Comprobador de validez:

bool correcto(const Matriz& v, int fil, int col) {
for (int i = 0; i < FILS; ++i) {
if (i != fil and v[i][col]==v[fil][col]) return false;
if (i != col and v[fil][i]==v[fil][col]) return false;
}
int fila = 3*(fil/3); // No debe simplificar ya que no estamos trabajando con números reales
int columna = 3*(col/3); // Obtenemos el número entero de hacer x/3 (truncando)
// y posteriormente, multiplicamos por 3
for (int i = fila; i < fila + 3; ++i) {
for (int c = columna; c < columna + 3; ++c) {
if ((i != fil or c != col) and v[i][c]==v[fil][col]) return false;
}
}
return true;
}

Por si se tiene alguna duda, aquí se propone un método para leer un sudoku como el descrito arriba (caracteres de números y "-") y lo transforma en una matriz numérica de 0 (valores a introducir) y números (preestablecidos).

// Precondición: V es una Matriz de tamaño FILS x COLS
void leer(Matriz& v) {
char x;
for (int i = 0; i < FILS; ++i) {
for (int c = 0; c < COLS; ++c) {
cin >> x;
v[i][c] = x=='-' ? 0:x&0xF;
}
}
}

Niveles de dificultad

A menudo, los sudokus publicados se clasifican según su dificultad. Aunque resulta sorprendente, la cantidad de números dados apenas afecta a la dificultad del sudoku, e incluso puede no afectar en absoluto. Un sudoku con un mínimo de números dados puede ser muy fácil de resolver, y uno con más números de la media puede ser extremadamente complicado de resolver. Está basado en la relevancia y la posición de los números más que en la cantidad de éstos. Se ha demostrado que el problema de resolución de sudoku es un problema NP (problemas cuya solución puede ser verificada en tiempo polinomial). Hasta el momento no se conoce la existencia de ningún algoritmo que resuelva el problema en tiempo polinomial, lo que no significa que éste no exista.

Los programas informáticos que resuelven sudokus pueden estimar la dificultad que tiene un humano para encontrar la solución, basándose en la complejidad de las técnicas de resolución necesarias. Esta estimación permite a los editores adaptar sus sudokus para personas con diferente experiencia resolutoria. Algunas versiones "en línea" (online) también ofrecen varios niveles de dificultad.

Construcción

Es posible establecer sudokus con más de una solución y también realizar tableros iniciales de sudoku sin solución, pero no se consideran rompecabezas sudoku apropiados; como la mayor parte de los rompecabezas lógicos, se espera una solución única.

La construcción de un rompecabeza sudoku puede ser realizada a mano eficientemente predeterminando las posiciones de los números dados y asignándoles valores para realizar un proceso deductivo. Se piensa que los sudokus Number Place de Dell están generados por computador. Normalmente tienen más de 30 números dados dispersos aparentemente de manera aleatoria, algunos de los cuales pueden ser deducidos a partir de otros números dados. También tienen créditos sin autoría (es decir, el nombre del constructor no se imprime junto a ningún puzzle). Wei-Hwa Huang asegura que Dell le encargó escribir un programa generador Number Place en invierno del año 2000; antes de ello, le dijeron que los sudokus eran realizados a mano. El generador fue escrito con Visual C++, y aunque tenía opciones para generar más rompecabezas de estilo japonés, con restricciones simétricas y menos números, Dell optó por no usar esas funciones, al menos no hasta su reciente publicación de las revistas compuestas íntegramente por sudokus.

Los sudoku Nikoli se construyen a mano, y el nombre del autor aparece en los créditos junto a cada rompecabeza; los números dados siempre se encuentran en forma de un patrón simétrico. Los rompecabezas Number Place Challenger de Dell (véase Variantes más abajo) también citan los créditos del autor. Los rompecabezas sudoku que aparecen en la mayoría de los periódicos del Reino Unido aparentemente son generados por ordenador, pero emplean números dados simétricos. The Guardian licencia y publica rompecabezas sudoku construidos con Nikoli, aunque no incluye créditos de autoría. The Guardian declaró que ya que eran realizados a mano, sus rompecabezas contendrían "ocurrencias imperceptibles" que serían poco probables en sudokus generados por ordenador. El desafío para los programadores de sudokus es enseñar a un programa cómo construir rompecabezas inteligentes, de manera que no se puedan distinguir de aquellos realizados por humanos; Wayne Gould necesitó retocar su popular programa durante seis años para creer que había alcanzado ese nivel.

Variantes

Archivo:Nonominosudoku.JPG

Un sudoku nonomino

Aunque los sudokus de 9 × 9 con regiones de 3 × 3 son, por mucho, los más comunes, abundan numerosas variaciones. Por ejemplo, hay sudokus de tablas de 4 × 4 con regiones de 2 × 2; se han publicado bajo el nombre de Logi-5 tablas de 5 × 5 con regiones pentaminó; el World Puzzle Championship ha realizado previamente una tabla de 6 × 6 con regiones de 2 × 3 y una tabla de 7 × 7 con seis regiones heptomino y una región disjunta; Daily SuDoku ofrece sudokus de 4 × 4, 6 × 6, y 9 × 9 sencillos cada día bajo el nombre de Daily SuDoku for Kids [1]. Incluso el sudoku de 9 × 9 no es siempre estándar, y Ebb publica regularmente algunos de ellos con regiones nonomino; los U.S. Puzzle Championship de 2005 tenían un sudoku con regiones de paralelogramos dispuestas alrededor del borde externo del rompecabezas, como si la tabla fuese toroidal. También se pueden realizar sudokus más grandes, como el Monster SuDoku de 12 × 12 de Daily SuDoku [2], los Number Place Challenger de 16 × 16 que publica Dell regularmente y el desafiante Sudoku el Gigante behemoths de Nikoli de 25 × 25.

Otra variante común consiste en establecer restricciones adicionales para forzar la posición de los números más allá de los habituales requisitos en cuanto a fila, columna y región. A menudo, las restricciones toman la forma de una "dimensión" extra; la más común es que se cumpla el requisito de que los números de las diagonales principales también sean únicos. Los mencionados sudokus Number Place Challenger forman parte de esta variante, así como lo son los Sudoku X del Daily Mail, que utiliza rejillas de 6 × 6. El Daily Mail también publica el Super Sudoku X en su revista Weekend: una rejilla de 8 × 8 en la que las filas, columnas, diagonales principales, bloques de 2 × 4 y bloques de 4  ×  2 contienen cada número una sola vez. Otra variante consiste en emplear dígitos con la misma posición relativa dentro de sus respectivas regiones; dichos rompecabezas se imprimen a menudo en color, de forma que cada grupo disjunto comparte un color para mayor claridad.

Otras clases de restricciones extra pueden ser matemáticas, como requerir que los números en segmentos delineados de la rejilla tengan sumas específicas o productos (un ejemplo de lo anterior sería el Killer Su Doku en The Times). También son frecuentes los rompecabezas construidos a partir de múltiples sudokus. Las rejillas de 9 × 9 que se superponen en las regiones de las esquinas en forma de un quincuncio son concidas en Japón como sudoku Gattai 5 (mezcla de cinco), pero también reciben el nombre de Super Sudoku. En The Times y The Sydney Morning Herald a este tipo de sudokus les llaman Samurai SuDoku (‘sudoku samurái’ en español). En algunas publicaciones japonesas son comunes sudokus con 20 o más regiones que se superponen. A menudo, no se ofrecen números dados en las regiones solapadas. También se publican rejillas secuenciales, en contraposición a las solapadas, con valores en lugares específicos en las rejillas que necesitan ser transferidos a otras.

También han emergido variaciones alfabéticas, que utilizan letras en lugar de números. Por supuesto, no hay diferencia funcional en el rompecabezas salvo que las letras deletreen algo. Las variantes recientes inciden en esto, a menudo haciendo que aparezca una palabra en una de las diagonales principales una vez solucionado el sudoku; la determinación de la palabra se puede ver como una ayuda por adelantado para llegar a la solución. El Code Doku [3] ideado por Steve Schaefer tiene una oración entera encajada en el rompecabezas; el Super Wordoku [4] de Top Notch representa dos palabras de 9 letras, una en cada diagonal. Es discutible si éstos son verdaderos sudokus: aunque presumiblemente tienen una sola solución válida lingüísticamente, no tienen por qué tener que ser solucionados basándose únicamente en la lógica, necesitando que el que lo resuelva determine cuáles son las palabras incrustadas. Top Notch alega que ésta es una característica que se diseñó para derrotar a los programas de resolución de sudokus.

A continuación, algunas de las variaciones únicas más importantes:

• Un sudoku tridimensional fue inventado por Dion Church y publicado en el Daily Telegraph en mayo de 2005.
• El U.S. Puzzle Championship de 2005 incluye una variante denominada Digital Number Place: en lugar de números dados, la mayoría de las celdas contienen un número parcial—un segmento de un número, con los números escritos como si formaran parte de un display de siete segmentos.
• Wei-Hwa Huang creó un meta-sudoku, donde el objetivo es acabar dibujando los bordes de una región pentomino de una rejilla de 5 × 5 para dejar un rompecabezas único resoluble con regiones sin una forma idéntica.
• Cuboku, un invento de Agustín Fonseca, que parte de la frase «el sudoku es a los pasatiempos lo que un cubo de Rubik es a los rompecabezas».