MCD4710 – Introduction to Algorithms and Programming Assignment 2 (10%)
Due: Thursday, January 6, 2022, 11:55 pm – Week 10
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:
1. Your name and student ID must be included at the start of every file in your submission.
2. Save your file(s) into a zip file called YourStudentID.zip
3. 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.au/__data/assets/pdf_file/0005/1266845/Student-Academic-Integrity- Diplomas-Procedure.pdf . 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.
1
MCD4710 – Introduction to Algorithms and Programming Assignment 2 (10%)
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 10% of your final mark. Task 1: Inference – 6 marks
Correct implementation of the forward single rule (1 mark)
Correct implementation of the backward single rule (3 marks)
o Meaningful structure of algorithm
o Considering all relevant fields in all related regions
o Correctly determining the options not provided by another field in the same region
Correct looping to carry out all the updates based on the single rules (1 mark)
Integration into the play function (1 mark) Task 2: board – 6 marks
Generation of random full Sudoku board (2 marks)
for removing full cells and detection of whether candidate board has a unique solution (2 marks)
for overall generation procedure and integration into the play function (2 marks)
o this includes ensuring the code works for any board size and not hard coded to work with k = 2 and k = 3 only
Programming practice – 2 marks
Decomposition (1 mark)
Variable names and code Documentation (1 mark)
Total: 14 marks
2
MCD4710 – Introduction to Algorithms and Programming Assignment 2 (10%)
Sudoku
Task 1: Inference
Inference is the process of deriving a logical conclusion from a set of given facts. In the context of Sudoku, a player attempts to infer the correct values for empty fields given the content of the already filled fields. There are numerous inference rules that experienced Sudoku players use. Let us focus on the ’Singles’ strategy (http://www. taupierbw.be/SudokuCoach/SC_Singles.shtml), which contains two separate rules.
1. The first one (let us refer to it as “forward single”) is the simple observation that if an empty field f has only one available option x, then f should contain x.
2. The second single rule (let us refer to it as “backward single”) is based on the fact that in every region of a Sudoku board (i.e., row, column, and subgrid) the solution needs to contain every number from 1 to n. From this we can derive the rule as: if within a given region the number x is available as option only in one field f of that region, then the solution contains x in field f (because it is the only field that can “supply” x).
It turns out that both rules in conjunction are enough to solve a lot of Sudoku boards and we can implement a decent partial Sudoku solver based on them.
Write a function inferred(board) that accepts as input a Sudoku board and returns as output a new Sudoku board that contains all values that can be inferred by repeated application of the two single rules. For example, for the big game board above the function would completely solve the board:
>>> inferred(big)
[[2, 1, 3, 4, 5, 6, 7, 8, 9],
[4, 5, 6, 7, 8, 9, 1, 2, 3], [7, 8, 9, 1, 2, 3, 4, 5, 6], [1, 2, 4, 3, 6, 5, 8, 9, 7], [3, 6, 5, 8, 9, 7, 2, 1, 4], [8, 9, 7, 2, 1, 4, 3, 6, 5], [5, 3, 1, 6, 4, 2, 9, 7, 8], [6, 4, 2, 9, 7, 8, 5, 3, 1], [9, 7, 8, 5, 3, 1, 6, 4, 2]]
In contrast, for the big4 game board, our inference rules get stuck right in the beginning:
>>> inferred(big4)
[[0, 0, 0, 6, 0, 0, 2, 0, 0],
[8, 0, 4, 0, 3, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 9, 0, 0, 0],
[4, 0, 5, 0, 0, 0, 0, 0, 7],
[7, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 0, 0, 8],
[3, 0, 0, 0, 7, 0, 0, 0, 4],
[0, 0, 0, 0, 0, 1, 9, 0, 0],
[0, 0, 0, 2, 0, 0, 0, 6, 0]]
Finally, integrate this function into the play function such that on user input ‘i’ (or ‘infer’), the current board state is replaced by the inferred board state (and as usually the new state is printed to the console to be inspected by the user). For that, make sure that the inferred function does not modify the input board.
3
MCD4710 – Introduction to Algorithms and Programming Assignment 2 (10%)
Task 2: board
In the template file, we provided solutions function, this function will return possible solutions to the board as a list of solutions, where each item in this list is a solved board. You don’t need to understand how this function works. However, you just need to understand the format of its input and output as you will use this function to extend the behaviour of the play function such that on input ‘g’ k,(i.e.,thelettergfollowedbyanintegerk>1),or’generate’ k,itgeneratesanewrandom k2 by k2 Sudoku board such that the board has a unique solution.
Hints:
• Think of a good decomposition of this problem. Some ideas for useful subproblems are, e.g.,
generating a random full game board that is valid (i.e., satisfies the placement constraints of
Sudoku) and checking whether a given partially filled board has a unique solution.
• The partially filled board can be generated by repeatedly removing a number from the board (set that cell to 0) and see if the resulting game board would still have a unique solution. The number to
be removed can be selected randomly. You should aim to remove as much numbers as possible.
• For randomising you can use the function shuffle from the random module.
• Your initial solutions to this problem are likely rather slow. Make sure to first test with the smallest
board size (k =2).
4