"""
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 . The first element in the list should be , the second element should be a puzzle that is in .extensions(), 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.
is either None (default) or a set of puzzle states' string 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 . The first element in the list should be , the second element should be a puzzle that is in .extensions(), 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.
is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution. """
# 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 . The first element in the list should be , the second element should be a puzzle that is in .extensions(), 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.
is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution. """
if __name__ == "__main__": import python_ta
python_ta.check_all(config={'pyta-reporter': 'ColorReporter', 'allowed-io': [], 'allowed-import-modules': ['doctest', 'python_ta', 'typing', '__future__', 'puzzle', 'adts'], 'disable': ['E1136'], 'max-attributes': 15} )
Please use python
Task 2: solver.py 1. Read the docstrings provided in solver.py and familiarize yourself with the interface that the Puzzle class provides. 2. Go through the A2: Search Algorithms Visual Guide (courtesy of Sophia!) to make sure you understand how the depth first and breadth first search algorithms work. 3. Implement the DisSolver and Bfs Solver classes in solver.py, based on the depth first search and breadth first search algorithms described earlier. The provided starter tests test_dfs_solver_example and test_bfs_solver_example in a 2_starter_tests.py can be used as a starting point for testing your solvers. 4. Many logic puzzles, like Sudoku, actually require their solution to be unique. Implement the has_unique_solution method in the SudokuPuzzle class, based on its docstring description. We'll be posting an additional play_sudoku.py module later (now available here!) which will make use of this method to generate random sudoku for you! 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 Salver: 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
. The first element in the list should be , the second element should be a puzzle that is in .extensions(), and so on. The last puzzle in the list should be such that it is in a solved state. HER 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. is either None (default) or a set of puzzle states' string 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 Dissolver 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 Dissolver(Solver): A solver for full-information puzzles that uses a depth first search strategy. 11 def solve(self, puzzle: Puzzle, seen: Optional[Set[str]] = None) -> List[Puzzle): HER Return a list of puzzle states representing a path to a solution of . The first element in the list should be spuzzle>, the second element should be a puzzle that is in .extensions(). 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. is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution. # 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, MAH 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 . The first element in the list should be cpuzzle>, the second element should be a puzzle that is in .extensions(). 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. is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution if_name__="_main__." import python_ta python_ta.check_all(config={pyta-reporter': 'ColorReporter allowed-lo: 01. 'allowed-import-modules': ['doctest, 'python_ta! 'typing) future__ 'puzzle 'adts'), 'disable': ['E1136'). 'max-attributes': 15) > Task 2: solver.py 1. Read the docstrings provided in solver.py and familiarize yourself with the interface that the Puzzle class provides. 2. Go through the A2: Search Algorithms Visual Guide (courtesy of Sophia!) to make sure you understand how the depth first and breadth first search algorithms work. 3. Implement the DisSolver and Bfs Solver classes in solver.py, based on the depth first search and breadth first search algorithms described earlier. The provided starter tests test_dfs_solver_example and test_bfs_solver_example in a 2_starter_tests.py can be used as a starting point for testing your solvers. 4. Many logic puzzles, like Sudoku, actually require their solution to be unique. Implement the has_unique_solution method in the SudokuPuzzle class, based on its docstring description. We'll be posting an additional play_sudoku.py module later (now available here!) which will make use of this method to generate random sudoku for you! 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 Salver: 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 . The first element in the list should be , the second element should be a puzzle that is in .extensions(), and so on. The last puzzle in the list should be such that it is in a solved state. HER 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. is either None (default) or a set of puzzle states' string 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 Dissolver 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 Dissolver(Solver): A solver for full-information puzzles that uses a depth first search strategy. 11 def solve(self, puzzle: Puzzle, seen: Optional[Set[str]] = None) -> List[Puzzle): HER Return a list of puzzle states representing a path to a solution of . The first element in the list should be spuzzle>, the second element should be a puzzle that is in .extensions(). 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. is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution. # 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, MAH 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 . The first element in the list should be cpuzzle>, the second element should be a puzzle that is in .extensions(). 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. is either None (default) or a set of puzzle states' string representations, whose puzzle states can't be any part of the path to the solution if_name__="_main__." import python_ta python_ta.check_all(config={pyta-reporter': 'ColorReporter allowed-lo: 01. 'allowed-import-modules': ['doctest, 'python_ta! 'typing) future__ 'puzzle 'adts'), 'disable': ['E1136'). 'max-attributes': 15) >
