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

Linha Codigo   (aula_05_problema_n_rainhas.py)
001# Aula 05: problemas das N rainhas
002# Dado N (natural) verificar se e' ou nao possivel posicionar N
003# rainhas no tabuleiro de xadrez sem que uma delas possa atacar outra.
004# Na solucao 1 apresento uma ideia inicial (ineficiente em termos de espaco, usando O(n^2)), depois
005# a solucao 2 que economiza espaco, usando apenas O(n) posicoes de memoria.
006# Apresento apenas a implementacao mais eficiente em termos de espaco em memoria (solucao 2).
007
008# Solucao 1. O(n^2) posicoes de memoria, O(n) para verificar posicao sob ataque
009# + Estrutura auxiliar: uma matriz (para posicionar as rainhas e indicar posicoes sob ataque);
010# + Ideia: Fazer umma implementacao recursiva para posicionar a linha i (sempre na linha i), entao escolher sua coluna.
011
012# Solucao 2. Mais eficiente em termos de memoria (O(n)) e velocidade (verifica posicao sob ataque em O(1))
013# + Estrutura auxiliar: 4 vetores
014# . - vlinha[] : vlinha[i]=k se rainha i foi posicionada na coluna i (vlinha[i]=-1 indica coluna livre)
015# . - vdiag_princ[ ] : vdiag_princ[i]=1 se existe uma rainha (qualquer) atacando a diagonal principal i
016# . - vdiag_secund[] : vdiag_secund[i]=1 se existe uma rainha (qualquer) atacando a diagonal secundaria i
017
018# Matematica necessaria para vdiag_princ[]:                                                    | Considerando uma matriz n=5 (dimensao 5)
019# - Ideia da Algebra Linear e do calculo de curva de nivel:                                    |   0_1_2_3_4
020#   d e x vetores do R^n, sao ortogonais se, e somente se, d'x=0                               | 0|_|\|_|_|\| -> curva de nivel i-j=-(n-1)=-4 (menor)
021#   Em R^2 os vetores x e y estao na curva de nivel de valor k, (1;-1)'(x;y)=k                 | 1|_|_|\|_|_|
022#   Considerando as posicoes de uma matriz quadrada de ordem n, desde (0,0) ate' (n-1,n-1),    | 2|_|_|_|\|_|
023#   um elemento esta' na linha i, coluna j tal que i-j=k, k=-(n-1),-(n-2),...,-1,0,1,2,...,n-1 | 3|_|_|_|_|\| -> curva de nivel i-j=-1
024#   Assim, as curvas de nivel vao de i-j=-(n-1) ate' i-j=n-1                                   | 4|\|_|_|_|_|
025#   Entao podemos usar uma bijecao para associar i com sua posicao: dp(i) = l-c + (n-1)        |   +-> curva de nivel i-j=(n-1)=4 (maior curva)
026
027# Matematica necessaria para vdiag_secund[]:                                                   | Considerando uma matriz n=5 (dimensao 5)
028# - Ideia da Algebra Linear e do calculo de curva de nivel:                                    |   0_1_2_3_4
029#   d e x vetores do R^n, sao ortogonais se, e somente se, d'x=0                               | 0|/|_|_|_|_| -> menor curva de nivel: i+j=0
030#   Em R^2 os vetores x e y estao na curva de nivel de valor k, (1;1)'(x;y)=k                  | 1|_|_|_|_|_|
031#   Considerando as posicoes de uma matriz quadrada de ordem n, desde (0,0) ate' (n-1,n-1),    | 2|_|_|_|_|_|
032#   um elemento esta' na linha i, coluna j tal que i+j=k, k=0, 1, 3, ..., 2n-2                 | 3|_|_|_|_|/| -> curva de nivel i+j=2n-3=7
033#   Assim, as curvas de nivel vao de i-j=-(n-1) ate' i-j=n-1                                   | 4|_|_|_|/|/| -> maior curva de nivel i+j=2n-2=8
034#   Entao podemos usar uma bijecao para associar i com sua posicao: ds(i) = i = l+c (l=linha)  |
035
036from __future__ import print_function; # para funciona print com 'end=""' no Python 2
037
038import sys; # Para passar parametro via linha de comando (valor do n):
039#             $ python problema_n_rainhas.py 5
040
041
042def imprima_solucao (N, vet_linhas) :
043  #D print("imprima_solucao(%d,%s)" % (N,vet_linhas));
044  for i in range(N) :
045    pos = vet_linhas[i]; # rainha i na coluna 'vet_linhas[i]'
046    for j in range(N) :
047      if (j==pos) : print("%2d " % (i+1), end=""); # internamente a primeira rainha e' 0, mas para diferenciar imprimimos como 1 ate' N
048      else : print("%2d " % 0, end="");
049    print(); # mude de linha
050
051
052# Diagonal principal
053# i    : -(n-1), -(n-2), ..., -1,     0,     1, 2,   ... (n-1)
054# dp(i):  0,      1,           (n-2), (n-1), n, n+1  ...  2n-1 => dp(i) = i+(n-1)
055# Exemplo de diagonal principal: Para n=4, menor curva e' i=0 e j=n-1 => (i-j)=-(n-1); maior e' i=n-1 e j=0 => (i-j)=n-1
056# Entao ajustando a funcao bijetora dp(i) para associar (0,n-1) com -(n-1) e (n-1,0) com n-1
057#         dp(i) = dp(l+c) = (l+c) + (n-1)
058# Tabela para n=4
059# i    : -3,     -2,          -1,     0,     1, 2,       3
060# dp(i):  0,      1,           2,     3,     4, 5,       6 => dp(i) = i+(n-1) = i+3 (i=linha-coluna)
061
062# Diagonal secundaria
063# ds(i):  0,      1,           (n-2), (n-1), n, n+1  ...  2n-2 => ds(i) = i         (i=linha+coluna)
064
065
066# Verifica se a posicao [lin][col] esta' livre para a rinha lin
067# Note que os vetores/listas 'vlinha,vdiagp,vdiags' sao passsado por referencia (logo modificacao reflete nos parametros efetivos),
068# ou usando o termo da apostila digital, esta' e' uma funcao "modificadora" em relacao 'a estas variveis!
069def posicaoSegura (N, r, lin, col, vlinha, vdiagp, vdiags) :
070  if (vlinha[col]!=-1) :        return False; # coluna 'col' ja' ocupada...
071  if (vdiagp[lin-col+N-1]==1) : return False; # diag. princ. ja' atacada...
072  if (vdiags[lin+col]==1) :     return False; # diag. secun. ja' atacada...
073  vlinha[col] = r;         # agora linha ocupada (rainha 'lin' na coluna 'col') (note: como r>=0, usamos -1 para indicar posicao livre)
074  vdiagp[lin-col+N-1] = 1; # agora diagonal principal ocupada:  k=l-c, k =  -(n-1), -(n-2), ...0,   1, 2, ... (n-1) <-> 0, 1, ..., n, n+1, n+2, ... 2n-1
075  vdiags[lin+col] = 1;     # agora diagonal secundaria ocupada: k=l+c, k =   0,      1,        n-1, n, n+1,   2n-2
076  return True; # pode posicionar rainha lin na coluna col
077
078
079# Tenta posicionar a rainha 'r' em alguma coluna
080def tenta_recursivamente (N, r, vlinha, vdiagp, vdiags) :
081  # Testa final de posicionamento: lin==N => posicionadas N rainhas! Sucesso!
082  if (r == N) : return True; # Sucesso! Todas as N rainhas posicionadas!
083  # Considere cada coluna 'col' para a rainha 'lin': tente posicionar rainha primeiro na colunas 0, depois 1, ate' N-1
084  for col in range(N) :
085    lin = r; # rainha i sempre na linha i
086    if (posicaoSegura(N, r, lin, col, vlinha, vdiagp, vdiags)) :
087
088      # Agora tente posicioar a rainha r+1
089      if (tenta_recursivamente(N, r+1, vlinha, vdiagp, vdiags)) :
090        return True; # Teve sucesso com esta posicao (posicionou todas)
091      
092      # Se houve erro, desfaca a marcacao para tentar em nova linha
093      vlinha[col] = -1;        # desocupa coluna (note: como r>=0, usamos -1 para indicar posicao livre)
094      vdiagp[lin-col+N-1] = 0; # desocupa diagonal principal
095      vdiags[lin+col] = 0;     # desocupa diagonal secundaria
096  # Se chegou neste ponto, entao nao foi possivel posiciona rainha col, desista...
097  return False;
098
099
100# Tentativa e erro para o problema das N rainhas
101def n_rainhas (N) :
102  if (tenta_recursivamente(N, 0, vlinha, vdiagp, vdiags) == False) : # tenta rainha 0 na coluna 0
103    print ("NAO existe posicionamente viavel para %d rainhas em tabuleiro %d x %d!" % (N, N, N));
104    return False;
105  imprima_solucao(N, vlinha);
106  return True;
107
108
109# Auxiliar para depuracao
110# Testando o truque da bijecao para a diagonal principal
111def testa_diagonal_p (n) :
112  print("2*N-2 = %d " % (2*n-2));
113  # dp(i) :  0,      1,           2,     3,     4, 5,       6 => dp(i) = i+3
114  for i in range(n) :
115    for j in range(n) : print("%d " % (i-j + n-1), end="");
116    print();
117
118
119# Codigo principal
120if (len(sys.argv)<2) : print("Precisa informar tamanho do tabuleiro, e.g., para n=5, deve digitar\npython aula_05_problema_n_rainhas.py 5"); sys.exit();
121#D print("sys.argv=%d" % len(sys.argv));
122
123# Tenta com N rainhas
124N = int(sys.argv[1]); # pega primeiro argumento (deve ser inteiro)
125
126# testa_diagonal_p(N);
127
128print("Tenta posicionar %d rainhas em um tabuleiro %d x %d" % (N, N, N));
129
130# Estruturas para algoritmo mais eficiente:
131vlinha  = N*[-1];  # linha[i] = k <=> rainha i esta' na coluna k (note: como r>=0, usamos -1 para indicar posicao livre)
132vdiagp  = 2*N*[0]; # diagp[i] = 1 <=> existe rainha na diagonal princial i   (i=-(n-1), -(n-2), ..., 0, 1, 2, ... (n-1))
133vdiags  = 2*N*[0]; # diags[i] = 1 <=> existe rainha na diagonal secundaria i (i=-0, 1, 2, ... 2*(n-1))
134
135n_rainhas(N);
136
137