"""Steepest-descent hill climbing: uniform starts, random best ties, no sideways moves."""
from random import Random
def conflicts(state):
    """state[column] is a zero-based row; count each attacking pair once."""
    return sum(state[a] == state[b] or abs(state[a] - state[b]) == b - a
               for a in range(len(state)) for b in range(a + 1, len(state)))
def neighbours(state):
    """For a tuple state, move one queen within its column; omit the current state."""
    for column in range(len(state)):
        for row in range(len(state)):
            if row != state[column]:
                yield state[:column] + (row,) + state[column + 1:]
def hill_climb(state, rng):
    """Return (final state, accepted moves, cost trace) for one finite attempt."""
    trace = [conflicts(state)]
    while trace[-1] != 0:
        scored = [(conflicts(other), other) for other in neighbours(state)]
        best_cost = min(score for score, _ in scored)
        if best_cost >= trace[-1]:  # Stop on a plateau as well as a local minimum.
            break
        best = [other for score, other in scored if score == best_cost]
        state = rng.choice(best)
        trace.append(best_cost)
    return state, len(trace) - 1, trace
def random_state(rng, size=8):
    return tuple(rng.randrange(size) for _ in range(size))
def experiment(trials=500, seed=1):
    """Independent attempts. A move is one accepted change, not a cost evaluation."""
    if trials < 1:
        raise ValueError('trials must be positive')
    rng = Random(seed)
    success_moves, stopped_moves = [], []
    for _ in range(trials):
        final, moves, _ = hill_climb(random_state(rng), rng)
        (success_moves if conflicts(final) == 0 else stopped_moves).append(moves)
    average = lambda values: sum(values) / len(values) if values else None
    return dict(trials=trials, seed=seed, successes=len(success_moves),
                success_rate=len(success_moves) / trials,
                mean_success_moves=average(success_moves),
                mean_stopped_moves=average(stopped_moves))
def random_restart(seed=1, max_attempts=1000):
    """Repeat independent attempts; return (solution or None, attempts, total moves)."""
    if max_attempts < 1:
        raise ValueError('max_attempts must be positive')
    rng = Random(seed)
    total_moves = 0
    for attempt in range(1, max_attempts + 1):
        final, moves, _ = hill_climb(random_state(rng), rng)
        total_moves += moves
        if conflicts(final) == 0:
            return final, attempt, total_moves
    return None, max_attempts, total_moves
def format_mean(value):
    """Readable output when a small sample has no solved or stopped attempts."""
    return "n/a" if value is None else f"{value:.2f}"
trials, seed = 1000, 1  # Change these and run again
result = experiment(trials, seed)
print(f"{trials} independent attempts; seed {seed}")
print(f"Solved: {result['success_rate']:.1%}")
print("Mean moves if solved:", format_mean(result["mean_success_moves"]))
print("Mean moves if stopped:", format_mean(result["mean_stopped_moves"]))