Sudoku Solver

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. Even though our computers are inherently logical devices, it might make more sense to smartly "brute-force" a solution to the problem.

Setup

Create a directory assignment10 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment10
cd assignment10

Details

You are going to write a program that will compute the number of solutions a sudoku puzzle can solve. To accomplish this, you will read a sudoku puzzle from a text file. This text file is very similar to the text file from Assignment 1: it contains 9 lines of 9 characters each. Each character is a digit 0 - 9, where 0 represents an empty space, and 1-9 specifies that value. Your program will print the number of solutions for that puzzle you read in.

To compute the number of solutions, you will create a backtracking algorithm using either recursion or a stack. Note: the actual number of solutions does not need to be calculated. Instead, you will simply specify if there are 0 solutions, Exactly 1 solution, or More than 1 solution for the given problem. Computing the exact number of solutions for a puzzle with no seed values would take a very, very long time.

The backtracking solution will be similar to the maze backtracking solution discussed in class. Instead of incrementally selecting which cell to explore next, however, we will incrementally select a new value for the cell we are currently in. We will do this by first trying to assign the value 1 to the current cell, and then try to assign values to the next cell in the list. If, through backtracking, we return to this cell without finding a solution, we will try the value 2. We will then try to assign values to the next cell in the list. It will continue this process until it either finds the requisite number of solutions, or it unsuccessfully found a solution after assigning 9 to the current cell. If you weren't able to find a solution, you reset the cell back to 0, and backtrack to the previous cell. You will continue this process for every cell until you find out there is more than one solution, or you have exhausted all of the possibilities.

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.

Program Outline

Write down an outline of your program on paper. You should define what classes you need, what the attributes of thos classes are, and what methods each class will have. For each attribute, define the datatype being stored within and their purpose. For each method, define their Pre and Post conditions.

This is due Monday, March. 31st. All of what you define here can (and probably will) change by the time your final program is written. Consider this an "rough draft" for your program. This will help you get started thinking about the problem before Monday.

Submission

You are required to submit a tar file to http://cseval.roanoke.edu/. On cseval, there is a link for Assignment 10. You can create a tar file by issuing the following commands: 

cd ~/cs170/assignments
tar czvf assignment10.tgz assignment10/

"Hacker" Prompt

  1. Puzzle Generation: Add a function to your program that can generate a random puzzle with exactly one solution. Your program will begin by creating a puzzle that is completely empty. Your 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 0 and another 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.

    This algorithm has a handful of flaws, but the most notable of which is that it is possible to have a legitimate infinite loop. Can you write a version of this algorithm that avoids this case?

  2. Hints: Another useful aspect of this program is that it can also generate the solution for a game. You could use this to generate a hint for a stuck person. You essentially have the entire solution, so a hint is just an arbitrary answer from the solution.

    However, random hints from the solution is not entirely helpful. What you really want to find are the hints that "reveal" the most information about the solution to the problem. Ideally, with one hint, the user could continue on their own for some amount of time without needing another hint.

    For the current state of the board, compute all of the possible values for each of the cells. When you reveal a certain location, you remove that value from all of the cells in the row, column, and box. This will "reveal" some number of additional cells - all of the cells that no longer have additional conflicts. Find the hint that maximizes the number of "revealed" cells.

  3. Integration: Add to your Assignment 1 code, so that it randomly generates a sudoku puzzle at the start of the game. Then, add a hint button that will provide a hint for the user when pressed.

Last modified: Tue Apr 1 16:29:57 EDT 2014