Python basics

Python Homework 2 Assigned: 11/21

Due: 11/30, 11:59pm

Possible Points: 100

Submit on Canvas a zip file containing your solution code for each problem (just the .py files, please do not submit the solution/project files), turn in at least one .py file for each problem. Each problem specifies what you should title the file containing your solution so that the autograder can find it. Incorrectly named programs will not be graded and thus will get 0 points for the problem.

Since the assignment will be graded using an automated grading system you should have your program’s output match the sample output shown. If your program fails to run using Visual Studio 2017 it will receive zero points. If your program fails to run properly (runtime errors or wrong output) points will be deducted based on how correct is the program.

If you have any questions or concerns about the assignment do not hesitate to post on the discussion forum on canvas, send us message on canvas, or see us after class or during office hours.

Students are expected to write their source code from scratch, those who copy code from each other or web (including from Canvas examples) will be reported for cheating. We will also look at your code so do not just hard-code the answer and print it.

We strongly encourage to put the sudoku reading, printing, and checking into a separate module (so it can be reused in all problems) and submit it alongside the other .py files.

Example Input File (same for all problems except the last optional problem)

5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9

1

1. Reading Input: 20 points File: sudoku1.py

A sudoku game is played on a 9x9 grid and starts at some initial valid state. To play you have to first read the initial configuration of a grid. Since the player may want to choose a different starting grid for each game, you need to allow the user to type in the name of the file that contains the initial grid.

At the start of the program, prompt user for the filepath using the input() function. Open the specified file and read its content. The file will contain a 9x9 grid of numbers separated by spaces; 1-9 are valid start numbers and 0 denotes an empty cell. To verify that the grid was read correctly, print it out. You can assume the input will always be a valid sudoku grid and your program must read only one input file (do not use loop).

Console Session

Enter input filepath: input.txt 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9

2. Solving Sudoku: 20 points File: sudoku2.py

Read a sudoku grid as before from the user specified file. To play the sudoku game a user must be able to enter numbers into the grid. After you printed the initial grid, prompt the user for a row, column, and a number, set the content of the cell at position (row,column) to value “number” and print the updated grid. You must prompt the user only once. The input will be a valid grid and the row and column will be the index of a cell that is empty (one containing a 0).

Note: you will have to convert the number of the input grid to inte- gers to update the values in the grid. Each cell should have numbers in 0-9 range (with 0 indicating an empty cell).

2

Console Session

Enter input filepath: input.txt 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 Enter row: 1 Enter column: 2 Enter number: 1 5 3 0 0 7 0 0 0 0 6 0 1 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9

3. Validating Steps: 20 points File: sudoku3.py

You can assume that the input entered by the user is in a valid range: row and column is in the 0-8 range and “number” is in the 0-9 range. In this exercise you need to check if the input constitutes a valid step in solving the sudoku based on the rules of the game.

A valid configuration of the sudoku grid must satisfy following rules:

• each cell has a number in the 0-9 range • in each row no number in the range 1-9 can be repeated • in each column no number in the range 1-9 can be repeated • in each 3x3 subgrid no number in the range 1-9 can be repeated

For example, entering number 3 at row 0 and column 2 will violate both the row rule and the subgrid rule.

In this exercise, read the starting sudoku configuration by prompting user for the filepath as in part 1 or 2. When user enters a new number that violates the sudoku rules print a message containing rules that were broken ('Number X twice

3

Figure 1: Example of sudoku grid which consists of nine 3x3 subgrids (source Wikipedia).

4

in row', 'Number X twice in column', or 'Number X twice in subgrid'; check and print them in this order) and do not update the grid. If the number does not break any rule, update the grid and print it.

Console Session

Enter input filepath: input.txt 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 Enter row: 1 Enter column: 2 Enter number: 1 Number 1 twice in row 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9

4. Grid GUI: 20 points File: sudoku4.py

In the quest of building a user friendly sudoku application we have to create GUI as some users dislike console. In this part, you need to write Qt program that constructs a 9x9 grid consisting of nine 3x3 subgrids. Cells in the subgrids should be combo boxes that allow the user to select a number (see code presented in class for an example). Read the input file and fill the GUI with the initial grid. The user can perform moves using the comboboxes in the GUI but you are not required to check for the validity of the moves based on the sudoku rules.

5

Figure 2: Example sudoku GUI

6

5. Validation and Hints in GUI: 20 points File: sudoku5.py

Anybody doing sudoku on paper knows that it is quite suboptimal experience. Enhance the sudoku GUI and check these rules:

• in each row no number in the range 1-9 can be repeated • in each column no number in the range 1-9 can be repeated • in each 3x3 subgrid no number in the range 1-9 can be repeated

If the user makes a mistake, show a message with the specifics of the mistake and revert back to the previous value in the grid cell. Also, show a message if a solution to a sudoku was obtained.

Moreover, it is common to write down the possible numbers for each cell when solving a sudoku on paper. Modify your code so that each empty combo box shows only the list of valid numbers from the range 1-9. For each non-empty combo box show only the option to maintain the current value or clear the cell. For example, the possible choices that do not violate any of the rules in row 0 and column 2 are 1, 2, and 4. Similarly, for row 2 and column 2 the user should only have the two options of clearing the cell or maintaining the value 8.

Optional Sudoku Solver: 0 points File: sudoku_solver.py

Implement a sudoku solver that takes an input grid as before and prints out all solutions separated by a newline. Reuse code from previous problems, for example, for checking if candidate entry to a cell is valid or if sudoku is solved. Your program should find the solutions for the following input in less than 10 seconds.

Example Input File

0 0 0 0 7 0 0 0 0 0 0 0 1 0 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 0 0 3 0 0 1 0 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 3 9

Console Session

Enter input filepath: input.txt 3 5 4 6 7 8 9 1 2

7

6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 1 5 9 6 4 7 2 3 4 2 6 7 5 3 8 9 1 7 3 9 8 2 1 4 5 6 9 6 1 5 3 7 2 8 4 2 8 3 4 1 9 6 7 5 5 4 7 2 8 6 1 3 9

5 3 4 6 7 8 9 1 2 6 2 7 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 2 7 6 1 4 9 3 4 7 6 9 5 3 8 2 1 3 1 9 8 2 4 7 5 6 9 6 1 5 3 7 2 8 4 2 8 3 4 1 9 6 7 5 7 4 5 2 8 6 1 3 9

5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 7 9 6 1 4 2 3 4 2 6 7 5 3 8 9 1 3 1 9 8 2 4 7 5 6 9 6 1 5 3 7 2 8 4 2 8 3 4 1 9 6 7 5 7 4 5 2 8 6 1 3 9

5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 7 9 6 1 4 2 3 4 2 6 8 5 3 7 9 1 3 1 9 7 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 3 4 1 9 6 7 5 7 4 5 2 8 6 1 3 9

5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 3 1 7 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4

8

2 8 3 4 1 9 6 7 5 7 4 5 2 8 6 1 3 9

9