Simulated annealing in N-queens

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(initial solution)
let solution be initial
let t be an initial temperature
until t is almost zero
    let neighbor be a random neighbor of solution
    if the cost of neighbor is less than the cost of solution
        let solution be neighbor
        stop if the cost is now 0
        let c be the cost increase
        compute p = e^(-c/t)
        with probability p, let solution be neighbor
    multiply t by a decay rate
return solution

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:

Parameter notes:

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',
                    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)
    agent = Agent()
    path = agent.anneal(board)
    while path:
        move = path.pop(0)
        board = board.neighbor(move)

if __name__ == '__main__':