EIU Programming Practices and Exams

The classic N-Queens problem asks to place N queens on an N×N chessboard such that no two queens can attack each other. This extended version requires you to find as many fundamentally different valid solutions as possible within a time limit.

Important: Two solutions are considered identical if one can be obtained from the other through any combination of rotations (90°, 180°, 270°) and reflections (vertical, horizontal, diagonal). Only unique canonical solutions should be output.

Task

Given an N×N chessboard where rows and columns are numbered from 1 to N, place N queens such that:

• No two queens are in the same row
• No two queens are in the same column
• No two queens are on the same diagonal

Your program should output as many fundamentally different valid solutions as possible within 2 seconds, up to a maximum of 10,000 solutions.

Input

A single integer N (4 ≤ N ≤ 1000) representing the size of the chessboard.

Output

At most 10,000 lines, each representing one unique canonical solution. Each line contains 2N integers where the numbers at positions (2i-1) and (2i) represent the row and column of the i-th queen respectively.

Queens should be numbered from 1 to N in the output.

Note: Among all symmetric variants of a solution, output only the lexicographically smallest one when queens are listed row by row.

Example

Input:

8

Output:

1 1 5 2 8 3 6 4 3 5 7 6 2 7 4 8
1 1 6 2 8 3 3 4 7 5 4 6 2 7 5 8
1 1 7 2 4 3 6 4 8 5 2 6 5 7 3 8
...
(up to 10,000 unique solutions)

Explanation:

• Each line represents one unique canonical solution
• First solution: Queen 1 at (1,1), Queen 2 at (5,2), Queen 3 at (8,3), etc.
• All solutions are fundamentally different (not symmetric variants of each other)

Symmetric Transformations (Considered Identical)

Two solutions are identical if one can be obtained from the other via:

1. Rotations: 90°, 180°, 270° clockwise
2. Reflections:
   • Vertical (left-right mirror)
   • Horizontal (top-bottom mirror)
   • Main diagonal (transpose)
   • Anti-diagonal

Scoring System

Per Line Scoring:

• +1 point for each correct unique canonical solution
• -1 point for each incorrect line (invalid solution, duplicate, or malformed)

Per Test Case:

• Score = (Points Earned) / (Maximum Possible Points)
• Range: [0.0, 1.0] (can be negative if too many errors)
• Maximum Possible Points = min(10,000, Total Unique Solutions for N)

Final Score:

• Final Score = (Sum of all test case scores) / (Number of test cases) × 100%
• This gives a percentage representing overall performance across all test cases

Constraints

• 4 ≤ N ≤ 1000
• Time limit: 2 seconds
• Memory limit: 256 MB
• Output limit: 10,000 lines maximum

Notes

• Solutions can be output in any order
• Each solution should be on a separate line
• Invalid solutions or duplicate symmetric variants will result in penalty
• Partial solutions (incomplete lines) will be ignored
• Program should terminate cleanly within time limit