N-Queens Problem

N-Queens Problem

Place N queens on an N x N chessboard so that no two queens attack each other, and return all solutions.

Input format

A single integer N (1 ≤ N ≤ 8).

Output format

Print every solution on its own line as N space-separated column indices (0-based), where the i-th number is the column of the queen in row i. Sort the lines lexicographically as strings. If there is no solution, print -1.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

4

1 3 0 2
2 0 3 1

1

0