This assignment cannot be dropped. However, you may hand this assignment in late by Friday, August 8, at 5:30PM, with a 2-point penalty.
For this assignment, you will create a Python source file containing a Python function(s) implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Python source file as the primary function they help. You should store your source file lights_out.py in a folder named pa11.
Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)
The game of Lights Out is single player game played on using a 5x5 grid of lights. Each light of the grid is either lit or unlit. The goal of the game is to turn off all of the lights. Each turn, the player selects one of the lights on the grid, and then that light and its four neighbors will be toggled (lights that are on are turned off and those that are off are turned on). The neighbors are above, below, to the left and to the right of the light. Note that lights along the edge don't have all four neighbors. Jaap's Puzzle Page has an online version of Lights Out that you can play in your web browser.
For example, consider the arrangement of lights shown at left below. The lights that are on are shown as yellow circles and the lights that are off are shown as black circles. Each circle is additionally labeled with its coordinate. If the player, selects the light in column 2 of row 0, this would turn off that light and also the lights at (0,1), (0,3), and (1,2), as shown below in the middle. If the player, then, selects the light at (1,0), it would turn off the lights at (1,0), (0,0), and (2,0) but turn on the light at (1,1).
|
|
|
Note that the maximum number of lights that can toggle at any given time is 5 (the chosen light and a maximum of four neighbors).
In this assignment, you should start by downloading a copy of the file lights_out.py into your pa11 folder. Read through the first two functions we give you to see how they work. You are responsible for understanding all of the code we've given you. The main function that you run to play the game is called play().
You will see that the file we give you has all of the functions represented as "stubs". This means that each function is written so that it returns something so that the entire program will run without crashing if you haven't completed all of the functions. As you complete each function, replace the code we give you for the function in question with your own code, but leave the subsequent stubs in place until you have tested your current function completely.
[2 points] Compelte the function rand_board(), so that it will return a 5x5 matrix (2D list) where each element is randomly set to 0 or 1.
Example:
>>> seed(15110) >>> rand_board() [[0, 1, 0, 0, 1], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 1, 1, 0, 0], [1, 1, 0, 0, 1]]
[2 points] Complete the function, display(board), so that it will display the 5x5 matrix board. It should, first, create a gray background. Then, it should place a yellow circle in each position corresponding to where board has a 1, and a black where board has a 0. It should also place the coordinate of the position (row, comma, column) in red at the center of each circle.
Example:
>>> seed(15110) >>> b = rand_board() >>> b [[0, 1, 0, 0, 1], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 1, 1, 0, 0], [1, 1, 0, 0, 1]] >>> Canvas.init(225,225,"LightsOut") >>> display(b)
You will need to use the following Canvas elements: Circle, Text.
At this point, you should be able to call play() to display an initial random board, but it will not do anything when the player enters coordinates for a light to be selected.
[2 points] Complete the function, select(board, i, j), so that it will toggle the lights in board at position (i,j) and the four neighbors of (i,j). (BE CAREFUL: the selected position might not have all four neighbors if it's on the edge of the board.)
Example:
>>> b = [[1, 0, 0, 0, 1], [0, 1, 1, 1, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 1]] >>> b [[1, 0, 0, 0, 1], [0, 1, 1, 1, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 1]] >>> select(b,2,0) >>> b [[1, 0, 0, 0, 1], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 1, 0, 0, 1]]
At this point, you should be able to use play() to play lights out, except that the program won't stop once you have won.
[2 points] Complete the function, all_out(board), so that it will return True if and only if all of the lights in board are turned off. It should return False otherwise.
Example:
>>> b1 = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] >>> b2 = [[1, 0, 0, 0, 1], [0, 1, 1, 1, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 1]] >>> b3 = [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] >>> all_out(b1) True >>> all_out(b2) False >>> all_out(b3) False
At this point, you should be able to use play() to play lights out, but since the majority of boards are unsolvable, you might want to play with a solvable board, by using the play_with_board function:
>>> play_with_board([[1, 0, 0, 1, 1], [0, 0, 0, 1, 1], [1, 1, 0, 1, 1], [0, 1, 0, 1, 1], [0, 1, 1, 1, 1]])
Turn all of the lights black.
Enter row (0-4): 1
Enter column (0-4): 0
Enter row (0-4): 1
Enter column (0-4): 3
...
Enter column (0-4): 2
Enter row (0-4): 4
Enter column (0-4): 4
You won!
Hint: to solve this board, start in row 1 and work your way down, selecting in each row the lights that are on in the row above it.
[2 points (harder)] Complete the function, solvable to determine whether a board is solvable.
Whether a Lights Out board is solvable can be determined by counting the lights that are on in particular positions. Specifically, there are two sets (QP1 and QP2) of light positions, called "quiet patterns". If the number of lights that are on in positions contained in QP1 is odd, then the board is unsolvable. Likewise, if the number of lights that are on in positions contained in QP2 is odd, then the board is unsolvable. Otherwise, the board is solvable.
QP1: |
(0,0),(1,0),(3,0),(4,0), (0,2),(1,2),(3,2),(4,2), (0,4),(1,4),(3,4),(4,4) |
 |
QP2: |
(0,0),(0,1),(0,3),(0,4), (2,0),(2,1),(2,3),(2,4), (4,0),(4,1),(4,3),(4,4) |
 |
For example, consider the board [[1, 0, 0, 0, 1], [0, 1, 1, 1, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 1]] (shown at right). If we examine the positions in QP1, we find that: (0,0) is on, (1,0) is off, (3,0) is on, (4,0) is off, (0,2) is off, (1,2) is on, (3,2) is off, (4,2) is off, (0,4) is on, (1,4) is off, (3,4) is on, and (4,4) is off. Thus, for this board, there are five lights in QP1 positions that are on. Since five is odd, the board is unsolvable.
If, however, there had been an even number of lights in QP1 positions, we would have also needed to check the number of lights in QP2 before determining whether the board is solvable.
Outline of algorithm:
Let board be the matrix (2D list) indicating which lights are lit, and let qp1 and qp2 be lists where each element is a position from QP1 or QP2, respectively. Go through the elements of qp1 adding up the values at those positions in board. Return False if this sum is odd. Do the same for qp2. If neither sum was False, return True.
Your function should be written using loops as indicated in the comments in the starter code.
Example:
>>> solvable([[1, 0, 0, 1, 1], [0, 0, 0, 1, 1], [1, 1, 0, 1, 1], [0, 1, 0, 1, 1], [0, 1, 1, 1, 1]]) True >>> solvable([[1, 0, 0, 0, 1], [0, 1, 1, 1, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 1]]) False >>> solvable([[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0]]) False >>> solvable([[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0]]) False
If you complete solvable correctly, you should now be able to call play() and always get a randomly generated, but solvable, board. Your game is done!
You should have a pa11 directory, containing:
Zip up your directory and upload it using the autolab system. Submissions after the deadline but before the late deadline will be marked on our system as "late".
There is a strategy that will solve any solvable Lights Out, which is described on the Jaap's Puzzle Page. You may want to see if you can implement this as Python code. You could even animate the solution.