N-Queens II

Q: 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 próxima tem no máximo n-1 , e assim por diante. A poda reduz o trabalho real muito mais, para 856,189 tabuleiros parciais quando n = 12 . O espaço é O(n) .

DifícilBacktracking

+10

Uma rainha ataca todas as casas de sua linha, de sua coluna e de ambas as diagonais, independentemente da distância. Dado um inteiro n, retorne o número de maneiras de posicionar n rainhas em um tabuleiro n × n de modo que nenhuma delas ataque outra.

Tabuleiros que diferem em qualquer casa são contabilizados separadamente, incluindo imagens espelhadas.

Função

totalNQueens(n: integer) → integer

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 em cada linha, de cima para baixo, os tabuleiros são 1, 3, 0, 2 e 2, 0, 3, 1: imagens espelhadas, contadas como duas. Todas as outras escolhas colocam duas rainhas na mesma coluna ou diagonal.

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.

0 de 3 abertas

Solução

Duas rainhas na mesma linha sempre se atacam, então o tabuleiro tem uma coluna por linha: n^n listas, cerca de 8.9 × 10^12 para n = 12. Em vez disso, construa-o linha por linha, descarte um tabuleiro parcial assim que uma rainha for atacada e marque as colunas e diagonais ocupadas para que testar uma casa custe três consultas.

Experimente cada posicionamento com uma rainha por linha

Correta, mas não termina nos maiores testes

Intuição

Escreva uma disposição como uma lista cols, com a coluna da rainha de cada linha, e percorra todas as n^n listas como um odômetro. As rainhas nas linhas i < j se atacam quando cols[i] == cols[j] ou |cols[i] - cols[j]| == j - i, pois uma diagonal avança uma coluna por linha. Cada lista é verificada uma vez, então nenhum tabuleiro é omitido nem contado duas vezes.

Nada interrompe a execução antes do fim: um conflito nas duas primeiras linhas ainda deixa n^(n-2) listas. Para n = 8, são 16,777,216 listas para 92 tabuleiros; para n = 12, 8.9 × 10^12, cerca de 2.5 horas a um nanossegundo cada.

Algoritmo

Comece com cols todo zerado.
Adicione 1 à contagem se nenhum par de linhas i < j tiver cols[i] == cols[j] ou |cols[i] - cols[j]| == j - i.
Avance como um hodômetro: começando pela última linha, redefina cada entrada em n-1 para 0 e, em seguida, adicione 1 à primeira entrada abaixo de n-1.
Pare e retorne a contagem quando todas as entradas forem n-1.

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] += 1

Retrocesso com conjuntos de colunas e diagonais

Intuição

Posicione as rainhas linha por linha e teste cada uma ao posicioná-la. Preencher as linhas abaixo não pode salvar uma rainha sob ataque, então pule essa casa. Uma rainha segura faz uma chamada recursiva para a próxima linha e é removida quando a chamada retorna; chegar à linha n conta um tabuleiro.

Apenas três linhas podem atacar a casa (row, c): sua coluna, sua diagonal /, na qual row + c é constante, e sua diagonal \, na qual row - c é constante (adicione n-1 para indexá-la a partir de 0). Os arrays de sinalizadores cols, diag e anti transformam o teste de segurança em três consultas. Cada linha comporta no máximo uma rainha, então limpar os sinalizadores no retorno restaura os arrays exatamente.

A linha k oferece no máximo n - k colunas, então a busca é limitada por O(n!), com espaço O(n).

Algoritmo

Crie arrays de sinalizadores cols de tamanho n e diag e anti de tamanho 2n-1, todos desligados.
place(row): se row == n, retorne 1.
Para cada coluna c, pule-a se cols[c], diag[row + c] ou anti[row - c + n - 1] estiver ligado.
Caso contrário, ligue os três sinalizadores, adicione place(row + 1) ao total e 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 por flags ainda testa todas as n colunas de cada linha; as máscaras de bits vão direto às casas livres. O bit c é a coluna c da linha que está sendo preenchida: cols guarda as colunas ocupadas, e left e right, as casas atacadas ao longo de cada diagonal. Então, free = ~(cols | left | right) & full, com full contendo os n bits menos significativos, e free & -free é a casa livre mais à esquerda. Uma linha abaixo, uma coluna continua ocupada e cada ataque diagonal se desloca uma coluna.

Com n = 4 e uma primeira rainha em bit = 0010, a linha 1 obtém free = 1000: coluna 3, encontrada sem testar as outras. Para n = 12, 856,188 iterações do loop substituem 10,103,868 testes de casas. O código R gera uma linha inteira de tabuleiros parciais de uma só vez, em vez de recorrer.

Algoritmo

Defina full = (1 << n) - 1.
count(cols, left, right): se cols == full, retorne 1.
Calcule free = ~(cols | left | right) & full.
Enquanto free não for 0, obtenha bit = free & -free, remova-o de free e some count(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

Indexar anti com row - c sem adicionar n-1. Java lança uma exceção, C lê fora do array e anti[-2] do Python lê silenciosamente a flag de outra diagonal.
Dimensionar os arrays das diagonais com n em vez de 2n-1. row + c chega a 2n-2.
Não limpar as flags após a chamada recursiva. Os ramos posteriores veem rainhas que já foram removidas, e a contagem diminui.
Deixar & full de fora de free. ~x define os bits acima da coluna n-1, então o loop escolhe casas fora do tabuleiro; em Python ou Ruby, free fica negativo e o loop nunca termina.

Perguntas frequentes3

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 próxima tem no máximo n-1, e assim por diante. A poda reduz o trabalho real muito mais, para 856,189 tabuleiros parciais quando n = 12. O espaço é O(n).

Qual é a diferença entre N-Queens e N-Queens II?

N-Queens retorna todos os tabuleiros, representados como linhas de texto; N-Queens II retorna apenas quantos existem. A busca é a mesma, mas a contagem não armazena tabuleiros, o que combina com a versão de máscara de bits.

Você pode usar a simetria para acelerar N-Queens II?

Espelhar um tabuleiro da esquerda para a direita gera outro tabuleiro válido, então conte os tabuleiros cuja primeira rainha está nas colunas 0 a n/2 - 1 e multiplique essa quantidade por dois. Para n ímpar, some uma vez os tabuleiros cuja primeira rainha está na coluna do meio.

def totalNQueens(n):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

n = 4

Saída Esperada

N-Queens II

Função

Restrições

Exemplos

Dicas

Solução

Experimente cada posicionamento com uma rainha por linha

Retrocesso com conjuntos de colunas e diagonais

Retrocesso com máscaras de bits

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos