7301 : 재귀 마스터
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 7
•통과: 7
•만든사람: suakii
문제 설명
$N \times N$ 체스판에 $N$개의 퀸을 서로 공격하지 않도록 배치하는 경우의 수를 구하십시오(N-Queens 문제).
백트래킹으로 구현합니다: 각 행에 하나의 퀸을 배치하고, 열 및 대각선 충돌을 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
백트래킹으로 구현합니다: 각 행에 하나의 퀸을 배치하고, 열 및 대각선 충돌을 검사합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 $N$이 주어집니다. ($1 \le N \le 10$)
출력 설명
$N$-Queens 문제의 해의 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
92도움
열 집합, 두 대각선 집합을 관리합니다.
def place(row): if row==N: count+=1; return; for col in range(N): if col not in cols and (row-col) not in d1 and (row+col) not in d2: cols.add(col); ...; place(row+1); ...