AI: Hill climbing for N queens

Run steepest-descent hill climbing and watch it succeed or get stuck.

What to build

A program that improves an N-queens placement by moving one queen at a time.

Requirements

  • Each step: among all moves of one queen to another column of its row, take the one that leaves the fewest attacking pairs (ties: smallest row, then smallest column), but only if it is fewer than now. Stop when no move improves.
  • Print each move as row R -> column C, attacking pairs K, then solved in S steps or stuck after S steps with K attacking pairs.

Input

Line 1: n. Line 2: the starting column of each row's queen.

Output

One line per move, then the result.

Constraints

n ≤ 10.

Example

Input:

4
0 0 0 0

Output:

row 1 -> column 3, attacking pairs 3
row 0 -> column 1, attacking pairs 1
row 3 -> column 2, attacking pairs 0
solved in 3 steps

Why it works

Each step makes the greatest immediate improvement, which is fast, but a state where no single move helps stops the climb even if it is not a solution.

Examples

Example 1 · Input
4
0 0 0 0
Expected output
row 1 -> column 3, attacking pairs 3
row 0 -> column 1, attacking pairs 1
row 3 -> column 2, attacking pairs 0
solved in 3 steps
Example 2 · Input
4
1 3 0 2
Expected output
solved in 0 steps

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

Hints

Hint 1

At each step, score every move of one queen to another column in its row, and keep the best.

Hint 2

Scan rows from 0 and columns from 0, and replace the best move only when a move is strictly better, so ties go to the first one.

Solution

Show one correct solution (try it yourself first)
def pairs(cols):
    n = len(cols)
    return sum(1 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)


n = int(input())
cols = list(map(int, input().split()))
steps = 0
while True:
    current = pairs(cols)
    best, move = current, None
    for row in range(n):
        for col in range(n):
            if col != cols[row]:
                score = pairs(cols[:row] + [col] + cols[row + 1:])
                if score < best:
                    best, move = score, (row, col)
    if move is None:
        break
    cols[move[0]] = move[1]
    steps += 1
    print(f"row {move[0]} -> column {move[1]}, attacking pairs {best}")
if current == 0:
    print(f"solved in {steps} steps")
else:
    print(f"stuck after {steps} steps with {current} attacking pairs")

Lesson: Local search and optimization →