Practice Loops and Conditions with the exercise "n Queens"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Loops
Conditions
2D array

Statement

Goal

We have to place n queens on a chessboard made of n x n squares.
We need to place all of them in such a way that none of them is in direct contact nor attacking another one.
(meaning only one queen is occupying each line, column and diagonal)

Example with n = 4, s = 2 solutions :

- Q - -
- - - Q
Q - - -
- - Q -

and

- - Q -
Q - - -
- - - Q
- Q - -

Input

n : Number of queens (height and width of the cheessboard).

Output

s : Number of solutions.

Constraints

1 ≤ n ≤ 11

Example

Input

Output

Solve it

A higher resolution is required to access the IDE