“””
CSC148, Summer 2021
Assignment 3: Automatic Puzzle Solver
==============================
This code is provided solely for the personal and private use of
students taking the CSC148 course at the University of Toronto.
Copying for purposes other than this use is expressly prohibited.
All forms of distribution of this code, whether as given or with
any changes, are expressly prohibited.
Authors: Diane Horton, Jonathan Calver, Sophia Huynh,
Maryam Majedi, and Jaisie Sin.
All of the files in this directory are:
Copyright (c) 2021 Diane Horton, Jonathan Calver, Sophia Huynh,
Maryam Majedi, and Jaisie Sin.
This module is adapted from the CSC148 Winter 2021 A2 with permission from
the author.
=== Module Description ===
This module contains the abstract Solver class and its two subclasses, which
find solutions to puzzles, step by step.
“””
from __future__ import annotations
from typing import List, Optional, Set
# You may remove this import if you don’t use it in your code.
from adts import Queue
from puzzle import Puzzle
class Solver:
“”””
A solver for full-information puzzles. This is an abstract class
and purely provides the interface for our solve method.
“””
# You may NOT change the interface to the solve method.
# Note the optional parameter seen and its type.
# Your implementations of this method in the two subclasses should use seen
# to keep track of all puzzle states that you encounter during the
# solution process.
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
“””
Return a list of puzzle states representing a path to a solution of
second element should be a puzzle that is in
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
representations, whose puzzle states can’t be any part of the path to
the solution.
“””
raise NotImplementedError
# TODO (Task 2): implement the solve method in the DfsSolver class.
# Your solve method MUST be a recursive function (i.e. it must make
# at least one recursive call to itself)
# You may NOT change the interface to the solve method.
class DfsSolver(Solver):
“”””
A solver for full-information puzzles that uses
a depth first search strategy.
“””
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
“””
Return a list of puzzle states representing a path to a solution of
second element should be a puzzle that is in
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
representations, whose puzzle states can’t be any part of the path to
the solution.
Note: A user of this method may pass a set of puzzle states that
shouldn’t appear in the path to the solution. You should also update
seen to include states, that you have encountered, which are not the
solved state of the puzzle.
“””
# TODO (Task 2): implement the solve method in the BfsSolver class.
# Hint: You may find a Queue useful here.
class BfsSolver(Solver):
“”””
A solver for full-information puzzles that uses
a breadth first search strategy.
“””
def solve(self, puzzle: Puzzle,
seen: Optional[Set[str]] = None) -> List[Puzzle]:
“””
Return a list of puzzle states representing a path to a solution of
second element should be a puzzle that is in
and so on. The last puzzle in the list should be such that it is in a
solved state.
In other words, each subsequent item of the returned list should take
the puzzle one step closer to a solution, which is represented by the
last item in the list.
Return an empty list if the puzzle has no solution.
representations, whose puzzle states can’t be any part of the path to
the solution.
Note: A user of this method may pass a set of puzzle states that
shouldn’t appear in the path to the solution. You should also update
seen to include states, that you have encountered, which are not the
solved state of the puzzle.
“””
if __name__ == “__main__”:
# you may add any code you want to use for testing here
import python_ta
python_ta.check_all(config={
# # uncomment to disable openning pyta output in browser
# ‘pyta-reporter’: ‘ColorReporter’,
‘allowed-io’: [],
‘allowed-import-modules’: [
‘doctest’, ‘python_ta’, ‘typing’, ‘__future__’, ‘puzzle’, ‘adts’
],
‘disable’: [‘E1136’],
‘max-attributes’: 15
})