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 \times n\$, la matriz será de tamaño \$n^2 \times n^2\$ con \$n^2\$ bloques. La variante más popular es la \$3^2 \times 3^2 = 9 \times 9\$ con 9 bloques de \$3 \times 3\$. El jugador debe encontrar los números que faltan en las celdas vacías, de tal forma que cumplan tres reglas lógicas:

Implemente un validador concurrente de Sudoku con Pthreads para saber si matrices existentes 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^2 \times n^2\$ de la entrada estándar. Dado que el tamaño \$n\$ es controlado por el usuario, su programa debe almacenar las matrices en memoria dinámica y no debe generar fugas de memoria.

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 número 0 (aunque en los ejemplos siguientes se usará un carácter punto '.' para facilitar la lectura). Todas las celdas se separan por espacios en blanco.

Ejemplo de entrada 1

Ejemplo de salida 1

Su programa debe determinar concurrentemente 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. Su solución debe crear tantos hilos como CPU disponibles se tengan en la computadora donde se ejecuta, y distribuir lo más equitativamente posible la validación de las tres reglas entre los hilos.

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 todos ellos, siguiendo el orden de evaluación de las tres reglas indicadas, y el orden de lectura izquierda-derecha y arriba-abajo. Este orden debe mantenerse pese a la naturaleza indeterministica de la concurrencia, y no debe limitar la eficiencia de su solución.

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^2 \times n^2\$ 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 una letra 'O' en lugar de un cero) 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, por ejemplo e2,5 indicaría un error en la fila 2 y columna 5. Si el tablero está completo pero consiste sólo de ceros, el veredicto sería valid, dado que conceptualmente cumple con las tres reglas de validez.

Ejemplo de entrada 2

Ejemplo de salida 2

Ejemplo de entrada 3

Ejemplo de salida 3

Cuando se tiene mucha hambre emergen dos tipos de personas: los pacientes y los impacientes. El paciente llega a su establecimiento de comida favorito y espera hasta ser atendido.

El impaciente llega también a su establecimiento de comida favorito, y si ve que la fila es corta, espera hasta ser atendido. En cambio, si la fila es larga, se impacientará y buscará otro lugar. Su impaciencia no acaba con cambiar de lugar. Si la fila ahí también está larga se desesperará de nuevo y buscará otro sitio. Así se comportará sucesivamente hasta encontrar un establecimiento donde considere que la fila es corta.

Si en su recorrido el impaciente encuentra todos los establecimientos de comida con filas largas, se resignará e irá al último lugar que vio con la fila más corta y se quedará a comer ahí, animándose con pensar que será el lugar en el que podrá comer más rápido. Por ejemplo, en la hora de almuerzo un impaciente podría recorrer las 6 sodas en la finca 1 de la UCR.

Cree una simulación concurrente que refleje este comportamiento. El hilo principal leerá de la entrada estándar la cantidad de establecimientos de comida, seguida por la capacidad de cada uno de ellos, como se muestra en el pseudocódigo siguiente. Cuando la capacidad de un establecimiento se agota, los clientes tendrán que hacer fila afuera hasta que alguien termine de comer y abandone el local.

Cada hilo secundario representa un comensal, el cual se identifica con un número secuencial (id) iniciando en 0. El comensal tratará primero de comer en su lugar preferido. Suponga que el establecimiento favorito del comensal id está dado por la relación id mod rest_count.

Asuma que el impaciente considera que la fila es larga cuando la cantidad de comensales que esperan es igual o mayor que la capacidad del local. En tal caso buscará el establecimiento vecino ubicado en la posición (id + 1) mod rest_count. Trasladarse no es inmediato, y le consume tiempo al impaciente, el cual está dado por la función walk() cuya duración se desconoce pero no es infinita.

Cuando el comensal decide por un establecimiento, hará la cola (si hay), y una vez que ingrese al establecimiento, comerá, lo cual consume un tiempo desconocido pero finito y dado por la función eat(). Cuando termine de comer, abandonará el local y dejará capacidad para un comensal más. Modifique el pseudocódigo dado para reflejar este comportamiento.

Validador de Sudoku

El hambriento impaciente