MAC0122
Material didático para princípios de desenvolvimento de Algoritmos
| Linha | Codigo |
| 001 | # Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br |
| 002 | # MAC0122 - 2025/08/19 |
| 003 | # |
| 004 | # Problema das N rainhas |
| 005 | # Aula 05: problemas das N rainhas (implementa 1: menos eficiente) |
| 006 | |
| 007 | from __future__ import print_function |
| 008 | |
| 009 | import sys; # Para passar parametro via linha de comando: python problema_n_rainhas.py 5 |
| 010 | |
| 011 | def imprima_solucao (tabuleiro) : |
| 012 | for i in range(N): |
| 013 | for j in range(N): |
| 014 | print(tabuleiro[i][j],end=' ') |
| 015 | print() |
| 016 | |
| 017 | # Diagonal principal |
| 018 | # i : -(n-1), -(n-2), ..., -1, 0, 1, 2, ... (n-1) |
| 019 | # dp(i): 0, 1, (n-2), (n-1), n, n+1 ... 2n-1 => dp(i) = i+(n-1) |
| 020 | # i : -3, -2, -1, 0, 1, 2, 3 |
| 021 | # l(i) : 0, 1, 2, 3, 4, 5, 6 => dp(i) = i+3 |
| 022 | |
| 023 | # Diagonal secundaria |
| 024 | # ds(i): 0, 1, (n-2), (n-1), n, n+1 ... 2n-1 => ds(i) = i |
| 025 | |
| 026 | |
| 027 | # Verifica se a posicao [lin][col] nao sofre ataque |
| 028 | def posicaoSegura (tabuleiro, lin, col, vlinha, vcoluna, vdiagp, vdiags) : |
| 029 | global N; |
| 030 | if (vlinha[lin]==1) : return False; |
| 031 | if (vcoluna[col]==1) : return False; |
| 032 | if (vdiagp[lin-col+N-1]==1) : return False |
| 033 | if (vdiags[lin+col]==1) : return False; |
| 034 | vlinha[lin] = 1; # agora linha ocupada |
| 035 | vcoluna[col] = 1; # agora coluna ocupada |
| 036 | vdiagp[lin-col+N-1] = 1; # agora diagonal principal ocupada: -(n-1), -(n-2), ...0, 1, 2, ... (n-1) <-> 0, 1, ..., n, n+1, n+2, ... 2n-1 |
| 037 | vdiags[lin+col] = 1; # agora diagonal secundaria ocupada |
| 038 | return True; # seguro |
| 039 | |
| 040 | def tenta_recursivamente (N, tabuleiro, col, vlinha, vcoluna, vdiagp, vdiags) : |
| 041 | # Testa final de posicionamento: col==N => posicionadas N rainhas! Sucesso! |
| 042 | if (col >= N) : return True |
| 043 | # Considere esta coluna e tente posicionar a rainha na linha i (i de 0 ate' N-1) |
| 044 | for lin in range(N): |
| 045 | if (posicaoSegura(tabuleiro, lin, col, vlinha, vcoluna, vdiagp, vdiags)) : |
| 046 | tabuleiro[lin][col] = 1; # posicione rainha col na linha lin |
| 047 | # Agora tente posicioar a rainha col+1 |
| 048 | if (tenta_recursivamente(N, tabuleiro, col+1, vlinha, vcoluna, vdiagp, vdiags)) : |
| 049 | return True; # Teve sucesso com esta posical (posicionou todas) |
| 050 | # Se houve erro, desfaca a marcacao para tentar em nova linha |
| 051 | tabuleiro[lin][col] = 0; # libere posical do tabuleiro |
| 052 | vlinha[lin] = 0; # desocupa linha |
| 053 | vcoluna[col] = 0; # desocupa coluna |
| 054 | vdiagp[lin-col+N-1] = 0; # desocupa diagonal principal |
| 055 | vdiags[lin+col] = 0; # desocupa diagonal secundaria |
| 056 | # Se chegou neste ponto, entao nao foi possivel posiciona rainha col, desista... |
| 057 | return False; |
| 058 | |
| 059 | # Tentativa e erro para o problema das N rainhas |
| 060 | def n_rainhas (N) : |
| 061 | # Solucao menos eficiente |
| 062 | tabuleiro = []; |
| 063 | for i in range(N) : |
| 064 | linhaA = [] |
| 065 | for j in range(N) : |
| 066 | linhaA.append(0); |
| 067 | tabuleiro.append(linhaA); |
| 068 | |
| 069 | if (tenta_recursivamente(N, tabuleiro, 0, vlinha, vcoluna, vdiagp, vdiags) == False) : |
| 070 | print ("Solution does not exist"); |
| 071 | return False; |
| 072 | |
| 073 | imprima_solucao(tabuleiro); |
| 074 | return True |
| 075 | |
| 076 | # Testando o truque da bijecao para a diagonal principal |
| 077 | def testa_diagonal_p (n) : |
| 078 | print("2*N-2 = %d " % (2*n-2)); |
| 079 | # dp(i) : 0, 1, 2, 3, 4, 5, 6 => dp(i) = i+3 |
| 080 | for i in range(n) : |
| 081 | for j in range(n) : print("%d " % (i-j + n-1), end=""); |
| 082 | print(); |
| 083 | |
| 084 | # testa_diagonal_p(N); |
| 085 | |
| 086 | # Tenta com N rainhas |
| 087 | N = int(sys.argv[1]); # pega primeiro argumento (deve ser inteiro) |
| 088 | |
| 089 | print("Tenta posicionar %d rainhas em um tabuleiro %d x %d" % (N, N, N)); |
| 090 | |
| 091 | # Estruturas para algoritmo mais eficiente: |
| 092 | vlinha = N*[0]; # linha[i] =1 <=> existe rainha na linha i |
| 093 | vcoluna = N*[0]; # coluna[i]=1 <=> existe rainha na coluna i |
| 094 | vdiagp = 2*N*[0]; # diagp[i] =1 <=> existe rainha na diagonal princial i (i=-(n-1), -(n-2), ..., 0, 1, 2, ... (n-1)) |
| 095 | vdiags = 2*N*[0]; # diags[i] =1 <=> existe rainha na diagonal secundaria i (i=-0, 1, 2, ... 2*(n-1)) |
| 096 | |
| 097 | n_rainhas(N); |
| 098 | |
| 099 |