NQueens package

Visão geral

O problema da N-Queens é um desafio clássico frequentemente encontrado em entrevistas de programação e ambientes acadêmicos. O desafio é colocar N Queens em um tabuleiro de xadrez n × n, de modo que não há duas rainhas se ameaçam. Isso significa que não há duas rainhas que não possam compartilhar a mesma linha, coluna ou diagonal.

Declaração de problemas

Dado um número inteiro, retorne todas as soluções distintas ao quebra-cabeça N-Queens. Você pode retornar as respostas em qualquer ordem.

Cada solução contém uma configuração distinta da placa do posicionamento N-Queens, onde 'Q' indica uma rainha e ''. indica um espaço vazio.

Exemplo

Para n = 4, as soluções possíveis são:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Abordagem e algoritmos

Algoritmo de volta

A abordagem mais comum para resolver o problema da N-Queens é usar o backtracking. O algoritmo de retrocesso constrói de forma incremental candidatos à solução e abandona um candidato assim que determinar que o candidato não pode levar a uma solução válida.

Passos:

1. Initialize the Board : comece com uma placa N × N vazia.
2. Place the Queen : tente colocar a rainha na primeira fila e prossiga para colocar as rainhas subsequentes.
3. Check Validity : para cada colocação da rainha, verifique se ele entra em conflito com as rainhas já colocadas.
4. Backtrack if Necessary : Se colocar uma rainha levar a nenhuma solução, remova a rainha (backtrack) e tente a próxima posição.
5. Store the Solution : se uma configuração válida for encontrada (N Queens colocada), armazene a configuração da placa.
6. Repeat : continue esse processo até que todas as configurações possíveis tenham sido tentadas.

Desafios

Representação do conselho

A placa pode ser representada usando uma lista 2D em que cada célula é 'q' ou '.'.

Verificando conflitos

Verificar com eficiência os conflitos é crucial:

1. Row Check : garantindo que nenhuma outra rainha esteja na mesma linha.
2. Column Check : garantindo que nenhuma outra rainha esteja na mesma coluna.
3. Diagonal Check : garantindo que nenhuma outra rainha esteja na mesma diagonal.

Otimização

O uso de conjuntos para rastrear colunas e diagonais ocupados pode acelerar o processo de verificação de conflitos.

Concorrência com ThreadpoolExecutor

Para otimizar a solução do problema para N maior, a solução aproveita a simultaneidade com o ThreadPoolExecutor:

• Cada encadeamento começa a resolver o problema para uma coluna diferente na primeira linha.
• Essa abordagem paralela pode reduzir significativamente o tempo para encontrar todas as soluções.

Nossa solução

Essa solução veio a um dos nossos desafios gratuitos de sexta -feira , onde escolhemos desafios de entrevistas aleatórias durante nosso tempo de inatividade para escrever soluções.

Instalação

 pip install wolfsoftware.NQueens

Uso

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

Resumo

O problema do N-Queens é um desafio fascinante e complexo que requer uma profunda compreensão das técnicas de recursão, retrocesso e otimização. Ao alavancar multi-threading, essa implementação encontra com eficiência todas as soluções possíveis para um determinado tamanho da placa. Compreender e implementar o problema N-Queens é um exercício valioso para melhorar as habilidades de solução de problemas e o pensamento algorítmico.