# Solution to the <i>n</i> Queens Puzzle

Time Limit: 1000MS

Memory Limit: 131072K

## Description

The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitrary *n* × *n* boards. Given *n*, you are to find a solution to the *n* queens puzzle.
## Output

For each test case, output your solution on one line. The solution is a permutation of {1, 2, …, *n*}. The number in the *i*th place means the *i*th-column queen in placed in the row with that number.