순열과 N-Queens 발상

순열은 모든 요소를 어떤 순서로 배열한 것입니다. 순열 생성은 부분집합 다음에 배우는 백트래킹 기술입니다. 🔀

n개의 항목으로 만들 수 있는 순열은 n 팩토리얼개입니다. 첫 번째 위치에는 n가지, 다음 위치에는 n-1가지 선택이 있고 이런 방식이 계속되기 때문입니다. 개수는 빠르게 증가합니다.

재귀는 위치를 왼쪽에서 오른쪽으로 채웁니다. 각 단계에서 사용하지 않은 요소를 하나 골라 배치하고, 나머지 요소에 대해 재귀 호출을 합니다.

불리언 사용 여부 배열은 이미 배치된 요소를 표시하므로, 모든 순열에서 각 요소가 정확히 한 번씩 나타납니다.

이 백트래킹은 사용하지 않은 값을 배치하고 재귀 호출을 한 다음, 다음 분기에서 사용할 수 있도록 해당 값을 다시 해제합니다.

빠르게 문제를 풀어야 할 때는 Python의 itertools.permutations가 직접 재귀를 작성하지 않아도 모든 순서를 생성해 줍니다.

N-퀸 문제는 서로 공격할 수 없도록 n × n 체스판에 n개의 퀸을 배치하는 문제입니다. 고전적인 백트래킹 퍼즐입니다. 👑

두 퀸이 같은 행을 공유하지 않으므로 행마다 퀸 하나를 정확히 배치하고 열만 선택하면 됩니다. 이렇게 하면 탐색 범위가 크게 줄어듭니다.

배치하기 전에 이미 사용된 열이나 대각선이라면 거부합니다. 집합을 사용하여 사용된 열과 두 방향의 대각선을 추적합니다.

어떤 열도 한 행에 배치할 수 없다면 해당 분기는 실패합니다. 백트래킹하여 마지막 퀸을 제거하고 다음 선택지를 시도합니다.

순열과 N-퀸 문제에는 선택하고, 재귀 호출하고, 되돌리는 하나의 공통 구조가 있습니다. 이 구조를 이해하면 대부분의 배치 퍼즐에 같은 틀을 적용할 수 있습니다.

사용하지 않은 항목을 배치하여 순열을 생성하고, N-퀸 문제도 충돌 확인과 함께 같은 선택-재귀 호출-되돌리기 패턴을 사용한다는 것을 배웠습니다. 🎯