#! /usr/bin/env python3
"""Note: unlike the course slides, the rows and columns (ranks and
files) of the puzzle are counted as {0, ..., N - 1} here (rather than
starting from 1) because this is the more common convention in
programming.
This is not an efficient implementation, as it is meant to be easy to
understand.
The code does not follow the pseudo-code in the lecture 100% due to
the need to gather statistics.
Note that the code is not fully generic in the way that state-space
search code is. Some of the assumptions about the problem are baked
directly into the algorithms, for example the fact that we are dealing
with a minimization problem.
"""
import random
def get_random_candidate(board_size):
return [random.randrange(board_size) for _ in range(board_size)]
def get_minimum(choices):
# Ties are broken uniformly randomly. Note that tie-breaking can
# have a large impact on performance in COPs.
min_h = min(h(candidate) for candidate in choices)
return random.choice([candidate for candidate in choices
if h(candidate) == min_h])
def get_number_of_conflicts(candidate):
num_conflicts = 0
size = len(candidate)
for index1, row1 in enumerate(candidate):
for index2 in range(index1 + 1, size):
row2 = candidate[index2]
if row1 == row2 or abs(row2 - row1) == index2 - index1:
num_conflicts += 1
return num_conflicts
def is_solution(candidate):
return get_number_of_conflicts(candidate) == 0
def get_neighbors(candidate):
neighbors = []
size = len(candidate)
for index, row in enumerate(candidate):
for new_row in range(size):
if row != new_row:
neighbor = list(candidate)
neighbor[index] = new_row
neighbors.append(neighbor)
return neighbors
def h(candidate):
return get_number_of_conflicts(candidate)
def simple_hill_climbing_with_stagnation(board_size, max_steps):
current = get_random_candidate(board_size)
num_steps = 0
best = current
for _ in range(max_steps):
next = get_minimum(get_neighbors(current))
current = next
num_steps += 1
if h(current) < h(best):
best = current
if h(current) == 0:
break
solved = is_solution(best)
return solved, num_steps
def main(board_size, num_trials, max_steps):
num_solved = 0
total_steps = 0
for trial in range(1, num_trials + 1):
if trial % 100 == 0:
print("trial {} out of {}...".format(trial, num_trials))
solved, num_steps = simple_hill_climbing_with_stagnation(
board_size=board_size, max_steps=max_steps)
num_solved += int(solved)
total_steps += num_steps
print("{} out of {} trials solved ({}%)".format(
num_solved, num_trials, 100.0 * num_solved / num_trials))
print("average number of steps: {}".format(
total_steps / num_trials))
if __name__ == "__main__":
main(board_size=8, num_trials=10000, max_steps=100)