讲解159.271留学生、Python讲解、辅导Sudoku Solver、讲解Python编程 辅导Web开发|讲解R语言编程
- 首页 >> 其他 Computational Thinking 14/03/19, 3)10 PM
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 1 of 3
159.271 Computational Thinking
Assignment 1: Sudoku Solver
This assignment is worth 10% of your final mark. It will be marked out of a total of 20
marks. The due date for this assignment is Monday April 8th. You are expected to work on
this assignment individually and all work that you hand in is expected to be your own work.
In this assignment your task is to write a Sudoku solver. You will develop an animated
application that uses recursive backtracking as the basis of the implementation. I'm going to
assume that you know how to solve Sudoku already, since, if not, then you must have been
hiding under a rock for the past 5 years!
Go to Stream and download the folder
Assignment1 Assignment1
This folder contains a template program that implements the code needed to read Sudoku
puzzles from files and to display them, and to run the solver in animation mode. Set up a
new project in your IDE and add the folder src to it. The main game module is
SudokuApp.py SudokuApp.py. If you run this, a screen will appear and clicking on either the 'e' or the 'h'
key will display a randomly chosen puzzle (either easy or hard) from one of the two folders
of puzzles included.
You need to complete the module Solver.py Solver.py, so that a call to the solve function will do
a bit more than just displaying the puzzle. You need to turn this function into a recursive
backtracking solver, which, for animation purposes, displays a snapshot of the current state
of the puzzle at the start of each recursive call.
The program uses two classes to represent a Sudoku – Cell and Snapshot Snapshot. Cell
represents a single cell in a Sudoku grid, and has methods to get and set the position of the
cell and the value of the cell. In any complete solution, the value must be between 1..9. If the
value is 0 this means that the cell is still empty. Snapshot Snapshot describes a state of the Sudoku
at a certain point in time – some cells have values (other than zero), some may not. The
Snapshot Snapshot class has methods that allow to clone a snapshot (this is useful to produce the
next level of snapshots in the recursion tree), to query the cells in various ways, and to set
cells.
Sudoku_IO.py Sudoku_IO.py contains the code used to read Sudoku puzzles from puzzle files and to
display them. The puzzle files consist of 9 lines containing 9 digits each, encoding the initial
values for the board cells.
In general, to develop a recursive backtracking algorithm you need to consider:Computational Thinking 14/03/19, 3)10 PM
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 2 of 3
In general, to develop a recursive backtracking algorithm you need to consider:
1. What question should we ask? Thinking only about the top level of recursion, you need
to formulate one small question about the solution that is being searched for. Remember
that, in order for the final algorithm to be efficient, it is important that the number of
possible answers is small.
2. How should we construct a subinstance? How to express the problem that we want to
solve as a smaller instance of the same search problem?
1. An input instance to the problem will be a snapshot snapshot specifying the current state of
the Sudoku. A solution is a valid way of filling the remaining empty cells.
2. The simple question to ask is "What number can go in the next empty cell?"
The brute force strategy is simply to find the next empty cell in the snapshot, working left to
right, top to bottom, and then to try all possible numbers in that cell. Initial pruning of the
recursion tree should include two strategies - 1. we don't continue on any branch that has
already produced an inconsistent (invalid) solution and 2. we stop once a complete solution
has been found. Python code examples that implement this basic strategy for two
straightforward problems have been given in the lecture slides.
A smarter approach is to look for 'singletons', i.e., those cells that can only have one possible
number in them. So, for each cell you need to keep a list of which numbers are allowed
within it, and then check the relevant row, column, and 3 x 3 block to remove those numbers
that have already been used. Of course, if you end up in a situation where there are no
possible numbers that can go in a cell then you've done something wrong, so your algorithm
should stop and backtrack. You will need to add attributes and methods to the Cell class to
implement this strategy.
Once you have run out of singletons you need another strategy. Perhaps you keep a list of
the cells in the current snapshot, sorted in order of the lengths of their 'possibles' lists. There
are other intelligent things that can be done. You can 'cross-reference' between the 'missing'
values in a row, column, or block and the 'possibles' lists for its empty cells. If a 'missing'
value appears in only one of the 'possibles' lists, then this value must go in the cell.
Marking scheme
1. 10 marks for a correct program that uses a recursive backtracking strategy with basic
pruning.
2. 5 marks for choosing 'singletons' ahead of other cells. With this approach, for easy
puzzles, your recursion tree will become simply a path, since at each stage you will
find at least one cell that can only have one value.
3. 5 marks for more sophisticated pruning strategies, either those described here or others,Computational Thinking 14/03/19, 3)10 PM
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 3 of 3
that allow for fast backtracking over hard puzzles. You will need to submit a readMe
document briefly describing the more sophisticated strategies that you have employed.
We will test your program using puzzles similar to those provided, for both easy and hard
categories.
Submission
Submit your project in Stream as a single zipped file containing your completed code,
contained in the folder Sudoku_YourID Sudoku_YourID, and your completed readMe document.
Plagiarism
There are many, many Sudoku solvers available on the internet. I am sure that many of these
are recursive backtracking solutions implemented in Python. For this reason, and also so that
the concepts taught in lectures are reinforced, you must use the template provided as the
basis of your implementation. You can improve the display or the animation however you
like, you can add more classes or improve those provided (this part you probably actually
need to do), you can make the solver as sophisticated as you like. What you cannot do is
download a solution from the internet and submit it as your own work. If you try this, you
will get no marks. Make an attempt to read the course notes, to follow the lecture slides and
to apply the concepts discussed, in completing this assignment.
As stated at the beginning of this document, you are expected to work on this assignment
individually and all work that you hand in is expected to be your own work. You are allowed
to discuss any aspect of this assignment with others, in person, on the Stream forum, or
using the Discord server. What you are not allowed to do is to submit someone else's
solution as your own work. If it appears that this is the case, you will get no marks.
Late submission:
Late assignments will be penalised 10% for each weekday past the deadline, for up to five (5)
days; after this no marks will be gained. In special circumstances an extension may be
obtained from the paper co-ordinator, and these penalties will not apply. Workload will not
be considered a special circumstance – you must budget your time.
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 1 of 3
159.271 Computational Thinking
Assignment 1: Sudoku Solver
This assignment is worth 10% of your final mark. It will be marked out of a total of 20
marks. The due date for this assignment is Monday April 8th. You are expected to work on
this assignment individually and all work that you hand in is expected to be your own work.
In this assignment your task is to write a Sudoku solver. You will develop an animated
application that uses recursive backtracking as the basis of the implementation. I'm going to
assume that you know how to solve Sudoku already, since, if not, then you must have been
hiding under a rock for the past 5 years!
Go to Stream and download the folder
Assignment1 Assignment1
This folder contains a template program that implements the code needed to read Sudoku
puzzles from files and to display them, and to run the solver in animation mode. Set up a
new project in your IDE and add the folder src to it. The main game module is
SudokuApp.py SudokuApp.py. If you run this, a screen will appear and clicking on either the 'e' or the 'h'
key will display a randomly chosen puzzle (either easy or hard) from one of the two folders
of puzzles included.
You need to complete the module Solver.py Solver.py, so that a call to the solve function will do
a bit more than just displaying the puzzle. You need to turn this function into a recursive
backtracking solver, which, for animation purposes, displays a snapshot of the current state
of the puzzle at the start of each recursive call.
The program uses two classes to represent a Sudoku – Cell and Snapshot Snapshot. Cell
represents a single cell in a Sudoku grid, and has methods to get and set the position of the
cell and the value of the cell. In any complete solution, the value must be between 1..9. If the
value is 0 this means that the cell is still empty. Snapshot Snapshot describes a state of the Sudoku
at a certain point in time – some cells have values (other than zero), some may not. The
Snapshot Snapshot class has methods that allow to clone a snapshot (this is useful to produce the
next level of snapshots in the recursion tree), to query the cells in various ways, and to set
cells.
Sudoku_IO.py Sudoku_IO.py contains the code used to read Sudoku puzzles from puzzle files and to
display them. The puzzle files consist of 9 lines containing 9 digits each, encoding the initial
values for the board cells.
In general, to develop a recursive backtracking algorithm you need to consider:Computational Thinking 14/03/19, 3)10 PM
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 2 of 3
In general, to develop a recursive backtracking algorithm you need to consider:
1. What question should we ask? Thinking only about the top level of recursion, you need
to formulate one small question about the solution that is being searched for. Remember
that, in order for the final algorithm to be efficient, it is important that the number of
possible answers is small.
2. How should we construct a subinstance? How to express the problem that we want to
solve as a smaller instance of the same search problem?
1. An input instance to the problem will be a snapshot snapshot specifying the current state of
the Sudoku. A solution is a valid way of filling the remaining empty cells.
2. The simple question to ask is "What number can go in the next empty cell?"
The brute force strategy is simply to find the next empty cell in the snapshot, working left to
right, top to bottom, and then to try all possible numbers in that cell. Initial pruning of the
recursion tree should include two strategies - 1. we don't continue on any branch that has
already produced an inconsistent (invalid) solution and 2. we stop once a complete solution
has been found. Python code examples that implement this basic strategy for two
straightforward problems have been given in the lecture slides.
A smarter approach is to look for 'singletons', i.e., those cells that can only have one possible
number in them. So, for each cell you need to keep a list of which numbers are allowed
within it, and then check the relevant row, column, and 3 x 3 block to remove those numbers
that have already been used. Of course, if you end up in a situation where there are no
possible numbers that can go in a cell then you've done something wrong, so your algorithm
should stop and backtrack. You will need to add attributes and methods to the Cell class to
implement this strategy.
Once you have run out of singletons you need another strategy. Perhaps you keep a list of
the cells in the current snapshot, sorted in order of the lengths of their 'possibles' lists. There
are other intelligent things that can be done. You can 'cross-reference' between the 'missing'
values in a row, column, or block and the 'possibles' lists for its empty cells. If a 'missing'
value appears in only one of the 'possibles' lists, then this value must go in the cell.
Marking scheme
1. 10 marks for a correct program that uses a recursive backtracking strategy with basic
pruning.
2. 5 marks for choosing 'singletons' ahead of other cells. With this approach, for easy
puzzles, your recursion tree will become simply a path, since at each stage you will
find at least one cell that can only have one value.
3. 5 marks for more sophisticated pruning strategies, either those described here or others,Computational Thinking 14/03/19, 3)10 PM
file:///Users/cmmccart/Documents/Teaching/159271/Notes/assignment1.html Page 3 of 3
that allow for fast backtracking over hard puzzles. You will need to submit a readMe
document briefly describing the more sophisticated strategies that you have employed.
We will test your program using puzzles similar to those provided, for both easy and hard
categories.
Submission
Submit your project in Stream as a single zipped file containing your completed code,
contained in the folder Sudoku_YourID Sudoku_YourID, and your completed readMe document.
Plagiarism
There are many, many Sudoku solvers available on the internet. I am sure that many of these
are recursive backtracking solutions implemented in Python. For this reason, and also so that
the concepts taught in lectures are reinforced, you must use the template provided as the
basis of your implementation. You can improve the display or the animation however you
like, you can add more classes or improve those provided (this part you probably actually
need to do), you can make the solver as sophisticated as you like. What you cannot do is
download a solution from the internet and submit it as your own work. If you try this, you
will get no marks. Make an attempt to read the course notes, to follow the lecture slides and
to apply the concepts discussed, in completing this assignment.
As stated at the beginning of this document, you are expected to work on this assignment
individually and all work that you hand in is expected to be your own work. You are allowed
to discuss any aspect of this assignment with others, in person, on the Stream forum, or
using the Discord server. What you are not allowed to do is to submit someone else's
solution as your own work. If it appears that this is the case, you will get no marks.
Late submission:
Late assignments will be penalised 10% for each weekday past the deadline, for up to five (5)
days; after this no marks will be gained. In special circumstances an extension may be
obtained from the paper co-ordinator, and these penalties will not apply. Workload will not
be considered a special circumstance – you must budget your time.