Instituto de Computação - UNICAMP

MC504 - Sistemas Operacionais

Primeiro Semestre de 2014

Islene Calciolari Garcia

Projeto 1: Sudoku Multithread

Sobre o Sudoku

O Sudoku é um quebra-cabeça japonês bastante popular. Em sua versão mais tradicional, o objetivo é o preenchimento de um diagrama 9x9 obedecendo as seguintes restrições:

As linhas devem conter números de 1 a 9 sem repetições.
As colunas devem conter números de 1 a 9 sem repetições.
O diagrama é dividido em 9 regiões 3x3 e estas também devem conter números de 1 a 9 sem repetições.

Se você ainda não jogou, tente um site como websudoku ou sudoku.net.br.

Objetivos

Cada grupo deverá escrever um programa em C que preencha um diagrama Sudoku, utilizando uma estratégia multithread. Vocês deverão também escrever um código multithread que avalia se um diagrama preenchido está obedecendo corretamente as restrições e também um módulo para dicas, que será explicado abaixo.

Verificação

Escreva um programa que leia um diagrama completo 9x9 e indica se ele respeita ou não as restrições do Sudoku. Caso o diagrama não esteja correto, o programa deve reportar pelo menos um erro. Por exemplo:

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

A linha 3 contém duas ocorrências do número 9.

Modo dica

Seu programa lê um diagrama Sudoku e avisa o usuário quais são as possibilidades para ele preencher. Veja o formato de entrada:

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

E o formato das dicas:

(278)  6       1      (38)  (478)  (347) (2458)  9    (4578)
 4     3      (278)   (8)    9      5    (128)   6    (78)
 9    (57)    (578)    1    (4678)  2    (458)  (578)  3
(278) (27)    (2378)   4    (5678)  1    (2568) (2358) 9
 5    (24)     9      (368) (68)   (36)   7     (238)  1
 6    (147)   (3478)   2    (578)   9    (458)  (358) (458)
 3    (12457) (2457)   9    (1245)  8    (5)    (57)   6
(1)    8      (56)     7     3     (6)   (59)    4     2
(27)   9      (24567) (56)  (2456) (46)   3      1    (578)

Os números entre parênteses indicam quais valores podem ser colocados em cada posição, de acordo com os números já marcados no diagrama. Por exemplo, a posição na linha 1 e coluna 1 pode ser preenchida com os números 2, 7 ou 8. A posição da linha 8 e coluna 1 pode receber apenas o número 1.

A sua saída deve conter todos os números separados por linhas, mas não precisa estar alinhada como no exemplo.

Completando o diagrama

Após a leitura de um arquivo como descrito acima, um diagrama preenhcido deve ser mostrado como abaixo.

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

Forma de entrega

Seu grupo deve criar um repositório no github ou no bitbucket. O seu projeto deverá conter:

Arquivo Makefile
Módulo para verificação de diagramas completos (com instruções de uso)
Módulo para a exibição de dicas (com instruções de uso)
Módulo para a exibição da solução completa (com instruções de uso)
Texto explicativo da estratégia multithread adotada, bem como uma análise de seus pontos fortes e fracos. Por exemplo, a estratégia adotada tem alto custo, mas consegue avaliar se um diagrama tem solução única ou não.

Data de entrega

O projeto deverá ser entregue até o dia 16 de março. Deverá ser enviado um email para islene at ic dot unicamp dot br com o endereço do repositório com o conteúdo descrito acima.

Dicas

Compile seu programa com:

gcc -g -pthread

E utilize o gdb para depurar.

Veja um exemplo de estrutura de código e arquivo Makefile no diretório exemplo. É só um exemplo. Seu có não precisa seguir esta estrutura.