Sudoku is a puzzle that has been found in most newspapers since it gained popularity in 2005. Typically, the puzzle is played with a 9x9 grid that is subdivided into nine 3x3 boxes. The object of the puzzle is to fill the grid such that the digits 1 to 9 are contained (without repeats) in each row, each column, and each box. Seed digits are initially placed in the grid to define the puzzle and to limit where additional digits can be added by the person solving the puzzle. When trying to solve a sudoku, people rely on logical reasoning to determine where certain digits can and cannot be placed in the grid.
Create a program that can validate sudoku puzzles, because nobody wants to try to solve a puzzle with no solutions. The program should read a sudoku puzzle from a text file that is specified as a command line argument. The sudoku puzzle text file contains 81 integers between 0 and 9. The integers specify the contents of each cell in row major order and 0 is an empty cell. The program should print whether there are is a valid solution to the puzzle or not
To verify that a puzzle has a solution, you should create an algorithm using backtracking, implemented using either recursion or a stack. Note, the actual number of solutions does not need to be calculated, only whether there is a solution. In fact computing the exact number of solutions for a puzzle with no seed values would take a very long time.
In order to find a solution to a puzzle using backtracking. The puzzle is repeatedly filled with the smallest valid values possible. When a cell is encountered that can not be filled with any valid value then the program backtracks to the cell that was last filled, and tries the next highest valid value. If the program backtracks to the first 0 cell and can not find a valid value for it, then there are no solutions to the puzzle. If the program fills all 0 cells with valid values, then there is at least one solution to the puzzle.
The zip file puzzles.zip contains three puzzle text files that you can use to test your program. One of the puzzles has no solution, one has one solution, and one has multiple solutions.
Submission: Submit your code as a zip file with your name as the zip file name on the course Inquire site.
Write down an outline of your program in .py files. You should define what classes you need, what the attributes of those classes will be, and what methods each class will have. For each attribute and global variable, define the datatype being stored within, and their purpose. For each method, define their Pre and Post conditions.
You are only required to provide test cases for the board validation
methods you will need to write. There will be at least three
methods for validation: Row validation, Column validation, and
Box validataion. For each method of
the validataion, provide at least 2 test cases that can be
used to verify that your code meets the requirements. One test case
should be executed on a valid section of the game board, and the
other should be executed on an invalid section of the game board.
You can write all six test cases in a file
called test_board_validataion.py.
Be sure to provide comments in this file, with the expected result
of each test case.
All of what you define here can (and probably will) change by the time the final program is written. This is just to get you started thinking about the problem before Wednesday.
Submission: Submit your files as a zip file with
named First_NameLast_Name_Tests.zip,
replacing First_NameLast_Name with your name.
Due Monday, April 8th by 10:00 pm
Multiple Solutions: It is much more enjoyable to solve a sudoku puzzle when there is exactly one solution. It's easy to determine if a puzzle has at least one solution, but conceptually a little bit trickier to determine if it has more than one solution. Modify your backtracking algorithm to determine if there are 0, 1, or more than one solution to a given puzzle. In order to find if there are multiple solutions, backtrack after filling all 0 cells and see if a higher value in a cell also produces a valid solution.
Puzzle Generation: Write a program that can generate a random puzzle with only one solution. The program should begin by creating a puzzle that is completely empty. Then program should choose a random cell and generate a random seed value. If the puzzle has no solutions, the cell should be set back to its previous value and a different random cell should be selected. If the puzzle has multiple solutions, then another random cell should be selected. This should proceed until the puzzle has only one solution. Note, this algorithm has a flaw, sometimes it will generate an infinite loop. Can you write a version that will never fall into an infinite loop?
Command Line Game: Write a command-line sudoku game. The game should display the puzzle for the player and ask for a move (a row, column, and value). If the move is legal and it is correct it should add modify the puzzle and prompt the user for another move. If the move is not legal or correct the program should inform the user and prompt the user for a different move. The program should also determine if the user completed the puzzle and stop the loop with a congratulatory message. A harder version of the game would end the loop and tell the player they lost as soon as they make a move that is not correct. A more frustrating version of the game would let the user make incorrect moves and inform the player they lost when it is no longer possible to make a valid move.