Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/11/13
003// 
004// Passeio do Cavalo: encontrar um passeio em tabuleiro de xadrez para
005// um cavalo de modo a visitar todas as casas uma unica vez.
006// 
007// Descricao: definir o tamanho da tabuleiro n; definir uma posicao inicial de (0,0) ate (n-1,n-1);
008// por tentativa e erro (backtracking) testar, todas as possibilidades (em busca em profundidade).
009// 
010// Inicia em (x,y) e faz Tenta(Tab, n, lin, col, 1)
011// int Tenta(Tab, n, lin, col, conta)
012//   if (conta==n*n) return 1; // conseguiu fazer n*n passos do cavalo => cobriu o tab. todo => sucesso!
013//   for "para cada movimento Mx, My (0 a 7)"
014//     if "Tab[Mx][My] movimento possivel"
015//       "registra movimento Tab[lin+Mx][col+My] <- conta"
016//       if (Tenta(Tab, n, lin+Mx, col+My, conta++)) // se devolver 1 => obteve sucesso!
017//          return 1; // "devolva sucesso"
018//       else "desmarcar movimento Tab[Mx][My] <- 0"
019//   return 0; // "devolva fracasso"
020
021// Fixando (0,0) para iniciar, primeiro tabuleiro factivel e' o 5x5
022
023// gcc -fsanitize=address -g -o passeio_cavalo passeio_cavalo.c
024
025#include <stdio.h>
026#include <stdlib.h> // 'atoi(...)' - string para inteiro
027
028// Movimentos do cavalo numerados de 0 ate 7
029//     0+1
030//   7  |  2
031//   +--+--+
032//   6  |  3
033//     5+4
034signed char M[][2] = { // movimentos considerando uma matriz desde (0,0) ate' (n-1,n-1)
035  -2, -1,  // 0 x <- x-1 e y <- y-2  
036  -2,  1,  // 1  
037  -1,  2,  // 2  
038   1,  2,  // 3   
039   2,  1,  // 4   
040   2, -1,  // 5   
041   1, -2,  // 6   
042  -1, -2   // 7  
043  };  
044
045long numeroTentativas = 0; // contabiliza numero de tentativas
046
047// Inicia tabuleiro. Usar 'unsigned char' para inteiros entre 0 e 256. Primeira posicao sera 1.
048void iniciaTabuleiro (unsigned char *Tab, int n) {
049  int i, j;
050  for (i=0; i<n; i++)
051    for (j=0; j<n; j++)
052      *(Tab + i*n +j) = 0; // Tab[i][j] = 0;      
053  }  
054
055void imprimeTabuleiro (unsigned char *Tab, int n) {
056  int i, j;
057  printf("Veja a configuracao do passeio no tabuleiro de dimensao %d\n     ", n);
058  for (i=0; i<n; i++)
059    printf("+----");
060  printf("+\n");
061  for (i=0; i<n; i++) {
062    printf("     |");
063    for (j=0; j<n; j++)
064      printf("%4d|", *(Tab + i*n +j));
065    printf("\n     ");
066    for (j=0; j<n; j++)
067      printf("+----");
068    printf("+\n");
069    }    
070  }  
071
072int movimentoPossivel (unsigned char *Tab, int n, int lin, int col) { // movimento e' valido?
073  if (lin<0 || lin>=n) return 0; // fora do tabuleiro
074  if (col<0 || col>=n) return 0; // fora do tabuleiro
075  if (*(Tab + lin*n + col)>0) return 0; // posicao ja ocupada
076  return 1;  
077  }  
078
079int tentarEncontrarPasseio (unsigned char *Tab, int n, int lin, int col, int conta) {
080  int i, mx, my;
081  //D1 printf("\nconta=%d: (%d,%d)", conta-1, lin, col); // ultimo colocado na posicao (lin,col)  
082  if (conta>n*n) { // ja' alocou todos os passeios => sucesso!
083    return 1;    
084    }    
085  for (i=0; i<8; i++) {
086    mx = lin+M[i][0];    
087    my = col+M[i][1];    
088    if (movimentoPossivel(Tab, n, mx, my)) { // registre o movimento "conta" na pos. (mx,my)
089      *(Tab + mx*n + my) = conta;      
090      numeroTentativas++;      
091      if (tentarEncontrarPasseio(Tab, n, mx, my, conta+1)) { // tenta completar o passeio
092        return 1;        
093        }        
094      else { // nao foi possivel completar o passeio a partir de "Tab[mx][my]==conta" => desfaz      
095        //D1 printf("\n i=%d : desfaz (%d,%d)=%d", i, mx, my, *(Tab + mx*n + my));         
096        *(Tab + mx*n + my) = 0; // libere posicao        
097        }        
098      } // if movimento valido      
099    } // for i    
100  return 0; // fracasso => MAO conseguiu da posicao atual um movimento completo  
101  }  
102
103int main (int argc, char *argv[]) {
104  unsigned char *Tab;   // tabuleiro - usar alocacao dinamica para nao precisar recompilar  
105  int lin, col, n, sucesso, i, j;
106  if (argc!=4 && argc!=2) {
107    printf("Testa passeio do cavalo. Duas opcoes, supondo desejar rodar com tabuleiro 8x8:\n");
108    printf(" - Para rodar tentando a partir de qualquer posicao:\n   ./passeio_cavalo 8\n");
109    printf(" - Para rodar iniciando na posicao (0,0), digitar:\n   ./passeio_cavalo 8 0 0\n");
110    return 1;    
111    }    
112  n = atoi(argv[1]);  
113
114  Tab = malloc(n * n * sizeof(unsigned char));  
115
116  iniciaTabuleiro(Tab, n);
117
118  sucesso = 0;
119  if (argc==2) { // Opcao 1: testar iniciando em todas os posicoes do tabuleiro
120    for (i=0; i<n; i++) {
121      if (sucesso) break;
122      for (j=0; j<n; j++) {
123        lin = i; col = j;        
124        *(Tab + lin*n + col) = 1; // posicao inicial        
125        if (tentarEncontrarPasseio(Tab, n, lin, col, 2)) {
126          printf("\n\n*** Passeio encontrado iniciando em (%d,%d)!", lin, col);
127          printf(" Apos tentar %ld vezes\n", numeroTentativas);
128          sucesso = 1; break;
129          }          
130        else {        
131          printf("Nao existe passeio iniciando na posicao (%d,%d)", lin, col);
132          printf(": tentei %8ld vezes!\n", numeroTentativas);
133          }          
134        }        
135      }      
136    } // if (argc==2)    
137  else { // Opcao 2: testar iniciando na posicao fornecida via linha de comando  
138    lin = atoi(argv[2]);    
139    col = atoi(argv[3]);    
140    printf("Tabuleiro de dimensao %d, cavalo iniciando em (%d,%d)\n", n, lin, col);
141    *(Tab + lin*n + col) = 1; // posicao inicial    
142    sucesso = tentarEncontrarPasseio(Tab, n, lin, col, 2);
143    } // else if (argc==2)    
144
145  if (sucesso) {
146    printf("\n*** Passeio encontrado iniciando-se em (%d,%d)! ", lin, col);
147    printf("Foram feitas %ld tentativas\n", numeroTentativas);
148    imprimeTabuleiro(Tab, n);
149    }    
150  else  
151  if (argc==4) { // Opcao 2: testar iniciando na posicao fornecida via linha de comando
152    printf("\nNao existe passeio iniciando na posicao (%d,%d)", lin, col);
153    printf("\nTentei %ld vezes!\n", numeroTentativas);
154    }    
155  printf("\n");
156
157  free(Tab);
158
159  return 0;  
160  }