EstruturadeDados Trabalho02

Prévia do material em texto

Estrutura de Dados - Trabalho 02
Data da entrega: 22/03/2017 - Em duplas
O jogo de Sudoku consiste em uma matriz 9x9 dividida em 9 sub-matrizes 3x3, como mostra a figura a seguir:
A matriz está parcialmente preenchida com números de 1 a 9 e o objetivo do jogo é completar a matriz, de forma com que cada linha, coluna e sub-matriz contenham os números de 1 a 9.
A partir destas informações, faça um programa utilizando os conceitos de matrizes e funções recursivas para resolver o jogo. 
Informações necessárias:
A matriz inicial contém zeros nas posições que devem ser preenchidas.
A matriz inicial é gerada aleatoriamente.
O programa deve imprimir a matriz solução do jogo.
O que deve ser entregue: 
Um arquivo fonte. O programa deve estar devidamente modularizado e comentado. Códigos mal feitos receberão pontuação menor do que códigos limpos e bem implementados.
Um texto de, no MÁXIMO, duas páginas explicando a lógica implementada para o computador solucionar o jogo.
Onde entregar:
Envie uma pasta compactada contendo todos os arquivos para o e-mail: jonas.mendonca@estacio.br
Assunto do e-mail: Estrutura de Dados - Trabalho 1
Não se esqueçam de colocar os nomes dos membros da equipe.
OBS 1: As notas serão disponibilizadas no site do professor para conferência.
OBS 2: O prazo NÃO será prorrogado.
Sudoku
Um sudoku “clássico” é um quadrado latino 9x9 com restrições adicionais: cada um dos nove quadrados 3x3 devem conter símbolos distintos, ou seja, um Sudoku é um quadrado latino 9x9 que contem 9 quadrados mágicos 3x3. Conforme visto acima temos:
5524751496156892842531225600 quadrados latinos; segundo Bertram Felgenhauer and Frazer Jarvis temos:
6670903752021072936960 grades de sudoku; As restrições adicionais reduziram da ordem de 10 elevado a 6!Uma redução da ordem de um milhão!
O programa abaixo verifica as restrições relacionadas ao arranjo 9x9 ser um quadrado latino:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE
int sudokuValido(int s[][9]){
  int i,j,k;
  int m,n;
  int digVisto[10];
  for(i=0; i<9; i++){
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[i][j]]){
         printf("Repete o digito %d na linha %d\n", s[i][j],i);
         return FALSE;
      }
      digVisto[s[i][j]]=TRUE;
    }
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[j][i]]){
      printf("Repete o digito %d na coluna %d\n", s[j][i],i);
      return FALSE;
      }
      digVisto[s[j][i]]=TRUE;
    }
  }
  return TRUE;
}
int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
  if(sudokuValido(s))
    printf("sudoku ok!\n");
  system("PAUSE"); 
  return 0;
}
Complete o programa acima para verificar se os nove quadrados 3x3 contêm digitos distintos, completando assim a verificação da validade do sudoku. Se depois de insistir (não clique agora!) não conseguir uma boa solução veja esta sugestão.
O programa abaixo mostra uma outra maneira de verificar a unicidade dos elementos das linhas e colunas:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE
int sudokuValido(int s[][9]){
  int i,j,k,v;
  int m,n;
  for(i=0; i<9; i++){
    for(j=0; j<9; j++){
      v=s[i][j];
      for(k=j+1; k<9; k++)
        if(v==s[i][k]){
           printf("Repete o digito %d na linha %d\n", s[i][j],i);
           return FALSE;
        }
    }
    for(j=0; j<9; j++){
      v=s[j][i];
      for(k=j+1; k<9; k++)
        if(v==s[k][i]){
        printf("Repete o digito %d na coluna %d\n", s[j][i],i);
        return FALSE;
        }
    }
  }
  return TRUE;
}
int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
  if(sudokuValido(s))
    printf("sudoku ok!\n");
  system("PAUSE"); 
  return 0;
}
Quantas matrizes 3x3 envolvendo os valores de 1 a 9 podem ser construídas? A geração de sudokus a partir da geração de matrizes de quadrados latinos utilizando a geração elemento a elemento é inviável. Teriamos que gerar  da ordem de 10 elevado a 77 matrizes. A geração de sudokus a partir de quadrados latinos com geração linha a linha, também é inviável, envolve a geração de 9 elevado a 9!= 362880 matrizes, ou seja “apenas” da ordem de 10 elevado a 50.