AI: Count attacking queens

Write the objective function for the N-queens problem.

What to build

A program that counts how many pairs of queens attack each other.

Requirements

  • There is one queen per row; the input gives each row's column, counted from 0.
  • Print the number of attacking pairs (same column or same diagonal).

Input

Line 1: n. Line 2: n columns.

Output

One number.

Constraints

n ≤ 100.

Example

Input:

4
1 3 0 2

Output:

0

Why it works

A solution is exactly a placement with zero attacking pairs, so this count tells a local search how close it is.

Examples

Example 1 · Input
4
1 3 0 2
Expected output
0
Example 2 · Input
4
0 0 0 0
Expected output
6

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Check every pair of rows a < b once.

Hint 2

Two queens attack each other if they share a column or if their column difference equals their row difference.

Solution

Show one correct solution (try it yourself first)
n = int(input())
cols = list(map(int, input().split()))
pairs = 0
for a in range(n):
    for b in range(a + 1, n):
        if cols[a] == cols[b] or abs(cols[a] - cols[b]) == b - a:
            pairs += 1
print(pairs)

Lesson: Local search and optimization →