automated puzzle solving solution

Puzzle solving is a typically human activity that, in recent decades, is being explored in the context of computers. There are two bene?ts to this: ?rst, we can o?-load some puzzle-solving tasks to computers, and second, we may understand human puzzle-solving better by studying how to implement it on a computer. This assignment investigates a class of puzzles that have the following features in common: full information: all information about the puzzle con?guration at any given point is visible to the solver; there are no hidden or random aspects well-defined extensions: a de?nition of legal extensions from a given puzzle con?guration to new con?gurations is given well-defined solution: a de?nition of what it means for the puzzled to be in a solved state is given These features are common to a very large class of puzzles: crosswords, sudoku, peg solitaire, verbal arithmetic, and so on. This assignment generalizes the required features into an abstract superclass Puzzle, and solving functions are written in terms of this abstract class. Once this is done, particular concrete puzzles can be modelled as subclasses of Puzzle, and solved using the solving functions. Although there may be faster puzzle-speci?c solvers for a particular puzzle by knowing speci?c features of that puzzle, the general solvers are designed to work for all puzzles of this sort. abstract Puzzle class The abstract class Puzzle has the following methods, which are not implemented, but meant to be implemented in subclasses: is solved: returns True or False, depending on whether the puzzle is in a solved con?guration or not extensions: returns a list of extensions from the current puzzle con?guration to new con?gurations that are a single step (\move") away fail fast: returns True or False, depending on whether it is clear that the current puzzle con?guration can never be completed, through a sequence of extensions, to a solved state And that's it. Notice that there is no init method, since the representation and initialization of puzzles in this class vary widely. Each subclass will need an init method to represent a particular puzzle. 1 sudoku This puzzle commonly appears in print media and online. You are presented with an n ? n grid with some symbols, for example digits or letters, ?lled in. The symbols must be from a set of with n symbols. The goal is to ?ll in the remaining symbols in such a way that each row, column, or pn ?pn subsquare, has each symbol exactly once. In order for all of that to make sense, n must be a square integer such as 4, 9, 16, 25, ... You may want to read more about sudoku to get a feel for the puzzle. We provide you with a mostly-implemented SudokuPuzzle subclass of Puzzle. We, however, did not override the fail fast method inherited from Puzzle, and you should be able to do better. Implement fail fast for sudoku by having it return True for, and hence abandoning, any sudoku con?guration where there is at least one empty position that will be impossible to ?ll because the set of symbols has been completely used up by other positions in the same row, column or subsquare. Experiment to see whether this makes any di?erence in the performance of solver(s) for sudoku. peg solitaire This puzzle has gone by various names: Hi-Q, peg solitaire, solo noble, and patience, and has been around for several hundred years. You are presented with a grid where most positions are occupied by a peg, marble, or other movable piece. The object is to \jump" a piece over a neighbouring piece and into an empty position, allowing you to remove the piece that was jumped over. A successful game leaves only one piece on the board. Boards come in various shapes of grid. We will assume that some portion of an m ? n grid is used, that some positions may be unused (no pieces may be placed there), some positions begin with pieces in them, and that a few (often just one) position is left empty to allow jumping. You can see various versions of peg solitaire on the web. We provide you with the class declaration and init method for subclass GridPegSolitairePuzzle of Puzzle. You will override the extensions and is solved methods for this subclass, which make it possible for the solvers (which you'll also write) to solve it. A legal extension of a GridPegSolitairePuzzle is a new con?guration that you can get to in a single jump. The puzzle is solved when a single peg is left. We do not require you to override the fail fast method, although you are welcome to see whether you can come up with one that improves performance. word ladder This puzzle involves starting with from word, from a set of allowed words, and deriving to word from the same set of allowed words, by changing one letter at a time. Each changed letter must result in a word that is is from the same set of words. Here's an example, assuming that the set of words is a rather large set of English words provided to many computer applications. The goal is to get from cost to save cost ! cast ! case ! cave ! save We provide you with the class declaration and init method for subclass WordLadderPuzzle of Puzzle. You will override the extensions and is solved methods for this subclass. A legal extension of a WordLadderPuzzle is a new con?guration where the from word di?ers by a single letter from the previous from word. A WordLadderPuzzle is solved when the from word is the same as the to word. 2 We don't require you to override the fail fast method, although you are welcome to see whether you can come up with one that improves performance. mn puzzle Sometimes called the 15-Puzzle, Boss Puzzle, or Game of 15, this puzzle consists of a 4 ? 4, 3 ? 3, or (in general) an m?n, grid with one empty position. A player must swap symbols with the empty position until they get the entire puzzle into the correct order. We provide the class declaration and init method for subclass MNPuzzle. You will override is solved and extensions methods to allow the solvers to solve this puzzle. The puzzle is solved when the con?guration is the same as the supplied target con?guration. Legal extensions of a con?guration swap the empty space with either the symbol to its right, the symbol to its left, the symbol above it, or the symbol below it. We don't require you to override the textbffail fast method, but you are welcome to see whether you can design one that improves performance. searching One approach to solving a puzzle is to systematically search for a solution, starting from the current con?guration. To make this daunting task even possible, we have to be sure that we have a systematic way of checking out puzzle con?gurations, and that we don't re-visit the same con?guration twice. You will implement two standard systematic searching techniques. We are well aware that plenty of code and pseudo-code for these are \out there" on the web, so you have to be very careful you are giving credit for any ideas you recycle, in order to avoid an academic o?ense. depth-first search As the name suggests, you search deeply before you search broadly. 1. don't bother with any puzzle con?guration if it's been seen before 2. check whether the current puzzle con?guration is solved; if so you're done; otherwise... 3. for each extension of the current puzzle con?guration, make that extension the current puzzle con?guration and return to step 1 Notice how this process unwraps. You check a con?guration, then one of its extensions, then one of the extension’s extensions, and so on. That means that if a con?guration has several extensions, you will be checking every possible chain of extensions from one of them before you check the others. Notice also that if there are no extensions, step 3 is empty. You will implement depth ?rst solve following this strategy. You are welcome to read material on depth?rst search, but be aware of several things: ? the return type for depth first solve is a PuzzleNode1 that must be the ?rst node in a path of PuzzleNodes that lead from the given con?guration to a solution ? give credit for ideas from the web that you recycle, so you won't be guilty of an academic o?ense. 1PuzzleNodes are de?ned in puzzle tools.py 3 breadth-first search As the name suggests, you search broadly before you search deeply. 1. skip any puzzle con?guration that has already been seen 2. check whether the current puzzle con?guration is solved; if so you're done, otherwise 3. check whether any extensions of the current puzzle con?guration are solved; if so you're done, otherwise 4. check whether any extensions of extensions of the current puzzle con?guration are solved; if so you're done, otherwise 5. ... Notice how this approach examines con?gurations that are \closer" to the starting con?guration before it examines those that are \farther." This may be useful for ?nding a shortest solution to a puzzle. You will implement breadth ?rst solve following this strategy. You are welcome to read material on breadth-?rst search, but be warned: ? the return type for breadth first solve is a PuzzleNode that is the ?rst node in a path of PuzzleNodes from the current puzzle con?guration to a solution ? give credit for ideas from the web that you recycle, so you won't be guilty of an academic o?ense starter code You'll ?nd the following ?les, with associated tasks, in Starter. Leave the class declarations, init methods, and the if name == ” main :” block as you ?nd them: we have veri?ed that neither PyCharm2 nor PEP8 disapprove of them. puzzle.py Read and understand the Puzzle class. sudoku puzzle.py Read and understand the SudokuPuzzle class, then override the fail fast method inherited from Puzzle. grid peg solitaire puzzle.py Read the init method, then override the extensions and is solved methods inherited from Puzzle. word ladder puzzle.py Read the init method, then override the extensions and is solved methods inherited from Puzzle. mn puzzle.py Read the init method, then override the extensions and is solved methods inherited from Puzzle. puzzle tools.py Read and understand the PuzzleNode class, then implement module-level functions depth first solve and breadth first solve.