N-Queens II
Uma rainha em um tabuleiro de xadrez ataca todas as casas de sua linha, de sua coluna e de ambas as diagonais, por mais distantes que estejam. Você recebe um inteiro n. Retorne o número de maneiras de posicionar n rainhas em um tabuleiro n × n de modo que nenhuma rainha ataque outra.
Duas maneiras são diferentes quando alguma casa contém uma rainha em uma delas e está vazia na outra. Portanto, um tabuleiro e sua imagem espelhada contam como duas maneiras, embora pareçam iguais.
Função
- ninteger
- o tamanho do tabuleiro e o número de rainhas
- Retornainteger
- o número de maneiras de posicionar as rainhas de modo que nenhuma ataque outra
Restrições
1 ≤ n ≤ 12- A resposta para
n = 12é 14.200, então cabe em um inteiro de 32 bits.
Exemplos
- Entrada
- n = 4
- Saída
- 2
- Explicação
- Escrevendo a coluna da rainha de cada linha de cima para baixo, os dois tabuleiros são
1, 3, 0, 2e2, 0, 3, 1. Cada um é a imagem espelhada do outro, e eles contam como duas soluções. Qualquer outra escolha coloca duas rainhas na mesma coluna ou diagonal.
- Entrada
- n = 3
- Saída
- 0
- Explicação
- Uma rainha no canto superior esquerdo deixa apenas a extremidade direita da linha do meio, e então a linha de baixo não tem nenhuma casa segura. O canto superior direito falha da mesma maneira, e uma rainha no meio da parte superior ataca as três casas da linha do meio. Portanto, nenhum tabuleiro funciona.
+10 testes ocultos ao enviar
Para ir além
Você consegue contar apenas os tabuleiros que continuam diferentes após girar e espelhar o tabuleiro? Para n = 8, os 92 tabuleiros se dividem em 12 grupos desse tipo.
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Duas rainhas na mesma linha atacam uma à outra, então cada linha contém exatamente uma rainha. O que resta escolher depois que você sabe disso?
Preencha o tabuleiro uma linha por vez, de cima para baixo. Assim que a nova rainha estiver sob ataque, abandone esse tabuleiro parcial, pois nada do que você adicionar abaixo poderá consertá-lo. Para testar uma casa sem olhar para o tabuleiro inteiro, lembre-se de quais colunas e diagonais já têm uma rainha. Em uma direção diagonal,
row + colé igual para todas as casas, e na outra,row - colé.Escreva
place(row), que retorna quantos tabuleiros completos podem ser finalizados a partir daqui. Ela retorna 1 quandorow == n. Caso contrário, tenta cada colunaccuja coluna, diagonalrow + ce diagonalrow - cestejam todas livres: marque as três, adicioneplace(row + 1)a um total acumulado e, em seguida, desmarque-as. A resposta éplace(0).
Solução
Uma disposição é determinada escolhendo uma coluna para cada linha, já que duas rainhas na mesma linha sempre atacam uma à outra. Ainda são n^n possibilidades, cerca de 8.9 × 10^12 para n = 12, então você não pode listar todas. Duas ideias resolvem o problema. Construa o tabuleiro linha por linha e abandone um tabuleiro parcial assim que uma rainha for atacada, reduzindo a busca para menos de um milhão de tabuleiros parciais para n = 12. E registre quais colunas e diagonais estão ocupadas, para que testar uma casa custe três consultas em vez de percorrer todas as rainhas colocadas até então.
Tente cada posicionamento com uma rainha por linha
Correta, mas não termina nos maiores testes
Intuição
Cada linha deve conter exatamente uma rainha, então um posicionamento é uma lista cols em que cols[r] é a coluna da rainha na linha r. Cada entrada pode ser qualquer uma das n colunas, então há n^n listas. Percorra todas elas como um hodômetro conta: aumente a última entrada em um e, quando ela passar de n-1, redefina-a para 0 e leve o incremento para a entrada anterior.
Para cada lista, compare todos os pares de linhas i < j. As duas rainhas se atacam quando estão na mesma coluna, cols[i] == cols[j], ou na mesma diagonal. Em uma diagonal, descer uma linha significa mover uma coluna para a esquerda ou para a direita, então duas rainhas estão na mesma diagonal exatamente quando a diferença entre as colunas é igual à diferença entre as linhas: |cols[i] - cols[j]| == j - i. Uma lista que passa por todos os pares corresponde a um tabuleiro válido. Como todas as listas são verificadas, nenhuma é ignorada e nenhuma é contada duas vezes.
É lento porque nunca para antes do fim. Duas rainhas na mesma diagonal nas duas primeiras linhas condenam o tabuleiro, mas o hodômetro ainda tenta todas as n^(n-2) maneiras de preencher as outras linhas. Para n = 8, são 16,777,216 listas para encontrar 92 tabuleiros. Para n = 12, são cerca de 8.9 × 10^12 listas. Mesmo a um nanossegundo por lista, isso dá cerca de 2,5 horas.
Algoritmo
- Comece com
colstodo igual a zero: cada rainha na coluna 0. - Verifique cada par de linhas
i < j: a lista é inválida secols[i] == cols[j]ou|cols[i] - cols[j]| == j - i. - Se nenhum par estiver em conflito, some 1 à contagem.
- Avance
colscomo um hodômetro: de baixo para cima, redefina cada entrada que contémn-1para 0 e, em seguida, some 1 à primeira entrada que não contémn-1. - Quando todas as entradas forem
n-1, todas asn^nlistas terão sido verificadas: retorne a contagem.
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1Retrocesso usando conjuntos de colunas e diagonais
Intuição
Posicione as rainhas linha por linha, de cima para baixo, e verifique cada nova rainha no momento em que a posicionar. Se ela estiver sob ataque, nenhuma maneira de preencher as linhas abaixo poderá corrigir isso, então pule a casa imediatamente. Se estiver segura, faça a chamada recursiva para a próxima linha e, quando essa chamada retornar, remova a rainha e tente a próxima coluna. Uma chamada que chega à linha n posicionou n rainhas seguras e conta um tabuleiro. Isso é retrocesso, e ele poda bastante: para n = 12, visita 856,189 tabuleiros parciais, em vez de 8.9 × 10^12 tabuleiros completos.
A outra metade é testar uma casa rapidamente. As linhas abaixo estão vazias, e a própria linha da nova rainha não tem outra rainha, então apenas três linhas podem atacar a casa (row, c): sua coluna, sua diagonal / e sua diagonal \. Todas as casas em uma diagonal / têm o mesmo row + c, de 0 a 2n-2. Todas as casas em uma diagonal \ têm o mesmo row - c, de -(n-1) a n-1, então some n-1 para obter um índice de 0 a 2n-2. Mantenha três arrays de flags: cols de tamanho n e diag e anti de tamanho 2n-1. A casa está segura exatamente quando as três flags estão desligadas: três consultas, O(1), enquanto comparar com cada rainha posicionada até então custaria O(n).
Uma linha pode conter no máximo uma rainha, então posicionar uma rainha liga suas três flags e removê-la as desliga novamente, deixando os arrays exatamente como estavam. No tabuleiro de 4 por 4, uma rainha em (0, 0) define cols[0], diag[0] e anti[3]. Na linha 1, a coluna 1 fica em anti[3], então é pulada sem verificar a própria rainha.
A primeira linha oferece n colunas, a segunda no máximo n-1 e assim por diante, então a busca é limitada por O(n!), e as diagonais a reduzem muito abaixo disso. Para n = 12, os loops testam 10,103,868 casas no total. A recursão tem profundidade de n chamadas e os arrays contêm cerca de 5n flags, então o espaço é O(n).
Algoritmo
- Crie três arrays de sinalizadores, todos desligados:
colscomnposições,diageanticom2n-1posições cada. - Escreva
place(row). Serow == n, retorne 1: cada linha contém uma rainha segura. - Caso contrário, para cada coluna
c, ignore-a secols[c],diag[row + c]ouanti[row - c + n - 1]estiver ligado. - Para uma coluna segura, ligue os três sinalizadores, some
place(row + 1)ao total e, em seguida, desligue-os. - Retorne o total. A resposta é
place(0).
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)Retrocesso com máscaras de bits
Intuição
A busca com conjuntos é rápida, mas em cada linha ainda testa todas as n colunas, a maioria delas atacadas. Uma máscara de bits permite ir direto às casas livres. Faça com que o bit c de um inteiro represente a coluna c da linha que você está prestes a preencher e mantenha três máscaras: cols, as colunas já ocupadas; left, as casas desta linha atingidas em uma direção diagonal; e right, as atingidas na outra.
As casas livres são então obtidas com uma única expressão: free = ~(cols | left | right) & full, em que full tem os n bits menos significativos definidos. free & -free isola a casa livre de menor posição, e subtraí-la avança para a próxima. Ao colocar uma rainha em bit e descer uma linha, a coluna dela continua ocupada, enquanto cada ataque diagonal se desloca uma coluna. Assim, a próxima linha recebe cols | bit, ((left | bit) << 1) & full e (right | bit) >> 1. Não há nada para desfazer: cada chamada recebe seus próprios três inteiros. Quando cols == full, as n rainhas estão posicionadas.
Considere n = 4 e uma primeira rainha na coluna 1, bit = 0010, escrevendo a coluna 0 como o bit mais à direita. A linha 1 recebe cols = 0010, left = 0100 e right = 0001, então free = 1000: a coluna 3 é a única opção, encontrada sem testar as colunas 0, 1 ou 2.
A busca visita os mesmos tabuleiros parciais que a versão com conjuntos, mas agora cada etapa do laço posiciona uma rainha. Para n = 12, são 856,188 etapas em vez de 10,103,868 testes de casas, com algumas operações inteiras em cada etapa. O tempo continua limitado por O(n!), e a recursão tem profundidade de n chamadas. O código em R executa as mesmas máscaras sem recursão: mantém em um vetor todos os tabuleiros parciais de uma linha e os expande todos, uma linha por vez, armazenando na memória um nível inteiro de tabuleiros, em vez de n chamadas.
Algoritmo
- Defina
full = (1 << n) - 1, a máscara de todas asncolunas. - Escreva
count(cols, left, right). Secols == full, retorne 1. - Calcule
free = ~(cols | left | right) & full. - Enquanto
freenão for 0, obtenhabit = free & -free, remova-o defreee adicionecount(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)ao total. - Retorne o total. A resposta é
count(0, 0, 0).
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
Armadilhas e casos extremos
A busca em si é curta. A maioria dos bugs está nos cálculos das diagonais e na etapa de desfazer.
- Usar
row - ccomo índice sem adicionarn-1. Em Java, isso gera uma exceção; em C, lê memória fora do array; e, em Python,anti[-2]lê silenciosamente a flag de outra diagonal, fazendo a contagem ficar errada sem gerar erro. - Dimensionar os arrays das diagonais com
nelementos. Um tabuleiron × ntem2n-1diagonais em cada direção. - Verificar apenas uma direção das diagonais ou apenas as colunas. As duas direções das diagonais permitem ataques.
- Esquecer de desligar as flags depois que a chamada recursiva retorna. Todos os ramos seguintes passam a considerar rainhas que já não estão no tabuleiro, e a contagem diminui.
- Omitir
& fullao calcularfree.~xtambém define todos os bits acima da colunan-1, então o loop seleciona casas fora do tabuleiro; e, em Python ou Ruby, cujos inteiros não têm largura fixa,freese torna negativo e o loop nunca termina. - Tratar imagens espelhadas como um único tabuleiro. O problema as conta separadamente:
n = 4tem 2 tabuleiros, e eles são imagens espelhadas um do outro. - Tratar casos especiais de tabuleiros pequenos de forma incorreta.
n = 1tem 1 tabuleiro, enquanton = 2en = 3não têm nenhum. A busca acerta os três casos sem nenhum caso especial.
Perguntas frequentes4
Qual é a complexidade de tempo de N-Queens II?
A busca com retrocesso é limitada por O(n!): a primeira linha tem n opções, a seguinte tem no máximo n-1, e assim por diante. As verificações das diagonais podam a busca muito antes desse limite, reduzindo-a a 856.189 tabuleiros parciais para n = 12. Não se conhece nenhum método polinomial para contar as soluções, então uma busca como esta é a resposta padrão. O espaço é O(n).
Como você identifica em qual diagonal um quadrado está?
Avançar um passo ao longo de uma diagonal / soma 1 à linha e subtrai 1 da coluna, então row + col nunca muda. Avançar ao longo de uma diagonal \ soma 1 a ambas, então row - col nunca muda. Cada soma identifica uma diagonal, e somar n-1 à diferença a transforma em um índice de array de 0 a 2n-2.
Qual é a diferença entre N-Queens e N-Queens II?
N-Queens pede todos os tabuleiros, desenhados como linhas de texto. N-Queens II pergunta apenas quantos existem. A busca usa o mesmo retrocesso, mas, para contar, não é necessário manter nenhum tabuleiro na memória, apenas os conjuntos de colunas e diagonais, o que torna o processo mais rápido e leve. É também por isso que a versão com máscaras de bits é natural aqui.
Você pode usar simetria para acelerar o N-Queens II?
Sim. Espelhar um tabuleiro da esquerda para a direita produz outro tabuleiro válido, então os tabuleiros com a primeira rainha na metade esquerda correspondem aos que a têm na metade direita. Conte os tabuleiros cuja primeira rainha está nas colunas 0 a n/2 - 1 e dobre esse valor. Quando n for ímpar, adicione uma vez os tabuleiros com a primeira rainha na coluna do meio. Isso reduz a busca pela metade.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def totalNQueens(n):
# Escreva o código aquiCaso 1
Caso 2
Entrada
n = 4
Esperado
2