407136: GYM102697 107 The Man Machine

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.

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

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.

8

92

1

1

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.