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, thensolved in S stepsorstuck 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")