To solve this problem, we need to determine the maximum number of points that can be marked on an N×N grid such that no two points are in the same row, column, or diagonal. This problem is equivalent to finding the maximum number of non-attacking queens on an N×N chessboard.
Approach
The key insight here is based on the N-Queens problem, which is a classic combinatorial optimization problem. The solution to the N-Queens problem (placing N queens such that no two attack each other) exists for all N except N=2 and N=3.
The maximum number of points (queens) we can place is:
- 1 if N=1 or N=2 (since no valid placement of 2 queens exists for N=2).
- 2 if N=3 (since no valid placement of 3 queens exists for N=3, but we can place 2).
- N for all N≥4 (since a valid placement of N queens exists).
Solution Code
n = int(input())
if n == 1:
print(1)
elif n == 2:
print(1)
elif n == 3:
print(2)
else:
print(n)
Explanation
- N=1: Only one cell exists, so we can mark it.
- N=2: No way to place two points without them being in the same row, column, or diagonal, so maximum is 1.
- N=3: No valid placement of three points exists, but we can place two points (e.g., (0,0) and (1,2)).
- N≥4: A valid placement of N points (queens) exists, so the maximum is N.
This approach efficiently computes the result in constant time O(1) since it uses simple conditional checks. The solution leverages known results from the N-Queens problem to directly get the answer.


作者声明:本文包含人工智能生成内容。