Problema das 8 rainhas

Aprender a programar bem é tão importante quanto aprender tecnologias atuais. O leitor poderá estar pensando assim:  mas será que esta história de algoritmos eficientes tem relevância, numa era de computadores cada vez mais velozes? Considere o seguinte exemplo, o popular problema da oitos rainhas, que deseja determinar uma maneira de colocar oitos rainhas em tabuleiro de xadrez de maneira que nenhuma rainha ataque as outras rainhas do tabuleiro. Uma abordagem ingênua examinaria 64!/56! = 178,462,987,637,760 possíveis maneiras de colocar 8 peças nos 64 casas do tabuleiro, e, para cada configuração, checar se nenhuma rainha ataca qualquer outra. Mas podemos restringir ainda mais o espaço de busca considerando apenas como soluções as permutações dos números de 1 até 8 como uma solução para o problema. Note que agora precisamos gerar 8! = 40320 configurações e testar se as rainhas de cada coluna colocadas na linhas dada pela permutação atacam uma as outras.

Essa configuração equivale a permutação [4,2,7,3,6,8,5,1]

  É claro que este algoritmo funciona para tabuleiros de tamanho moderado e poderia ser usado por nós para resolver este problema. Mas o que ocorre com tabuleiros maiores? Vejamos, por exemplo, uma situação em que o tamanho do tabuleiro cresce para 50. Neste caso, o computador deveria examinar 50! permutações potenciais. Tentemos estimar a magnitude deste número.  A forma mais simples é usar a fórmula de Stirling, que fornece a estimativa n! $\equiv \sqrt{2\pi n}(\frac{n}{e})^n$ . Mas, neste caso, podemos usar estimativas mais elementares.  Por exemplo, podemos usar apenas potências de 2. Temos:

50! =    1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × ... × 15 × 16 × ... × 31 × 32 × … × 49  x 50 >

            1 × 2 × 2 × 4 × 4 × 4 × 4 × 8 × ... ×   8 × 16 × ... × 16 × 32 × …× 32  x 32 = 

            2² x 4⁴ x 8⁸ x 16¹⁶ x 32¹⁹  =  2^2+8+64+95 = 2¹⁶⁹ =(2¹⁰)^16,9. 

Mas 2¹⁰ = 1024 >10³.  Logo 50! > (10³)^16,9=10^50,7.

Ora, um computador moderno pode realizar cerca de 1 bilhão de  operações por segundo. Se em cada operação ele conseguir testar um circuito, ele ainda assim precisará de mais de 10^50,7 / 1. 10⁹ = 5 × 10⁴¹ segundos, o que corresponde a aproximadamente a 1,58 × 10³⁴ anos.  Assim, trata-se claramente de uma missão impossível para o algoritmo de força bruta baseado na análise de cada permutação.

Backtracking

Os computadores modernos podem utilizar força bruta para resolver problemas de maneira efetiva. Em geral, precisamos desenvolver algoritmos para busca exaustiva em todas as permutações e/ou em todos os subconjuntos possíveis. Vamos aprender algoritmos com retrocesso (backtracking) e desenvolver cortes para tornar estes algoritmos mais poderosos.

Como gerar todas as permutações?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int marc[4];//vetor marc[x] = 1 se o elemento esta na permutação
int v[4]; //vetor original
int p[4]; //vetor da permutação
int i;
int n=3;
 
int permute(int i){
 int j;
 
 if(i<=n){ //escolhendo o i-ésimo elemento 
  for(j=1;j<=n;j++){
   if(marc[j]==0){ //se um element não foi escolhido
    marc[j]=1; // este elemento é marcado
    p[i]=j;    // o i-ésimo elemento da permutação corresponde
      // ao j-ésimo elemento do vetor  
    permute(i+1); //escolhe-se o próximo elemento
    marc[j]=0;
   }
  }
 }else{ //Imprime a permutação escolhida
  printf("%d",v[p[1]]);
  for(j=2;j<=n;j++){
   printf(" %d",v[p[j]]);
  }
  printf("\n");
 }
}

int main(){
 int i;
 memset(marc,0,sizeof(marc));
 for(i=1;i<=n;i++) v[i]=i;
 permute(1);
  system("PAUSE");
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
using namespace std;

int main(){
  int v[] = {1,2,3}; 
 
  //sort(inicio,fim) 
  sort (v,v+3); //ordena o vetor 

  do {
    cout << v[0] << " " << v[1] << " " << v[2] << endl;
  } while ( next_permutation (v,v+3) ); // gera a próxima permutação
  
  system("PAUSE");

}

Saída

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Pressione qualquer tecla para continuar. . .

Desafio SPOJ

http://br.spoj.pl/problems/TENTA/

CORTANDO

No problema das oitos rainhas, reduzimos bastante nosso espaço de busca limitando-se a pesquisar apenas as permutações de [1,..,n]. Mas podemos desistir de uma permutação se a permutação tem duas rainhas que se atacam. Então podemos descobrir prematuramente quando uma permutação não é mais válida.

Em tabuleiro 8x8, temos 8 linhas , 15  diagonais principais e 15 diagonais secundárias. As diagonais principais são formadas pelos elementos (i,j) com 2≤i+j≤16 ou 0≤i+j-2≤14. As diagonais secundárias são formadas pelos elementos (i,j) com -7≤i-j≤7 ou 0≤i-j+7≤14.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int linha[9];
int coluna[9];
int d1[15];
int d2[15];
int cont;

void queen(int i){
 int j;
 
 if(i<=8){
  //escolhendo onde colocar a i-ésima rainha
  for(j=1;j<=8;j++){
   //nao tem nenhuma outra rainha na mesma linha ou diagonal
   if(linha[j]==0 && d1[i+j-2]==0 && d2[i-j+7]==0){
    coluna[i] = j;
    linha[j]=i;
    d1[i+j-2]=1;
    d2[i-j+7]=1;
    queen(i+1);
    linha[j]=0;
    coluna[i] = 0;
    d1[i+j-2]=0;
    d2[i-j+7]=0;
   }
  }
 }else{
  cont++;
  printf("%d. ",cont);
  printf("%d",coluna[1]);
  for(j=2;j<=8;j++){
   printf(" %d",coluna[j]);
  }
  printf("\n");
 }


}

int main(){
 memset(linha,0,sizeof(linha));
 memset(d1,0,sizeof(d1));
 memset(d2,0,sizeof(d2));
 cont = 0;
 queen(1);
  system("PAUSE");
}

O programa foi capaz de gerar todas 92 possibilidades de colocar 8 rainhas em tabuleiro 8x8;

1. 1 5 8 6 3 7 2 4
2. 1 6 8 3 7 4 2 5
3. 1 7 4 6 8 2 5 3
4. 1 7 5 8 2 4 6 3
5. 2 4 6 8 3 1 7 5
6. 2 5 7 1 3 8 6 4
7. 2 5 7 4 1 8 6 3
8. 2 6 1 7 4 8 3 5
9. 2 6 8 3 1 4 7 5
10. 2 7 3 6 8 5 1 4
11. 2 7 5 8 1 4 6 3
12. 2 8 6 1 3 5 7 4
13. 3 1 7 5 8 2 4 6
14. 3 5 2 8 1 7 4 6
15. 3 5 2 8 6 4 7 1
16. 3 5 7 1 4 2 8 6
17. 3 5 8 4 1 7 2 6
18. 3 6 2 5 8 1 7 4
19. 3 6 2 7 1 4 8 5
20. 3 6 2 7 5 1 8 4
21. 3 6 4 1 8 5 7 2
22. 3 6 4 2 8 5 7 1
23. 3 6 8 1 4 7 5 2
24. 3 6 8 1 5 7 2 4
25. 3 6 8 2 4 1 7 5
26. 3 7 2 8 5 1 4 6
27. 3 7 2 8 6 4 1 5
28. 3 8 4 7 1 6 2 5
29. 4 1 5 8 2 7 3 6
30. 4 1 5 8 6 3 7 2
31. 4 2 5 8 6 1 3 7
32. 4 2 7 3 6 8 1 5
33. 4 2 7 3 6 8 5 1
34. 4 2 7 5 1 8 6 3
35. 4 2 8 5 7 1 3 6
36. 4 2 8 6 1 3 5 7
37. 4 6 1 5 2 8 3 7
38. 4 6 8 2 7 1 3 5
39. 4 6 8 3 1 7 5 2
40. 4 7 1 8 5 2 6 3
41. 4 7 3 8 2 5 1 6
42. 4 7 5 2 6 1 3 8
43. 4 7 5 3 1 6 8 2
44. 4 8 1 3 6 2 7 5
45. 4 8 1 5 7 2 6 3
46. 4 8 5 3 1 7 2 6
47. 5 1 4 6 8 2 7 3
48. 5 1 8 4 2 7 3 6
49. 5 1 8 6 3 7 2 4
50. 5 2 4 6 8 3 1 7
51. 5 2 4 7 3 8 6 1
52. 5 2 6 1 7 4 8 3
53. 5 2 8 1 4 7 3 6
54. 5 3 1 6 8 2 4 7
55. 5 3 1 7 2 8 6 4
56. 5 3 8 4 7 1 6 2
57. 5 7 1 3 8 6 4 2
58. 5 7 1 4 2 8 6 3
59. 5 7 2 4 8 1 3 6
60. 5 7 2 6 3 1 4 8
61. 5 7 2 6 3 1 8 4
62. 5 7 4 1 3 8 6 2
63. 5 8 4 1 3 6 2 7
64. 5 8 4 1 7 2 6 3
65. 6 1 5 2 8 3 7 4
66. 6 2 7 1 3 5 8 4
67. 6 2 7 1 4 8 5 3
68. 6 3 1 7 5 8 2 4
69. 6 3 1 8 4 2 7 5
70. 6 3 1 8 5 2 4 7
71. 6 3 5 7 1 4 2 8
72. 6 3 5 8 1 4 2 7
73. 6 3 7 2 4 8 1 5
74. 6 3 7 2 8 5 1 4
75. 6 3 7 4 1 8 2 5
76. 6 4 1 5 8 2 7 3
77. 6 4 2 8 5 7 1 3
78. 6 4 7 1 3 5 2 8
79. 6 4 7 1 8 2 5 3
80. 6 8 2 4 1 7 5 3
81. 7 1 3 8 6 4 2 5
82. 7 2 4 1 8 5 3 6
83. 7 2 6 3 1 4 8 5
84. 7 3 1 6 8 5 2 4
85. 7 3 8 2 5 1 6 4
86. 7 4 2 5 8 1 3 6
87. 7 4 2 8 6 1 3 5
88. 7 5 3 1 6 8 2 4
89. 8 2 4 1 7 5 3 6
90. 8 2 5 3 1 7 4 6
91. 8 3 1 6 2 5 7 4
92. 8 4 1 3 6 2 7 5
Pressione qualquer tecla para continuar. . .

Passeio do cavalo

A recursividade pode ser usada para resolver problemas cuja solução é tentar todas as alternativas possíveis. A idéia para algoritmos tentativa e erro é decompor  o problema em um número finitos de sub-tarefas  parciais que devem ser exploradas exaustivamente.  Isso significa que devemos testar todas as possibilidades de resultados em um problema à fim de descobrir qual o melhor resultado para esse. Costumam ser algoritmos com uma implementação simples, porém com uma complexidade geralmente elevada.

Exemplo: Dado um tabuleiro com n x n posições, o cavalo movimenta-se segundo as regras do xadrez. Enconte um passeio de um cavalo no tabuleiro de xadrez que visite todas as posições do tabuleiro.

A partir da posição inicial (x₀,y₀), o problema consiste em encontrar, se existir, um passeio do valo com n² – 1 movimentos, tal que todos os pontos do tabuleiro são visitados uma única vez. Um caminho para resolver o problema é considerar a possibilidade de realizar o próximo movimento ou verificar que ele não é possível.

Algoritmo Básico

 Um exemplo de uma solução para o problema do passeio de um cavalo para o tabuleiro 8x8.  

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int t[8][8],a[8],b[8];
void imprime(){
 int i,j;
 for(i=0;i<8;i++){ 

   for(j=0;j<8;j++){ 

     printf("%3d",t[i][j]);} 

    printf("\n"); 

   }
}
int cavalo(int i, int x, int y){
 int u,v,k,q; 
 if(i==65){ imprime(); return 1;}
 //executa movimentos
 for(k=0;k<8;k++){
  u = x + a[k];  v = y + b[k];
  //testa limites do tabuleiro
  if( (u>=0 && u<=7) && (v>=0 && v<=7)){
   if(t[u][v]==0){ //posicao livre
    t[u][v]=i; //registre o movimento
    q = cavalo(i+1,u,v);
    if(q==0) t[u][v]=0; //se não alcançou todos, desfaça 

    else return 1; // se alcançou todos, retorne 1
   }
  }
 }
 return 0;
}
int main(){
 int cont;
 //inicializa��o dos deslocamentos dos movimentos
 a[0]=2;a[1]=1;a[2]=-1;a[3]=-2; 
 b[0]=1;b[1]=2;b[2]=2;b[3]=1;
 
 a[4]=-2;a[5]=-1;a[6]=1;a[7]=2;
 b[4]=-1;b[5]=-2;b[6]=-2;b[7]=-1; 
 memset(t,0,sizeof(t));
 cont =1;
 t[0][0]=1;
 cavalo(2,0,0);
 system("PAUSE");
}

Bibliografia

Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Pioneira Thomson Learning, 1993.