407136: GYM102697 107 The Man Machine

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

107. The Man Machinetime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Man Machine

You played against a Man Machine in chess, and because it is a superhuman being, you lost every game. Now, you're trying to practice chess so that you can beat the Man Machine.

To practice, you want to figure out how many different ways there are to place $$$N$$$ queens on an $$$N$$$ by $$$N$$$ chessboard, such that no two queens attack each other (queens can attack any number of spaces directly diagonal, left, right, up, or down). This is called the $$$N$$$-queens problem, and is a standard computer science problem involving recursion and backtracking. Your task is to implement this solution on chessboards where $$$N$$$ can be up to 9.

Input

The only line of input contains a single positive integer $$$N$$$: the size of the chessboard.

Output

Output a single positive integer $$$c$$$: the number of ways to place $$$N$$$ queens on the chessboard, such that no two queens attack each other.

ExamplesInput
8
Output
92
Input
1
Output
1
Note

If your program consists only of a lookup table with the correct values, your submission will be judged as incorrect and you may be disqualified from the contest.

加入题单

上一题 下一题 算法标签: