Project 2 -- Queen's Lament
Due: Tuesday, February 17, 2004
- To implement, compare, and contrast local search
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.
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
Which is better?
Once all three searches are working, run tests to compare the
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:
- Is one of the searches clearly more effective than another?
Why or why not?
- What value(s) of k worked best for local beam search?
Does it depend on n?
- 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
- prudent discussion of your test results in your writeup
I'm not looking for:
- mistakes or inefficiencies in the design of your code. This
isn't a programming class,
after all. However, if an error is so egregious that I catch it anyway
without even looking for it,
points may still be deducted.
Please hand in both an electronic copy of your project on
BlackBoard and a paper copy.
Programming assignments, like homework
assignments, are individual projects. I encourage you to
others about the general nature of the project and ideas about how to
However, the technical work, the writing, and the inspiration behind
be substantially your own. If any person besides you contributes in any
the project, you must credit their work on your homework. Similarly, if
include information that you have gleaned from other published sources,
cite them as references. Looking at, and/or copying, other people's
written work is inappropriate, and will be considered cheating.