2802ICT Programming Assignment 1
Due on: Midnight, Sunday of week 4, 22 March 2020
Mark: 15
Solving the N-Queens Problem
Background:
The n-queens problem is a fundamental coding puzzle which asks: how can N queens be placed on an NxN
chessboard so that they cannot attack each other? In chess, a queen can attack horizontally, vertically, and
diagonally across the board. Thus, to solve the n-queens problem, we must effectively figure out how to
place the queens in such a way that no two of them occupy the same row, column, or diagonal.
For further information see https://en.wikipedia.org/wiki/Eight_queens_puzzle.


For example, this is one of the (92) possible solutions for the 8-queens problem:
About the Assignment:
The assignment includes 2 parts - Part A and B. In each part you are required to implement algorithm/s and
to provide a report according to the instructions.
The algorithms should be implemented in Python/C/C++ only. Your code should be easy to follow. You will
need to put your findings and analysis in a neatly written up report.
Part A - Uninformed Search (7 marks in total):
1. Implement a program that finds ALL solutions to the N-queen problem using the Breadth-First-Search
(BFS) algorithm, for N=1 up to 20. (3 marks)
• For N=1 to 6, you need to list all the solutions.
• For N=7 to 20, returns only the number of solutions.
- Note that as the ability to run your algorithm depends on your hardware, you do not have to run the BFS
up to N=20 if it takes too long (but explain that in your report why you didn't run all the way to N=20).
2. Record the time taken to find all solutions for N=1 to 20. (1 mark)
3. Based on the results you obtained for N=1 to 20, predict the number of solutions and the time needed to
obtain the solutions for N = 30. Show how you do that clearly. (1 mark)
4. Suggest a way to prune the search tree of the BFS to speed up the computation. Contrast how this speeds
up the computation by doing a comparison study between the un-pruned and the pruned versions of your
code. For that, you should implement your pruning by modifying your code and then contrast how this
save computation time and allows you to run N to a larger number. (2 marks)
Part B - Local Search (8 marks in total):
1. Now, instead of finding ALL solutions to the N-queen problem, you should use the following types of
local search algorithms to find just ONE of the solutions to the problem:
• Hill-climbing search (3 marks)
• Simulated annealing (SA) search (3 marks)
For this part:
• You will need to decide on a cost function that decreases towards 0 as the board gets closer to a
solution.
• Verify that the solution you obtained is correct for N=1 up to 6 by visualising the result.
• You will have to visualise your initial state and final solution in an intelligible manner for N=1 up to 6.
• The N should be set to a range of values, i.e. N=1 is to K (where K is a big number at which it takes
too long for your algorithms to search for the solution). This will allow you to test the effectiveness,
and efficiency of your algorithms by recording the time it takes to find the correct solution.
2. Perform a comparative study of the two local search algorithms in finding a solution. This should include
the effect of using different parameter settings (for SA search), running time, and anything else you
could think of (2 marks)
What to hand in:
You should hand in the following in one zip file:
1. Your (well commented) source code.
2. A standalone executable file (that is runnable in a windows environment). If you are using Python, you
can just submit your *.py file.
3. A detailed report explaining your algorithms and experimental results.
Submission should be done through the link provided in L@G by the due date.
NOTE: You might be asked to present (“defend”) your work in an one-on-one meeting with one of the
course staff.
About collaboration/plagiarism:
You are encouraged to discuss the assignment with your fellow students, but eventually this should be your
own work. Anyone caught plagiarising will be penalised.
Good luck and enjoy