Apareció como un pasatiempo en medios de comunicación de Francia a finales del siglo 19 pero desapareció con la primera guerra mundial. Su forma moderna la obtuvo en Indiana, Estados Unidos, en 1979 como un pasatiempo publicado por el arquitecto jubilado Howard Garns con el nombre Number Place. En 1984 llegó a Japón, donde adquirió el nombre de Sudoku. En el 2004 alcanzó la revista británica The Times, de donde se popularizó hasta adquirir las dimensiones de un fenómeno mundial.

El Sudoku consiste en una matriz parcialmente llena de números enteros, como la ilustrada a la derecha. Las formas más populares del juego usan matrices cuadradas divididas en bloques (o regiones). Si cada bloque es de tamaño n × n, la matriz será de tamaño n² × n² con n² bloques. La variante más popular es la 3² × 3² = 9 × 9 con 9 bloques de 3 × 3. El jugador debe encontrar los números que faltan en las celdas vacías, de tal forma que cumplan tres reglas lógicas:

1. Cada fila debe tener los números de 1 a n² sin que se repitan.
2. Cada columna debe tener los números de 1 a n² sin que se repitan.
3. Cada bloque o región debe tener los números de 1 a n² sin que se repitan.

Implemente un validador de Sudoku para saber si juegos digitalizados de las primeras revistas tienen errores, o para ayudar a personas a crear nuevos retos de este juego, o para ayudar a programas interactivos a resaltar errores del jugador. Su programa debe leer tableros cuadrados de Sudoku de tamaño n² × n² de la entrada estándar. La entrada consistirá del valor de n en la primera línea, seguido del tablero. Los tableros podrían estar parcialmente llenos, donde las celdas llenas se indican con el número que contienen y las vacías con el carácter punto ('.'). Todas las celdas se separan por espacios en blanco.

Ejemplo de entrada 1

3

8 . .   . . .   . . .
. . 3   6 . .   . . .
. 7 .   . 9 .   2 . .

. 5 .   . . 7   . . .
. . .   . 4 5   7 . .
. . .   7 . .   . 3 .

. . 1   . . .   . 6 8
. . 8   5 . .   . 1 .
. 9 .   . . .   4 . .

Ejemplo de salida 1

b6,4

Su programa debe determinar si el tablero de Sudoku leído de la entrada estándar es válido o no. Un tablero es válido si cumple las tres reglas lógicas del juego, y en tal caso se debe imprimir el texto valid en la salida estándar. Si el tablero no es válido se debe imprimir las coordenadas de cada celda donde se detecta un valor reiterado. Anteceda las coordenadas por una de las letras: 'r' para fila, 'c' para columna, ó 'b' para bloque, correspondiente a la regla que el número reiterado infringe.

La salida en el ejemplo 1 indica que el valor de la celda en la fila 6 y columna 4 genera un bloque (b) inválido. En caso de que hayan múltiples errores en un tablero, se deben reportar todas ellos, siguiendo el orden de evaluación de las tres reglas indicadas, y el orden de lectura izquierda-derecha y arriba-abajo.

Importante: Un tablero de Sudoku válido (parcialmente lleno) no es necesariamente resoluble. Su programa sólo debe validar que las celdas llenas cumplan con las tres reglas anteriores, indiferentemente de si el tablero es resoluble o no.

Los tableros de Sudoku en la entrada deben constar de n² × n² números o puntos. Sin embargo, por errores de digitación o de reconocimiento de caracteres a partir de documentos históricos, podrían aparecer caracteres no esperados (por ejemplo un '0' en lugar de un '8') o tableros incompletos. En tal caso, se debe imprimir la celda donde se detecta el error usando la notación anterior precedida por la letra e. Si el tablero está completo pero consiste sólo de puntos, se debe imprimir valid, dado que conceptualmente cumple con las tres reglas de validez.

Ejemplo de entrada 2

2

1 2  3 4
3 4  1 2

2 1  2 3
4 3  4 1

Ejemplo de salida 2

r3,3
r4,3

Evaluación:

En cada ejercicio se evaluará la completitud, correctitud, y buenas prácticas de programación (programación defensiva, identificadores significativos, indentación, convenciones de estilo). Dispone de 3 horas para elaborar su solución, de forma estrictamente individual. No utilice dispositivos de comunicación durante el examen. Puede consultar cualquier material impreso, pero no compartirlo. Al finalizar, recuerde firmar la hoja de asistencia y fotografiar su solución si va a realizar el ejercicio opcional.

1. [40%] Diseña una solución usando sólo los ocho tipos de instrucciones. Divide el problema en subtareas. Solicite el código de confirmación cuando haya finalizado el diseño y antes de iniciar la implementación.
2. [40%] Implementa una solución correcta y completa
3. [20%] Rastrea la memoria de su programa con el ejemplo 2 hasta imprimir el primer error en la salida estándar.
4. [10% opcional] Transcribe algoritmo y código, y lo corrige en juez automático.

Ejemplo de entrada 3

4

 . 16  . 10    11  .  .  4     .  .  .  .     . 12  3  .
 .  . 14  .     .  .  .  .     .  5  .  .     .  .  6  .
 2 15  .  .     .  5  3  1     .  .  .  .    .  11  8  .
13  .  5  .    10  .  .  .     .  .  . 15    16  .  .  .

 9 12  6  .     1  .  5  .     .  . 10 16     .  .  .  .
 7  .  .  .     .  .  .  .     .  4  .  .     .  .  .  .
 1  .  .  .    12 10  .  .     .  . 11  5     . 16 13  8
 .  5 10  8     .  . 13 15     .  1  .  7     9 14  .  .

 .  .  .  .     2  . 16  .     .  .  .  4     1  .  . 14
 . 14  .  6     .  . 12  .     2  .  .  3     .  .  .  .
 .  .  . 11     .  .  .  5    10  .  .  .     .  8  .  2
12  3  .  1     .  .  .  6     . 13 14  .    15 10 16  .

 .  . 16  .     .  . 10  .     . 11  7  .     . 13  1  4
 .  .  .  .     . 16  .  .     .  8  .  9    11  .  .  .
 .  .  7  .    15 13  . 11     .  .  .  6     8  3  2  .
 . 10 15  .     .  1  .  .     3 16  .  .     .  .  .  .

Ejemplo de salida 3

valid