Sudoku Paralelo

O Sudoku é um popular quebra-cabeça de lógica e raciocínio que se baseia na colocação de números. O nome vem do japonês “Suuji wa dokushin ni kagiru”, que significa algo como “Os números devem ser únicos”.

O Sudoku é jogado em uma grade de N linhas e N colunas. O número N é um quadrado perfeito, de forma que ele também pode ser divido em regiões menores sqrt(N).

Tradicionalmente, o Sudoku possui 9x9 (9 linhas e 9 colunas), que é subdividida em nove regiões de 3x3.

O objetivo é preencher todas as células vazias com números de 1 a 9, de forma que, cada região, cada linha e cada coluna não possua números repetidos.

O desafio consiste em usar a lógica pura (sem precisar de matemática, apenas organização) para deduzir qual número se encaixa em cada célula vazia, eliminando as possibilidades de acordo com os números que já estão presentes nas respectivas linhas, colunas e blocos.

Veja no exemplo da tabela abaixo um Sudoku resolvido: todas as linhas contém apenas um número (de 1 a 9), assim como todas as colunas e todas as regiões. As diferentes regiões 3x3 estão destacadas em negrito, e também não possuem números repetidos.

Neste problema, você deve criar um programa que recebe um número N (9 <= N <= 6400) e um tabuleiro de Sudoku. Você deve então verificar se o tabuleiro está em uma configuração válida ou inválida.

Note que, a maioria dos Sudokus são pequenos… No entanto ele pode crescer muito e possuir 6400 linhas e 6400 colunas!!! Neste caso, você só vai conseguir resolver o problema se usar programação paralela para a análise!! Caso contrário, o corretor irá lhe atribuir Time Limit Exceeded.

Entrada

A primeira linha contém um número N, quadrado perfeito, indicando o tamanho do Sudoku a ser analisado. As próximas N linhas contém um Sudoku N x N para ser analisado

Saída

Após analisar o Sudoku, seu programa deve imprimir “Invalido” ou “Valido”

Restrições

Seu programa deve ser construído em OpenMP. * Não são admitidas construções usando #pragma omp for reduction() * Não são admitidas construções com o uso de pragmas de bloqueio como #pragma omp atomic ou #pragma omp critical * Uma matriz 6400 x 6400 não cabe na stack. Não utilize variáveis locais.

Exemplo de Entrada 1

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

Exemplo de Saída 1

Invalido

Exemplo de Entrada 2

6400
(...)

Exemplo de Saída 2

Valido

É esperado que, com o uso de paralelismo, seu programa consiga executar em menos de 4 segundos