Acknowledgement: This lab assignment takes inspiration from Solving Every Sudoku Puzzle, which is an essay by Peter Norvig on how to solve Sudoku. The code is partially taken from the website. We thank Peter Norvig for making the project available to the public. Also OSMnx module developed by Geoff Boeing which made it possible to get geographic and street network of Mumbai alongwith stunning graphs. We thank him for making such an awesome library and open-sourcing it.
The base code for this assignment is available
in this
zip file. The following files are the most relevant ones for you;
you will only have to edit sudoku.py
and maps.py
.
File Name | Description |
sudoku.py | Where your logic for converting Sudoku into a search problem resides. |
maps.py | Where your logic for converting a 2-D map into a search problem resides. |
search.py | Your search algorithms will reside here. |
main.py | The main file which actually runs the search algorithms on the given tasks. |
util.py | Useful data structures for implementing search algorithms. |
In sudoku.py
and maps.py
, you will find a skeleton code which you need to fill, these convert the abstract problems into fully defined search problems. The search algorithms need to go in search.py
which will actually solve the search instances.
You need to get familiar with NetworkX module. It makes it easier to manipulate complex graphs like maps.
Now you will implement different search algorithms to solve interesting problems like Sudoku and How to get to Marine Drive in the shortest path possible if you decide to cycle there (That's quite a mouthful, why don't we just call it Shortest Path Problem). Remember that a search node must contain not only a state but also the information necessary to reconstruct the path which gets to that state from the start state.
Important note: Some of your search functions need to return a list of nodes that will lead you from the start to the goal.
Important note: Make sure to use the Stack
, and PriorityQueue
data structures provided to you in util.py
! These data structure implementations have particular properties that are required for compatibility with the autograder.
Hint: The algorithms are quite similar. Algorithms for DFS and A* differ only in the details of how the fringe (or frontier) is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit.)
(Image source: https://en.wikipedia.org/wiki/Sudoku#/media/File:Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg)
['A1', 'A2', .... , 'I8', 'I9']
. We maintain a dictionary of possible values that each square can take. So the dict called values has the following form : values = {'A1' : '1278', 'A2' : '1', ... , 'I8' : '2673', 'I9' : '12'}
. Basically, the keys are the squares and the values are the possible digits that can be in that square based on the current conditions. This is your state.
'data/sudoku/hardest.txt'
and 'data/sudoku/top95.txt'
. We encourage you to solve at least one of the hardest ones yourself to appreciate the algorithm. Go through the parse_grid function and the grid values function to visualise the sudoku problem as a grid. Use the display function to display the values
dictionary in a format suitable for visualisation.
The function parse_grid
calls assign(values, s, d)
.
We could implement this as values[s] = d
, but we can do more
than just that. Those with experience solving Sudoku puzzles know
that there are two important strategies that we can use to make progress towards
filling in all the squares:
(1) If a square has only one possible value, then eliminate that value from the square's peers.
(2) If a unit has only one possible place for a value, then put the value there.
It turns out that the fundamental operation is not assigning a value, but
rather eliminating one of the possible values for a square, which is
implemented with eliminate(values, s, d)
. Once we have
eliminate
, then assign(values, s, d)
can be
defined as "eliminate all the values from s
except d
".
sudoku.py
file under the SudokuSearchProblem
class.
list(tuple(nextState, Action, EdgeCost))
Run your code with the following command. This serves as both running the script as well as autograder
python2 main.py -t 1
The key idea in this is that the action we take at each step. I.e. changing from one state (values) to another is done by chosing a digit to place in one of the squares having minimum remaining values greater than 1. So essentially we choose the square with minimum values[s]
and our action at state "values
" are filling s
with [d for d in values[s]]
. i.e. actions from states = values is [(s, d) for d in values[s]]
, here s = square with minimum {values(s) > 1}
. The reason for doing this is elaborated in the section search of the above link.
depthFirstSearch
function of the search.py
file.
Run your code with the following command.
python2 main.py -t 2
For the definition and use of Node class refer to Section 3.3, and for DFS to Section 3.4, Russell and Norvig (2010).
answers.txt
.
In this task we are going to answer what is the optimal path from Hostel 4 to Lecture Hall Complex. This is a confounding problem due to the myriads of paths possible from Hostel 4. We hope that this helps all the sleepy people in making a better decision in the morning and reach the Lectures on time.
We have also been informed that the lab takes most of your time on the weekends and you have not been able to explore Mumbai. So we also take you on a virtual tour of Mumbai. You would be travelling but obviously you are not a salesman.
maps.py
file under the MapSearchProblem
class.
list(tuple(nextState, Action, EdgeCost))
Run your code with the following command.
python2 main.py -t 4
(Image source: https://vignette.wikia.nocookie.net/main-cast/images/6/6f/Star.jpg/revision/latest?cb=20151213212737)
You need to implement the A star Search Algorithm algorithm in the AStar_search
function of the search.py
file. At the end
your function should return a route as list of nodes in order, consisting of both the start and end node.
Run your code with the following command.
python2 main.py -t 5 --show
For the definition and use of Node class refer to Section 3.3, and for AStar_search to Section 3.5, Russell and Norvig (2010).
heuristic
function of the search.py
file. We have provided some useful function in the util.py
file to calculate the distance between 2 points given their latitude and longitude.
Run your code with the following command.
python2 main.py -t 6 --show
For information on Heuristics refer to Section 3.6, Russell and Norvig (2010).
Write your solutions in answers.txt
for both the problems.
You are expected to work on this assignment by yourself. You may
not consult with your classmates or anybody else about their
solutions. You are also not to look at solutions to this assignment or
related ones on the Internet. You are allowed to use resources on the
Internet for programming (say to understand a particular command or a
data structure), and also to understand concepts (so a Wikipedia page
or someone's lecture notes or a textbook can certainly be
consulted). However, you must list every resource you have
consulted or used in a file named references.txt
,
explaining exactly how the resource was used. Failure to list all
your sources will be considered an academic violation.
Be sure to write all the observations/explanations in the answers.txt
file.
We have mentioned wherever there is such a requirement. Find the keyword 'answers.txt'
in the page.
Place all files in which you have written code in or modified in a
directory named la7-rollno
, where rollno
is
your roll number (say 12345678). Tar and Gzip the directory to produce
a single compressed file (say la7-12345678.tar.gz
). It
must contain the following files.
sudoku.py
maps.py
search.py
references.txt
answers.txt
Submit this compressed file on Moodle, under Lab Assignment 7.