MCD4710 - Introduction to Algorithms and Programming Assignment 2

Objectives

The objectives ofthis 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 oftest 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.

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

Marking Criteria

This assignment contributes to 10% of your final mark.

Task 1:  Inference – 6 marks

     Correct implementation ofthe 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: Generting Suduko 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

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: ifwithin 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.