[SOLVED] CMPSC 442: Homework 2 Solved

In this assignment, you will explore three classic puzzles from the perspective of uninformed search.A skeleton file homework2-cmpsc442.py containing empty definitions for each question has been provided. Since portions of this assignment will be graded automatically, none of the names or function signatures in this file should be modified. However, you are free to introduce additional variables or functions if needed.You may import definitions from any standard Python library, and are encouraged to do so in cases where you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at the data structures and functions defined in the collections, itertools, math, andrandom modules.You will find that in addition to a problem specification, most programming questions also include a pair of examples from the Python interpreter. These are meant to illustrate typical use cases to clarify the assignment, and are not comprehensive test suites. In addition to performing your own testing, you are strongly encouraged to verify that your code gives the expected output for these examples before submitting.You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was written in part by the creator of Python. However, your code will not be graded for style.In this section, you will develop a solver for the n-queens problem, wherein n queens are to be placed on an n x n chessboard so that no pair of queens can attack each other. Recall that in chess, a queen can attack any piece that lies in the same row, column, or diagonal as itself.A brief treatment of this problem for the case where n = 8 is given in Section 3.2 of the textbook, which you may wish to consult for additional information.num_placements_one_per_row(n) that return the number of possible placements of n queenson an n x n board without or with this additional restriction. Think carefully about why this restriction is valid, and note the extent to which it reduces the size of the search space. You should assume that all queens are indistinguishable for the purposes of your calculations.Though our discussion of search in class has primarily covered algorithms that return just a single solution, the extension to a generator which yields all solutions is relatively simple. Rather than using a return statement when a solution is encountered, yield that solution instead, and then continue the search.>>> solutions = n_queens_solutions(4) >>> list(n_queens_solutions(6))>>> next(solutions) [[1, 3, 5, 0, 2, 4], [2, 5, 1, 4, 0, 3],[1, 3, 0, 2] [3, 0, 4, 1, 5, 2], [4, 2, 0, 5, 3, 1]]>>> next(solutions) >>> len(list(n_queens_solutions(8)))[2, 0, 3, 1] 92The Lights Out puzzle consists of an m x n grid of lights, each of which has two states: on and off. The goal of the puzzle is to turn all the lights off, with the caveat that whenever a light is toggled, its neighbors above, below, to the left, and to the right will be toggled as well. If a light along the edge of the board is toggled, then fewer than four other lights will be affected, as the missing neighbors will be ignored.In this section, you will investigate the behavior of Lights Out puzzles of various sizes by implementing a LightsOutPuzzle class. Once you have completed the problems in this section, you can test your code in an interactive setting using the provided GUI. See the end of the section for more details.>>> b = [[True, False], [False, True]] >>> b = [[True, True], [True, True]]>>> p = LightsOutPuzzle(b) >>> p = LightsOutPuzzle(b)>>> p.get_board() >>> p.get_board()[[True, False], [False, True]] [[True, True], [True, True]]>>> p = create_puzzle(2, 2) >>> p = create_puzzle(2, 3)>>> p.get_board() >>> p.get_board()[[False, False], [False, False]] [[False, False, False], [False, False, False]]>>> p = create_puzzle(3, 3) >>> p = create_puzzle(3, 3)>>> p.perform_move(1, 1) >>> p.perform_move(0, 0)>>> p.get_board() >>> p.get_board()[[False, True, False], [[True, True, False],[True, True, True ], [True, False, False],[False, True, False]] [False, False, False]]LightsOutPuzzle object initialized with a deep copy of the current board. Changes made to the original puzzle should not be reflected in the copy, and vice versa.>>> p = create_puzzle(3, 3) >>> p = create_puzzle(3, 3)>>> p2 = p.copy() >>> p2 = p.copy()>>> p.get_board() == p2.get_board() >>> p.perform_move(1, 1)True >>> p.get_board() == p2.get_board()False>>> p = create_puzzle(2, 2) >>> for i in range(2, 6):>>> for move, new_p in p.successors(): p = create_puzzle(i, i + 1) print move, new_p.get_board() print len(list(p.successors())) (0, 0) [[True, True], [True, False]] 6(0, 1) [[True, True], [False, True]] 12(1, 0) [[True, False], [True, True]] 20(1, 1) [[False, True], [True, True]] 30Hint: For efficient testing of duplicate states, consider using tuples representing the boards of the LightsOutPuzzle objects being explored rather than their internal list-based representations. You will then be able to use the built-in set data type to check for the presence or absence of a particular state in near-constant time.>>> p = create_puzzle(2, 3) >>> b = [[False, False, False],>>> for row in range(2): [False, False, False]] for col in range(3): >>> b[0][0] = True p.perform_move(row, col) >>> p = LightsOutPuzzle(b) >>> p.find_solution() is None>>> p.find_solution() True[(0, 0), (0, 2)]Once you have implemented the functions and methods described in this section, you can play with an interactive version of the Lights Out puzzle using the provided GUI by running the following command:The arguments rows and cols are positive integers designating the size of the puzzle.In the GUI, you can click on a light to perform a move at that location, and use the side menu to scramble or solve the puzzle. The GUI is merely a wrapper around your implementations of the relevant functions, and may therefore serve as a useful visual tool for debugging.In this section, you will investigate the movement of disks on a linear grid.The starting configuration of this puzzle is a row of L cells, with disks located on cells 0 through n 1. The goal is to move the disks to the end of the row using a constrained set of actions. At each step, a disk can only be moved to an adjacent empty cell, or to an empty cell two spaces away, provided another disk is located on the intervening cell. Given these restrictions, it can be seen that in many cases, no movements will be possible for the majority of the disks. For example, from the starting position, the only two options are to move the last disk from cell n 1 to cell n, or to move the second-to-last disk from cell n 2 to cell n.Your solver for this problem should be implemented using a breadth-first graph search. The exact solution produced is not important, as long as it is of minimal length.Unlike in the previous two sections, no requirement is made with regards to the manner in which puzzle configurations are represented. Before you begin, think carefully about which data structures might be best suited for the problem, as this choice may affect the efficiency of your search.>>> solve_identical_disks(4, 2) >>> solve_identical_disks(4, 3)[(0, 2), (1, 3)] [(1, 3), (0, 1)]>>> solve_identical_disks(5, 2) >>> solve_identical_disks(5, 3)[(0, 2), (1, 3), (2, 4)] [(1, 3), (0, 1), (2, 4), (1, 2)]Your solver for this problem should again be implemented using a breadth-first graph search.As before, the exact solution produced is not important, as long as it is of minimal length.>>> solve_distinct_disks(4, 2)[(0, 2), (2, 3), (1, 2)]>>> solve_distinct_disks(5, 2)[(0, 2), (1, 3), (2, 4)]>>> solve_distinct_disks(4, 3) [(1, 3), (0, 1), (2, 0), (3, 2), (1, 3),(0, 1)]>>> solve_distinct_disks(5, 3)[(1, 3), (2, 1), (0, 2), (2, 4), (1, 2)]