NQueens package

개요

N-Queens 문제는 프로그래밍 인터뷰 및 학업 환경에서 종종 발생하는 고전적인 도전입니다. 도전은 두 여왕이 서로를 위협하지 않도록 n 퀸즈를 n × n 체스 판에 배치하는 것입니다. 이것은 두 퀸즈가 동일한 행, 열 또는 대각선을 공유 할 수 없음을 의미합니다.

문제 진술

정수 N이 주어지면 모든 별개의 솔루션을 N- 큐 퍼즐에 반환하십시오. 어떤 순서로든 답변을 반환 할 수 있습니다.

각 솔루션에는 N-Queens의 배치에 대한 뚜렷한 보드 구성이 포함되어 있으며, 여기서 'Q'는 여왕과 '를 나타냅니다.' 빈 공간을 나타냅니다.

예

n = 4의 경우 가능한 솔루션은 다음과 같습니다.

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

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

접근 및 알고리즘

역 추적 알고리즘

N- 큐 문제를 해결하기위한 가장 일반적인 접근법은 역 추적을 사용하는 것입니다. 역 추적 알고리즘은 후보자가 유효한 솔루션으로 이어질 수 없다고 판단하자마자 솔루션에 대한 후보자를 점진적으로 구축하고 후보를 포기합니다.

단계 :

1. Initialize the Board : 빈 N × N 보드로 시작하십시오.
2. Place the Queen : 여왕을 첫 번째 줄에 놓고 후속 여왕을 배치하십시오.
3. Check Validity : 각 여왕 배치에 대해 이미 배치 된 여왕과 충돌하는지 확인하십시오.
4. Backtrack if Necessary : 여왕을 배치하면 솔루션이 없으면 여왕 (백 트랙)을 제거하고 다음 위치를 시도하십시오.
5. Store the Solution : 유효한 구성이 발견되면 (퀸즈 배치) 보드 구성을 저장하십시오.
6. Repeat : 가능한 모든 구성을 시도 할 때 까지이 프로세스를 계속하십시오.

도전

보드 표현

보드는 각 셀이 'Q'또는 '인 2D 목록을 사용하여 표현할 수 있습니다.

충돌 확인

갈등을 효율적으로 점검하는 것이 중요합니다.

1. Row Check : 다른 여왕이 같은 행에 있지 않도록합니다.
2. Column Check : 같은 열에 다른 여왕이 없는지 확인하십시오.
3. Diagonal Check : 다른 퀸즈가 같은 대각선에 있지 않도록합니다.

최적화

세트를 사용하여 점유 된 열 및 대각선을 추적하면 충돌 점검 프로세스 속도가 빨라질 수 있습니다.

ThreadPooleExecutor와 동시성

더 큰 n에 대한 문제 해결을 최적화하려면 솔루션은 동시성을 ThreadPooleExecutor와 활용합니다.

• 각 스레드는 첫 번째 행에서 다른 열에 대한 문제를 해결하기 시작합니다.
• 이 병렬 접근법은 모든 솔루션을 찾는 시간을 크게 줄일 수 있습니다.

우리의 해결책

이 솔루션은 Frome Freme Free Friday 과제 중 하나가되었으며 다운 타임 중에 무작위 인터뷰 문제를 선택하여 솔루션을 작성했습니다.

설치

 pip install wolfsoftware.NQueens

용법

 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.

요약

N- 큐인 문제는 재귀, 역 추적 및 최적화 기술에 대한 깊은 이해가 필요한 매혹적이고 복잡한 도전입니다. 멀티 스레딩을 활용 하여이 구현은 주어진 보드 크기에 대한 모든 가능한 솔루션을 효율적으로 찾습니다. N- 큐인 문제를 이해하고 구현하는 것은 문제 해결 기술과 알고리즘 적 사고를 향상시키는 데 유용한 운동입니다.