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. . .