Sudoku

Piste verte Le 22 novembre 2008  - Ecrit par  François Sauvageot
Le 18 mai 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Sudoku Voir les commentaires
Lire l'article en  

El juego es un reflejo de la actividad humana, el el sentido que escenifica una situación y permite por lo tanto zambullirse en ella, vivirla concretamente y, si se desea, reflexionar sobre ella. El matemático se interesa en el juego principalmente porque es un buen vector, un medio para hacer comprender las matemáticas y también fenómenos de la sociedad contemporánea a personas a priori reticentes o ajenas a esta visión.

En 1783, un matemático suizo, Leonhard Euler, planteó el problema de los oficiales : ¿cómo colocar en un cuadrado 6 oficiales de 6 regimientos diferentes, de modo que en cada línea y cada columna haya sólo un representante de cada regimiento y de cada grado ?

Este problema despertó el interés de matemáticos e informáticos por el ancestro del Sudoku, el cuadrado latino. Fue un arquitecto jubilado de 74 años, Howard Garn, quien creó el puzzle -al que llamó Number Place- para la revista estadounidense Dell Magazine. El juego se popularizó en Japón en los años 80 -cinco años después de la muerte de Garn- en la revista Monthly Nikolist bajo el nombre de ’’Suuji Wa Dokushin Ni Kagiru’’ (los números deben ser únicos), y el juego se hizo popular. Kaji Maki, presidente de Nikoli, abrevió el nombre a Sudoku (número único) y lo patentó. Como el juego era popular, los competidores mantuvieron el nombre original Nanpure (número colocado). Todavía ahora las revistas japonesas le llaman Number place, mientras que en Estados Unidos y en otras partes se habla de Sudoku.

Los juegos de letras, así como las palabras cruzadas, tienen mucho menos participantes en Japón. Fue en 2004 cuando el entusiasmo por el Sudoku fue total en ese país. Este fervor se extendió rápidamente al Reino Unido a través de los diarios locales. Si hay explicaciones para este fenómeno, tal vez provengan de los siguientes comentarios.

Es necesario comprender que el Sudoku no es un puzzle aritmético. Se podría sustituir los números por cualquier cosa, pero lo que mejor funciona probablemente son los números, ya que la colección de referencia más común para nueve cosas es tal vez la lista de los nueve primeros números. El número tiene algo de universal : Pitágoras (matemático, filósofo y astrónomo griego del siglo VI A.C.) decía ’’Todo es número’’. Además, todo el mundo sabe los números del 1 al 10. Las grillas 16x16, con pequeños cuadrados 4x4, claramente tienen menos éxito.

El Sudoku es un derivado de los cuadrados latinos, problema que consiste en rellenar un cuadrado de tamaño arbitrario utilizando los mismos símbolos sobre cada línea, pero de manera que ninguno aparezca dos veces en una misma columna. Es como un Sudoku, salvo que la condición sobre los cuadrados pequeños no está presente. Los cuadrados latinos tienen un interés matemático. En efecto, corresponden a tablas de multiplicación un poco especiales. Aquí hay un ejemplo.

Tomemos los números de 1 a 4 y escribamos la tabla de multiplicación como se hace (según Pitágoras) en la escuela :

1234
2468
36912
481216

Tomemos ahora el residuo de la división por 5 en todas las casillas. Por ejemplo, para 12 se tiene ’’12 dividido por 5 igual a 2 y quedan 2’’, es decir, 12=2x5+2, y escribimos 2 en el lugar del 12. Aquí está el resultado :

1234
2413
3142
4321

¡Es un cuadrado latino ! ¿Mágico ? En absoluto. Acabamos de escribir la tabla de multiplicación del grupo cíclico con 4 elementos.

Uno puede hacer los Sudoku con grillas elementales rectangulares de tamaño arbitrario. Por ejemplo, se puede colocar los números de 1 a 6 en un rectángulo 2x3 y tratar de llenar una grilla formada por seis rectángulos, con las reglas usuales del Sudoku. Estos Sudoku con seis números son más accesibles que los de nueve números.

Los más grandes, como los 16x16, son en cambio a menudo más difíciles. En realidad, la complejidad de los Sudoku puede ser estudiada desde un punto de vista algorítmico, y ahí se llega a la informática y a la lógica.
Simbólicamente, llenar un Sudoku es como pasear por una carretera con cruces tipo rotonda (se abren varios caminos) y avanzar cuando se puede (esto es, cuando se puede colocar un número sin infringir una de las reglas) o regresar hasta el cruce anterior cuando el camino está bloqueado. Llenar un Sudoku de este modo es, por lo tanto, exclusivamente un ejercicio de lógica (¡y de tenacidad !).

Sin embargo, cuando se estudia los Sudoku de tamaño arbitrario, el ejercicio se vuelve cada vez más complejo a medida que el tamaño aumenta. En realidad, resolver un Sudoku de tamaño arbitrario es tan difícil como encontrar un algoritmo para romper la seguridad de los protocolos de criptografía utlizados en Internet o en las tarjetas con chip. Se habla de problema NP-completo.

Usted puede consultar tambien el artículo de Wikipedia.

Article original édité par François Sauvageot

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Sudoku» — Images des Mathématiques, CNRS, 2019

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?