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
    otherwise
        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:

• 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()