Royal Placement Count (Hard) — Practice with Code Visualizer

You are a royal strategist tasked with arranging n royal guards on an n × n grid-based fortress courtyard. Each guard has a unique ability to patrol their entire row, column, and both diagonals simultaneously. Because of their territorial nature, no two guards can share the same patrolling zone—meaning no two guards can be placed in the same row, column, or diagonal.

Your mission is to determine the total number of distinct valid arrangements where all n guards can be placed on the courtyard without any two guards threatening each other's patrol zones.

A valid arrangement ensures that:

Each row contains exactly one guard
Each column contains exactly one guard
No two guards share the same diagonal (both ascending and descending diagonals)

Given the integer n representing the size of the fortress courtyard, return the count of all distinct valid placements.

For a 4×4 courtyard, there are exactly 2 distinct ways to place 4 guards such that none of them threaten each other. The guards can be placed at positions: (1,2), (2,4), (3,1), (4,3) or (1,3), (2,1), (3,4), (4,2) where coordinates are (row, column).

With only a single cell in the 1×1 courtyard, there is exactly one way to place the single guard—at the only available position.

For a 5×5 courtyard, there are exactly 10 distinct valid arrangements where 5 guards can be placed without any mutual conflicts.