Please be careful not to post spoilers to discussion forum. Please don't post any code that
is directly related to the assignments. However you are welcome and encouraged to
discuss general ideas on the discussion forums.
Grading
We will use an autograder to grade your program, please read the instructions in this
document carefully to make sure that your program will pass the autograder.
The evaluation function in the VPL will test your code for the minimum requirement. Your
code must at least pass the test in the evaluation to get marks.
The correctness of your implementation -- not the autograder's judgements -- will be the
final judge of your score. If necessary, we will review and grade assignments individually to
ensure that you receive due credit for your work.
We will test your program with additional test cases apart from those included in the
evaluation function.
Sandbox
1. A special sandbox is provided for this assignment, you could test your assignment code in
the Sandbox while keeping your work in the assignment VPLs.
2. The sandbox VPL will execute the main() function in your code when you click on the
Run button
!
. The same will happen in all other VPLs in the assignment.
3. Click here to access the
sandbox.
Question 1: Local search (10%)
Overview
We have discussed the 8-queen problem in the lecture. In this question, you are asked to
implement a solver that solve the generalized n-queen problem using the local search
technique.
You should write your program in this VPL
id=1115849).
When you first use the VPL, you should see these code:
# Put your testing code here
# This function will be executed when you run your program on VPL
# This function will not be graded
Function main() is only used for testing and will not be graded. You should test your
program by writing code in this main() function.
You can always copy-and-paste your code to the assignment sandbox to test your idea while
keeping your work in the assignment VPL.
The other functions are specific to the tasks in the assignment. You will implement them
when you do your assignment. Do not remove or rename these functions, and do not change
the list of parameters. However, you should replace the existing code in each of the these
functions with your own code.
You can add any other functions.
# This function will not be graded
def main():
print("nothing done.")
#Task 1.1
def countAttack(queen):
return 0
#Task 1.2
def getNext(queen):
bestQueen = list(queen)
return tuple(bestQueen)
#Task 1.3
def solve(queen, n):
solution = list(queen)
return tuple(solution)
Introducing our queen representation
1. To solve for the n-queen problem, we start from an initial state and try to move one queen
at a time.
2. As our target is to find a configuration that no pairs of queen are on the same row, column
and diagonal line, we can limit our initial state to have one queen in each row and allow
only horizontal movement for each queen.
3. For example, one possible initial state for a 4-queen problem will be:
4. Since we have only one queen in each row, we can use a tuple of 4 numbers, (0, 0,
0, 0) to represent the above initial state, where each value represents the horizontal
position of the queen in a row.
5. Using this representation, (0, 1, 2, 3) represents the configuration of:
and (2, 0, 3, 1) represents the configuration of:
which is one of the possible solution to a 4-queen problem.
6. Larger board can be represented with a longer list, so for example, (0, 1, 2, 3,
0, 1, 2, 3) represents the board:
7. To help visualizing the above representation, we can write a simple function to help
printing the list as a board.
You are encouraged to make use of this function in testing your code, or even modify it for
your own purpose.
def printBoard(queen):
for n in queen:
print("- "*n+"Q"+" -"*(len(queen)-n-1))
Task 1-1: Attack count (1%)
Before we can solve the n-queen problem, we need a way to evaluate the board.
Evaluation allow us to compare two boards and pick one that is closer to the solution.
For n-queen problem, we can count the number of attacking pairs.
Consider the board (0, 2, 3, 1):
only the queen at row 2 and 3 will attack each others, so the number of attacking pairs is 1.
Consider the board (0, 0, 2, 3):
the attacking pairs are (0, 1), (0, 2), (0, 3), and (2, 3), so the number of attacking pairs is 4.
Needless to say, the number of attacking pairs is zero for any solution of the n-queen
problem.
In this task, you will complete the function countAttack(), so that it takes one
parameter, queen, which represents a n-queen configuration as described above, and
return the corresponding number of attacking pairs.
For example, if the input queen is the tuple (0, 0, 2, 3), the function should
return the value 4.
You can use the main() function to test your code. For example:
should produce the output of:
Note the use of printBoard() function.
There is no need to validate the input, you can assume that the input list queen will
only consist of non-negative integer that is less than the size of the list itself.
The input queen is a tuple, so your function should not modify the content of queen.
def main():
queen = (0, 0, 2, 3)
count = countAttack(queen)
print("Board:")
printBoard(queen)
print("count:", count)
9/11/2017 å 11(54ENGG1202 Assignment 2
Task 1-2: Get next best move (2%)
Consider the board (0, 0, 0, 0), we have 12 possible moves, which produce 12
different boards.
If we count the number of attacking pairs of these 12 boards, we have:
(1, 0, 0, 0): 4
(2, 0, 0, 0): 4
(3, 0, 0, 0): 4
(0, 1, 0, 0): 5
(0, 2, 0, 0): 4
(0, 3, 0, 0): 3
(0, 0, 1, 0): 5
(0, 0, 2, 0): 4
(0, 0, 3, 0): 3
(0, 0, 0, 1): 4
(0, 0, 0, 2): 4
(0, 0, 0, 3): 4
We can see that by moving the queen at row 1 or 2 to position 3, we will get the smallest
attacking count among the 12 possible moves.
In this task, you will complete the function getNext(), which takes one parameter
queen that represent a board, so that it returns the board with the minimum number
of attacking pairs after moving one queen.
For example, if the input queen is the list (0, 0, 0, 0), the function should
return either (0, 3, 0, 0) or (0, 0, 3, 0).
You can use the main() function to test your code. For example:
which gives the output of:
def main():
queen = (0, 0, 0, 0)
next = getNext(queen)
print("Original:")
print(queen)
print("Next:")
print(next)
Original:
(0, 0, 0, 0)
New:
(0, 3, 0, 0)
or any other best move.
The function should return one of the 12 possible moves as a result, even if the move does
not reduce the number of attacking pairs.
There is no need to validate the input, you can assume that the input list queen will
only consist of non-negative integer that is less than the size of the list itself.
The input queen is a tuple, so your function should not modify the content of queen.
Task 1-3: Solving n-queen (1%)
With task 1-1 and 1-2 completed, we can solve the n-queen problem using a local search
approach.
Starting from an initial board, we do the following:
1. Check if the current board is a solution, if yes, return it.
2. If not, find the best next state if we move only one queen. Repeat from step 1.
For example, if we start from the board (0, 0, 0, 0), the search may goes from
the initial board to (0, 3, 0 ,0), then to (1, 3, 0 ,0), then (1, 3, 0,
2) which is a solution.
In this task, you will complete the function solve(), which takes two parameters,
queen the initial state, and n the maximum number of moves, so that it returns the
list of board reaching a solution starting from the initial state.
For example, if the input queen is the list (0, 0, 0, 0), the function may return
the list of states: [(0, 0, 0, 0), (0, 3, 0, 0), (1, 3, 0, 0), (1,
3, 0, 2)].
The function should only return a list of at most n items plus the initial state, even if a
solution is not found.
You can use the main() function to test your code. For example:
will produce the output of:
Your code may not produce the same result, your implementation is consider correct if:
You pick the next best move from the previous state.
The number of moves (excluding the initial state) returned does not exceed n.
There is no need to validate the input, you can assume that the input list queen will
only consist of non-negative integer that is less than the size of the list itself; and the input
n is always a positive integer.
The input queen is a tuple, so your function should not modify the content of queen.
Task 1-4: Written questions on local search (6%)
This is a written question. You should submit your work through Turnitin
(http://moodle.hku.hk/mod/turnitintooltwo/view.php?id=1115851). Make sure you are
submitting to the correct task.
In this part, you should answer the following questions about the n-queen problem and
the local search method. You are advised to use the sandbox to do some of the
computation required.
1. Consider the example shown in task 1-2, where we try to move one queen from the
initial state of (0, 0, 0, 0), giving us the 12 possible results:
(1, 0, 0, 0): 4
(2, 0, 0, 0): 4
(3, 0, 0, 0): 4
(0, 1, 0, 0): 5
(0, 2, 0, 0): 4
(0, 3, 0, 0): 3
(0, 0, 1, 0): 5
(0, 0, 2, 0): 4
(0, 0, 3, 0): 3
(0, 0, 0, 1): 4
(0, 0, 0, 2): 4
(0, 0, 0, 3): 4
If we put these numbers on the board, at the position where the queen was moved
to, the result will be:
- 4 4 4
- 5 4 3
- 5 4 3
- 4 4 4
Let's call this the attack matrix. Suppose the initial state is generated from the first
10 digits of your student number, for example, if your student number is
3035123456, the initial board will be (3, 0, 3, 5, 1, 2, 3, 4, 5,
6). Construct the attack matrix of your initial state.
2. Find an initial state of any size that will never be solved by solve() no matter
how big n is. Explain why it is the case.
3. Suggest one change to our local search method that can resolve the problem in part
2. Your suggestion does not need to garauntee that solve() will find a solution.
There is no need to implement your suggested change.
4. We have discussed the topic of uninformed search algorithms in lecture, which of
the algorithms is the most similar to the local search method presented in this
question? Explain your answer.
Question 2: Slider puzzles (10%)
Overview
We have explained a number of searching algorithms in the lecture. In this question you will
be implementing the A* tree search algorithm to solve a slider puzzle.
You should write your program in this VPL
id=1115850).
When you first use the VPL, you should see these code:
Function main() is only used for testing and will not be graded. You should test your
program by writing code in this main() function.
# Put your testing code here
# This function will be executed when you run your program on VPL
# This function will not be graded
def main():
print("nothing done.")
#Task 2.1
def evaluate(puzzle):
return 0
#Task 2.2
def applyMove(puzzle, move):
newPuzzle = list(puzzle)
return tuple(newPuzzle)
#Task 2.3
def astarTSA(puzzle):
moves = []
return moves
program by writing code in this main() function.
You can always copy-and-paste your code to the assignment sandbox to test your idea while
keeping your work in the assignment VPL.
The other functions are specific to the tasks in the assignment. You will implement them
when you do your assignment. Do not remove or rename these functions, and do not change
the list of parameters. However, you should replace the existing code in each of the these
functions with your own code.
You can add any other functions.
Introducing our puzzle representation
1. Our slider puzzle is a matrix of slots filled with tiles, and so there is always an
empty slot inside. Each tile is labeled with a number from to . In this assignment, we
will assume that the solved state of such puzzle will have the empty slot at the top-left
corner, and the numbered tiles are placed in a row-major manner.
2. This is the terminal state of a slider puzzle:
- 1 2
3 4 5
6 7 8
3. To model this puzzle in Python, we can use a tuple to hold the tile numbers from top to
bottom, left to right. We use 0 to represent an empty slot. So for the above terminal state,
we use the tuple (0, 1, 2, 3, 4, 5, 6, 7, 8) to represent it.
4. To help visualizing the above representation, we can write a simple function to help
printing the list as a puzzle.
You are encouraged to make use of this function in testing your code, or even modify it for
your own purpose.
3×3 8
1 8
1
2
3
4
5
def printPuzzle(puzzle):
for i in range(3):
for j in range(3):
print(puzzle[i*3+j], end=' ')
print()
Task 2-1: Evaluate puzzle (1%)
With any puzzle state, we want to evaluate how close the puzzle is to the terminal state. In
this assignment, we use the heuristic of the sum of mahattan distance of each of the tiles
to their position in the terminal state.
For example, the puzzle state below consists of 3 tiles that is not in their position in
For example, the puzzle state below consists of 3 tiles that is not in their position in
terminal state.
1 4 2
The heuristic will be 3 as the tile 1, 3 and 4 are 1 distance apart from their terminal
position.
In this task, you will complete the function evaluate(), which takes one parameter,
puzzle a puzzle state, so that it calculate the heuristic as described above.
For example, if input is (1, 4, 2, 0, 3, 5, 6, 7, 8), the function should
return 3.
You can use the main() function to test your code. For example:
should print:
Note the use of printPuzzle() function.
There is no need to validate the input, you can assume that the input value puzzle is
# expand the node adding the resulting nodes to the frontier
moves = astarTSA(puzzle)
print("Puzzle:")
printPuzzle(puzzle)
print("Solution:")
print(moves)
Task 2-4: Written question on uniformed search (5%)
This is a written question. You should submit your work through Turnitin.Make sure you are submitting to the
correct task.
In this part, you should answer the following questions about the slider puzzle and the A* search methods.
You are advised to use the sandbox to do some of the computation required.
1. Copy the following code to the sandbox, input your student number and record the result, which is a
slider puzzle.
(Code modified 2017-11-03)
2. Using the result in the previous part as the initial state, what are the nodes in the frontier after the
initial state is explored? (Assuming that we skip checking for the terminal state)
3. Suppose A* search is used, among the nodes in part 2, which node will be picked? Show the slider
puzzles corresponding to the nodes and the result of computation that is involved.
4. Explore the node and update the frontier, what are the nodes in the frontier now? (Again, assume
that we skip checking for the terminal state)
5. Now again, suppose A* search is used, among the nodes in part 4, which node will be picked? Show
the slider puzzles corresponding to the nodes and the result of computation that is involved.
6. Jenny suggests that, instead of using evaluate() as heuristic, we can simply count the number
of different values in the puzzle state with that in the terminal state. For example, in the puzzle state:
the highlighted slots are different from the terminal state, and thus the heuristic for this puzzle is 7.
Is this heuristic function admissible? Explain your answer.
7. To show that you are using A* search in your code, explain clear how you have implemented the part
"choose a leaf node and remove it from frontier" to pick the next node in the frontier in your
astarTSA() function. (Your answer to this question will contribute marks in task 2-3 instead.
You may not get any marks in Task 2-3 if you failed to answer this question.)