N-Queens II

Hard

The n-queens puzzle places n queens on an n x n chessboard so that no two queens attack each other (no shared row, column, or diagonal). Given an integer n, return the number of distinct solutions.

Example 1

Input:  n = 4
Output: 2

Example 2

Input:  n = 1
Output: 1

Example 3

Input:  n = 8
Output: 92

Constraints

• 1 <= n <= 9