MCD4710算法分析算法

MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Objectives
The objectives of this assignment are:
● To gain experience in designing algorithms for a given problem description and implementing those algorithms in
Python.
● To demonstrate your understanding on:
o Implementing problem solving strategies
o Recognizing the relationship between a problem description and program design
o Decomposing code into functions in Python.
Submission Procedure
Your assignment will not be accepted unless it meets these requirements:

Your name and student ID must be included at the start of every file in your submission.
Save your file(s) into a zip file called YourStudentID.zip
Submit your zip file containing your entire submission to Moodle.
Late Submission
Late submission will have 5% deduction of the total assignment marks per day (including weekends). Assignments
submitted 7 days after the due date will not be accepted.
Important Notes
● Please ensure that you have read and understood the university’s procedure on plagiarism and collusion available
at https://www.monashcollege.edu...
. You will be required to agree to these policies when you submit your assignment.
● Your code will be checked against other students’ work and code available online by advanced plagiarism
detection systems. Make sure your work is your own. Do not take the risk.
● Your program will be checked against a number of test cases. Do not forget to include comments in your code
explaining your algorithm. If your implementation has bugs, you may still get some marks based on how close
your algorithm is to the correct algorithm. This is made difficult if code is poorly documented.
● Where it would simplify the problem you may not use built-in Python functions or libraries (e.g. using
list.sort() or sorted()). Remember that this is an assignment focusing on algorithms and programming.

2
MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Assignment code interview
Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of
your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand
the code submitted. Your assignment mark will be scaled according to the responses provided.
Interview Rubric
0 The student cannot answer even the simplest of questions.
There is no sign of preparation.
They probably have not seen the code before.
0.25 There is some evidence the student has seen the code.
The answer to a least one question contained some correct points.
However, it is clear they cannot engage in a knowledgeable discussion about the code.
0.5 The student seems underprepared.
Answers are long-winded and only partly correct.
They seem to be trying to work out the code as they read it.
They seem to be trying to remember something they were told but now can’t remember.
However, they clearly know something about the code.
With prompting, they fail to improve on a partial or incorrect answer.
0.75 The student seems reasonably well prepared.
Questions are answered correctly for the most part but the speed and/or confidence they are
answered with is not 100%.
With prompting, they can add a partially correct answer or correct an incorrect answer.
1 The student is fully prepared.
All questions were answered quickly and confidently.
It is absolutely clear that the student has performed all of the coding themselves.
Marking Criteria
This assignment contributes to 8% of your final mark.
Task 1: Display Sudoku - 5 marks
? Displaying all rows of the field in individual lines (1 mark)
? Displaying spaces instead of zeroes and no commas (1 mark)
? Visualisation of subgrid boundaries for k==2 (1 mark)
? Visualisation of subgrid boundaries for arbitrary k (not necessarily aligned columns for k > 2) (1 mark)
? If function correctly aligns columns for k = 4 by replacing values 10 to 16 by letters 'A' to 'G' (1 mark)
Task 2: Implement the rules - 5 marks
? Correct implementation of subgrid values (2 mark)
? Correct implementation of options (1 mark)
? Integration into the play function (1 mark)
? For success message when board is solved (1 mark)
Task 3: Undo – 2 marks
? Restart functionality (1 mark)
? Undo functionality (1 mark)
Task 4: Hints - 3 marks
? Printing a hint and explaining how the hint is chosen in the docstring (2 marks)
? Printing board with marker on the field corresponding to the hint (1 mark)
Programming practice – 2 marks
? Decomposition (1 mark)
? Variable names and code Documentation (1 mark)
Total: 17 marks
3
MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Sudoku
Sudoku is a puzzle game for one player where one has to fill up a regular grid of fields (game board) with
numbers. Typically a Sudoku board is 9 times 9 fields, but in this assignment we will write functions that can
work in principle with arbitrary sized n times n boards as long as n = k**2 for some integer k > 1.
Conceptually, the board is composed of k×k subgrids (each consisting of k×k fields). The objective of the
player is to fill all fields with the numbers 1 to n (inclusive) such that
? no column of the grid contains the same number more than once
? no row of the grid contains the same number more than once
? none of the k**2 subgrids contains the same number more than once
See https://en.wikipedia.org/wiki... for more information.
In this assignment, we represent a Sudoku board by a n×n table where each entry is either a number from
1 to n (inclusive) or 0 representing that the corresponding field is still empty. For example, a small game board
with n=4 (and k=2) with four fields already filled could be defined as follows:

small = [[0, 0, 1, 0],
... [4, 0, 0, 0],
... [0, 0, 0, 2],
... [0, 3, 0, 0]]
An example for the typical 9x9 size is:
big = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
... [4, 0, 0, 7, 8, 9, 0, 0, 0],
... [7, 8, 0, 0, 0, 0, 0, 5, 6],
... [0, 2, 0, 3, 6, 0, 8, 0, 0],
... [0, 0, 5, 0, 0, 7, 0, 1, 0],
... [8, 0, 0, 2, 0, 0, 0, 0, 5],
... [0, 0, 1, 6, 4, 0, 9, 7, 0],
... [0, 0, 0, 9, 0, 0, 0, 0, 0],
... [0, 0, 0, 0, 3, 0, 0, 0, 2]]
Finally, an example of a giant board with 4x4 subgrids each of size 4x4 is:
giant = [[ 0, 5, 0, 0, 0, 4, 0, 8, 0, 6, 0, 0, 0, 0, 9, 16],
... [ 1, 0, 0, 0, 0, 0, 0, 13, 4, 0, 0, 7, 15, 0, 8, 0],
... [13, 0, 0, 0, 0, 7, 3, 0, 0, 0, 0, 9, 5, 10, 0, 0],
... [ 0, 11, 12, 15, 10, 0, 0, 0, 0, 0, 5, 0, 3, 4, 0, 13],
... [15, 0, 1, 3, 0, 0, 7, 2, 0, 0, 0, 0, 0, 5, 0, 0],
... [ 0, 0, 0, 12, 0, 3, 0, 5, 0, 11, 0, 14, 0, 0, 0, 9],
... [ 4, 7, 0, 0, 0, 0, 0, 0, 12, 0, 15, 16, 0, 0, 0, 0],
... [ 0, 0, 0, 0, 14, 0, 15, 0, 6, 9, 0, 0, 0, 0, 12, 0],
... [ 3, 0, 15, 4, 0, 13, 14, 0, 0, 0, 0, 1, 0, 0, 7, 8],
... [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0],
... [11, 0, 16, 10, 0, 0, 0, 0, 0, 7, 0, 0, 0, 3, 5, 0],
... [ 0, 0, 13, 0, 0, 0, 0, 0, 14, 0, 15, 16, 0, 9, 0, 1],
... [ 9, 0, 2, 0, 0, 14, 0, 4, 8, 0, 0, 0, 0, 0, 0, 0],
... [ 0, 14, 0, 0, 0, 0, 0, 10, 9, 0, 3, 0, 0, 0, 1, 7],
... [ 8, 0, 0, 0, 16, 0, 0, 1, 2, 14, 11, 4, 0, 0, 0, 3],
... [ 0, 0, 0, 1, 0, 0, 5, 0, 0, 16, 0, 6, 0, 12, 0, 0]]
4
MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Play Sudoku
Task 1: Display Sudoku (5 marks)
The function print_board(board) from the template accepts as input parameter a game board and prints it.
Improve the function such that each row of the board is printed in its own line with aligned column entries, zeroes
replaced by spaces, and the subgrids are visible. For example, the output for the above small and big boards could be:
print_board(small)

| |1 |
|4 | | | | 2|
| 3| |

print_board(big)

| | | |
|4 |789| |
|78 | | 56| | 2 |36 |8 |
| 5| 7| 1 |
|8 |2 | 5| | 1|64 |97 |
| |9 | |
| | 3 | 2| For k=4, it is more complicated to have the columns aligned. Thus a nicer overview is to use letter codes
for the numbers 10 to 16, where 10 =A, 11 = B, …, 16 = G, For example:

print_board(giant)

| 5 | 4 8| 6 | 9G|
|1 | D|4 7|F 8 |
|D | 73 | 9|5A |
| BCF|A | 5 |34 D| 【MCD4710算法分析】|F 13| 72| | 5 |
| C| 3 5| B E| 9|
|47 | |C FG| |
| |E F |69 | C | |3 F4| DE | 1| 78|
| | | 9A| |
|B GA| | 7 | 35 |
| D | |E FG| 9 1| |9 2 | E 4|8 | |
| E | A|9 3 | 17|
|8 |G 1|2EB4| 3|
| 1| 5 | G 6| C | Hint: You may need to use print(x, end=‘’) to avoid printing new line with each print.
5
MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Task 2: Implement the rules (5 marks)
The function play(board) provided in the template accepts as input a Sudoku board and allows to play a
game of Sudoku via the console. When you run the function you will find that it has the following bevaviour:
? When the function is called, it prints the input game board (via the function print_board)
? Then it goes into an infinite loop where it first waits for user input (via the built-in input function)
and then proceeds as follows:
– On input ‘q’ or ‘quit’ the loop ends.
– On inputting three integers i j x (separated by a single whitespace character), it updates the game
board by setting the value of field (i, j) to x and prints the updated board.
– On input ‘n’ k d (the character ‘n’ followed by integers k and d, separated by a single whitespace
character), it loads a new game board of specified size k
2
and difficulty d (with some limited available
choices for k and d).
What is unsatisfactory is that the function allows the player to modify the board with invalid moves. Also,
the program does not notice when the Sudoku has been solved. In short, it doesn’t actually k now how Sudoku
works. Let’s change that.
Subgrid values:
Write a function subgrid_values(board, r, c) that accepts as input parameters a Sudoku board, board, a
row index r, and a column index c, and that produces as output a list of all numbers that are present in the subgrid of
the board that row r and column c belong to. For example:

subgrid_values(small, 1, 3)
[1]
subgrid_values(big, 4, 5)
[3, 6, 7, 2]
subgrid_values(giant, 4, 5)
[7, 2, 3, 5, 14, 15]
Options:
Write a function options(board, r, c) that accepts as input parameters a game board (board), an integer
row index r, and an integer column index c and that produces as output a list of all possible values that a player is
allowed to place into field (r, c) of the board. For example:
options(small, 0, 0)
[2, 3]
options(big, 6, 8)
[3, 8]
options(giant, 1, 5)
[2, 5, 6, 9, 11, 12, 16]
Now modify the play function that on user input of three numbers i j x, it only modifies and reprints the board if x is a
legal value for the field (i, j) in the current board and otherwise prints an error message. Finally, let the play function
print a success message when, at the beginning of the loop, the sudoku is solved (i.e., there are no empty fields left)
6
MCD4710 - Introduction to Algorithms and Programming
Assignment 1 (8%)
Task 3: Undo (2 marks)
Extend the behaviour of the play function such that:
? on input ‘r’ or ‘restart’ the game restarts with the last loaded game board ( the board that was loaded with the command
n),
? on input ‘u’ or ‘undo’ the last move is taken back.
Task 4: Hints (3 marks)
Extend the behaviour of the play function such that on input ‘h’ or ‘hint’ it prints the coordinates of a
field for which it is easiest to see the correct value. Think of meaningful ways to implement this functionality
and explain your approach in a docstring. The functionality should also reprint the board with the indicator
symbol ‘*’ at the position referred to by the hint.
For instance, when entering ‘h’, the function could print the following to the console (this is just an
illustration; your function might behave differently):