The N-queens problem is to place N queens on an N-by-N chess board so that none are in the same row, the same column, or the same diagonal. For example, if N=4, this is a solution:

The goal of this assignment is to solve the N-queens problem using simulated annealing.

Here is the simulated annealing algorithm:

simulated-annealing(letinitialsolution)solutionbeinitiallettbe an initial temperature untiltis almost zero letneighborbe a random neighbor ofsolutionif the cost ofneighboris less than the cost ofsolutionletsolutionbeneighborstop if the cost is now 0 otherwise letcbe the cost increase computep= e^(-c/t) with probabilityp, letsolutionbeneighbormultiplytby a decay rate returnsolution

A Board class and an Agent class have been started for you below. Once you complete the indicated methods, you will be able to watch a random initial solution being annealed. Adjust the height of your console window to match the board height, so that each display appears in the same place.

**Algorithm notes:**

- You will need to decide on a cost function that decreases towards 0 as the board gets closer to a solution.
- You will also need to decide what types of moves to allow and how to represent them.
- Finally, you will need to keep track of the sequence of moves taken during the annealing process.

**Parameter notes:**

- You may need to try a few values for the initial temperature (e.g. 1, 10, 100), the stopping threshold (e.g. 0.1, 0.01, 0.001), and the decay rate (e.g. 0.9, 0.99, 0.999) to find an effective combination.

import time import random class Board(object): """An N-queens solution attempt.""" def __init__(self, queens): """Instances differ by their queen placements.""" self.queens = queens.copy() # No aliasing! def display(self): """Print the board.""" for r in range(len(self.queens)): for c in range(len(self.queens)): if self.queens[c] == r: print 'Q', else: print '-', print print def moves(self): """Return a list of possible moves given the current placements.""" # YOU FILL THIS IN def neighbor(self, move): """Return a Board instance like this one but with one move made.""" # YOU FILL THIS IN def cost(self): """Compute the cost of this solution.""" # YOU FILL THIS IN class Agent(object): """Knows how to solve an n-queens problem with simulated annealing.""" def anneal(self, board): """Return a list of moves to adjust queen placements.""" # YOU FILL THIS IN def main(): """Create a problem, solve it with simulated anealing, and console-animate.""" queens = dict() for col in range(8): row = random.choice(range(8)) queens[col] = row board = Board(queens) board.display() agent = Agent() path = agent.anneal(board) while path: move = path.pop(0) board = board.neighbor(move) time.sleep(0.1) board.display() if __name__ == '__main__': main()