N-퀸

8×8 체스판 위에 서로 공격하지 못하도록 퀸 8개를 놓는 문제는 잘 알려진 퍼즐이다. 퀸은 자신과 같은 행, 같은 열, 또는 두 대각선 위에 있는 모든 말을 공격한다.

이 문제를 일반화한 형태는 1850년에 Franz Nauck이 제기하였다.

N×N 판 위에 서로 공격하지 못하도록 퀸 N개를 놓는 방법은 몇 가지인가?

N > 3인 모든 N에 대해 그러한 배치가 적어도 하나 존재한다는 사실이 증명되어 있다. 예를 들어 N = 26일 때 배치의 수는 22317699616364044가지이다.

N이 주어졌을 때, N×N 판 위에 서로 공격하지 못하는 퀸 N개의 배치 하나를 출력하라. 유효한 배치가 매우 많을 수 있으므로, 아래 출력 설명에 정의된 특정한 배치 하나를 출력해야 한다.

첫째 줄에 정수 N이 주어진다. (4 ≤ N ≤ 100000)

N개의 줄을 출력한다. i번째 줄에는 정수 하나를 출력하며, 이는 i번째 행에 놓인 퀸의 열 번호(1 이상 N 이하)이다.

유효한 배치가 여러 가지이므로 답을 유일하게 만들기 위해, 다음 구성 방법으로 만들어지는 특정한 배치를 출력해야 한다.

E를 2, 4, 6, …과 같이 N 이하의 짝수를 오름차순으로 나열한 목록, O를 1, 3, 5, …과 같이 N 이하의 홀수를 오름차순으로 나열한 목록이라 하자. N을 6으로 나눈 나머지에 따라 두 목록을 다음과 같이 조정한다.

• N mod 6 = 2인 경우: O의 처음 두 원소를 서로 바꾼다(그러면 O는 3, 1, 5, 7, …로 시작한다). 그런 다음 O에서 값 5를 제거하여 O의 맨 뒤에 붙인다.
• N mod 6 = 3인 경우: E에서 값 2를 제거하여 E의 맨 뒤에 붙인다. 그런 다음 O에서 값 1과 3을 제거하여 그 순서대로 O의 맨 뒤에 붙인다.
• 그 외의 경우: E와 O를 그대로 둔다.

E 뒤에 O를 이어 붙이면 N개의 수로 이루어진 목록이 된다. 이 목록의 i번째 수가 i번째 행에 놓인 퀸의 열이며, 이를 i번째 줄에 출력하면 된다.