# CSc 244

## Project 2 -- Queen's Lament Due: Tuesday, February 17, 2004

### Objectives

• To implement, compare, and contrast local search algorithms

In this project, you'll apply several local search algorithms to the n-queens problem, where you try to place n queens on an n X n chessboard in such a way that no pair are in the same row, the same column, or the same diagonal. In class, we saw how several local searches could be implemented for a specific n, say n=4 or n=8. You'll be testing your code to see how well the algorithms perform over a wide range of n.

### The Details

You are to implement the following local searches:
• Hill climbing with random restart.
• Simulated annealing. You will have to come up with a suitable way of mapping time to temperature.
• Local beam search. You may experiment with the value of k=the number of states you keep in memory

For the purposes of this project, we will say that a valid state is any chessboard where there is 1 queen per column. That way, you can use the same successor function that we used in class; namely, that a single queen can move anywhere in her own column.

For each search, your agent should be able to take a size n as input (the size of the board). It should then be able to create an initial random valid state and use the search to locate the goal. Your agent should then output the number of moves it took to reach it. Note that for local beam, there will be k moves per generation.

### Which is better?

Once all three searches are working, run tests to compare the effectiveness of the three algorithms for various n. To do this, start n at a small number (4 is good), set a fixed k for local beam, and find out the average number of moves it takes for the three searches to find the goal at that n. (You should run each search a fixed number of times to find an average.) Then, increase n by a predetermined amount and repeat. Remember, as n goes up, your algorithms may get "stuck" on local maxima/minima. Hill climbing may keep restarting, simulated annealing may stay in a current state seemingly forever if the probability of accepting a worse state gets really low, and local beam may not get enough diversity in its states to break out of local maxima/minima if k is picked badly. So you should also have a way of stopping the search in case it takes too long (say, 1 minute). We'll call that a failure. Once you've reached an n where failures are common, you should stop. That probably won't happen on all the searches, though. Run the experiment on enough values of n to be able to estimate its general behavior.

Once you've collected your data, display the results as a graph with n on the horizontal axis and the average number of moves on the vertical axis. Answer the following in your write-up:

1. Is one of the searches clearly more effective than another? Why or why not?
2. What value(s) of k worked best for local beam search? Does it depend on n?
3. What temperature mapping(s) worked best for simulated annealing? Does it depend on n?

This project is worth 50 points. I'm looking for:
• correct implementations of your search algorithms