trabalho

Universidade Tecnol´ ogica Federal do Paran´ a (UTFPR)
Departamento Acadˆ emico de Inform´ atica (DAINF)

Algoritmos II - 1 semestre de 2015
Professor: Rodrigo Minetto ([e-mail])

Trabalho Pr´ atico - T2
1

Objetivo

O objetivo desse trabalho pr´atico ´e aplicar os conceitos do Tipo Abstrato de Dados (TAD)
Pilha para a resolu¸c˜ao de um jogo conhecido como Sudoku.

2

Sudoku

Sudoku ´e um quebra-cabe¸ca baseado na coloca¸ca˜o l´ogica de n´ umeros. O objetivo do jogo ´e a coloca¸ca˜o de n´ umeros de 1 a 9 em cada uma das c´elulas vazias numa grade de 9 × 9, constitu´ıda por 3 × 3 subgrades chamadas regi˜oes. O quebra-cabe¸ca cont´em algumas pistas iniciais, que s˜ao n´ umeros inseridos em algumas c´elulas, de maneira a permitir uma indu¸ca˜o ou dedu¸ca˜o dos n´ umeros em c´elulas que estejam vazias. Cada coluna, linha e subgrade s´o pode ter UM n´ umero de cada um dos 1 a 9 (texto extra´ıdo do Wikip´edia).

3

Entrada

A entrada para o seu programa ser´a uma matriz de tamanho 9 × 9 (sempre com esse tamanho), onde os n´ umeros 0 (ZERO) s˜ao aqueles que o seu programa deve completar. A matriz abaixo ´e um poss´ıvel exemplo para o seu programa

1

0
3
8
1
2
9
4
5
0

0
0
9
0
8
0
1
0
3

0
7
0
0
4
0
0
9
8

3
4
2
0
1
0
6
8
5

9
1
5
4
0
8
3
7
2

7
8
0
0
0
0
9
4
1

2
6
0
8
0
4
0
1
0

1
0
7
2
9
6
8
0
0

0
9
0
0
0
1
7
2
0

Uma solu¸ca˜o para a matriz acima pode ser
6
3
8
1
2
9
4
5
7

4
2
9
7
8
5
1
6
3

5
7
1
6
4
3
2
9
8

3
4
2
9
1
7
6
8
5

9
1
5
4
6
8
3
7
2

7
8
6
5
3
2
9
4
1

2
6
3
8
7
4
5
1
9

1
5
7
2
9
6
8
3
4

8
9
4
3
5
1
7
2
6

Existem matrizes mais d´ıficeis de resolver, e seu programa deve tamb´em achar solu¸co˜es para elas, como por exemplo
0
4
0
0
0
9
0
0
3

0
0
2
0
5
0
7
0
0

0
0
0
3
4
0
0
0
6

4
0
0
0
0
0
0
5
0

3
0
0
4
0
5
0
0
2

0
6
0
0
0
0
0
0
9

6
0
0
0
9
7
0
0
0

0
0
4
0
1
0
6
0
0

5
0
0
8
0
0
0
1
0

6
8
1
5
9
7
2
3
4

7
9
4
2
1
3
6
8
5

5
2
3
8
6
4
9
1
7

cuja solu¸ca˜o ´e
1
4
6
7
8
9
5
2
3

9
3
2
6
5
1
7
4
8

8
5
7
3
4
2
1
9
6

4
7
8
9