# 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()
```