COMP2611 COURSEWORK 1 (10% of module)
Coursework issued: 24 Feb 2021 8:00 AM
Submission deadline: 17 March 2021 8:00 AM
To be submitted via Gradescope
General Overview
In this coursework you will produce a representation of a problem that can
be used with the implementation of search algorithms that you have been
experimenting with in the lab sessions.
The Problem
We have seen the 8 queens problem, which asks for an arrangement of 8
queens on an 8 × 8 chess board so that no two of them can take each other.
That is, no two of the queens can be in the same column, or in the same row,
or in the same 45 degree diagonal line. We have also mentioned the problem
of placing n queens on an n × n board.
In this coursework the problem is given an m × n board, where m and n
are any integers greater than zero, to find the smallest number of queens that
cover all the squares on the board. That is, to find the minimum number of
queens which can be placed in such a way that every square on the board
either has a queen on it, or is in the same column, or in the same row, or in the
same 45 degree diagonal line (in any direction) as at least one queen. Unlike
the 8 queens problem, there is no requirement about queens threatening each
other.
Your solution must use the implementation of search provided in the files
queue_search.py and tree.py as seen in the lab exercises.
You hand in one Python file and nothing else
• A file called queen-cover.py containing the problem representation.
You can base the overall structure on the examples of the knights tour,
the eight puzzle, and the lab exercises which you have already studied.
There are some comments in queen-cover.py to explain this Python
script, you just need to implement two functions qc_successor_state
and qc_successor_state in queen-cover.py.
It is essential that the representation works with the code in queue_search.py
and tree.py without making any changes at all to these files. Do not
submit these two files. Your solution will be tested using the versions
of these files provided on Gradescope.
• Do not rename the queen-cover.py file and any function in the file.
• Submission is be via Gradescope.
• Your code will be tested using the version of Python 3.6+ on the Linux
computers in the Gradescope. If you develop it under a different version, check that this does not cause problems.
Test File
• We will provide you a test file called qc_tester.py which could be
used to evaluate your code (all the tests should work with your code
in reasonable time). If the search algorithm is reporting more than
60 seconds that would count as unreasonable for that test; you should
expect very much less for many of them. Your coursework will not be
marked on how fast the tests run provided it is not unreasonable.
• Do not submit the qc_tester.py file, it is just for your test.
Note that this runs uniform cost search by providing a constantly zero
heuristic to A* search and the cost function used is the length of the path in
the search tree.
import sys
from tree import *
from queue_search import *
from queen_cover import *
def zero_heuristic(state):
return 0
search(make_qc_problem(1,1), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(3,3), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(4,4), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(5,5), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(5,6), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(6,5), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(10,3), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(3,4), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(4,7), (’A_star’, zero_heuristic), 5000, [])
search(make_qc_problem(2,50), (’A_star’, zero_heuristic), 5000, [])
Marking scheme (total available: 100)
• No score for submitted file with different name (just queen-cover.py).
• No score for similar codes.
• Code runs and works on all examples in the test file, producing a correct
solution in each case. (50)
• Sucessor state function (40)
• Test for goal state (10)
To get full marks there should be a few appropriate comments in the code
but not excessively long.