The project for this year's take-home problem is the implementation of a Sudoku puzzle solver. Your program will input an unsolved puzzle, figure out how to complete it, and output the result.
Sudoku puzzles have become extremely popular in Japan and England in recent months and are quickly catching on in this country. For those of you who have not seen them, here is a brief description.
The puzzle is a 9 by 9 array of boxes. This array can be perceived in three different ways. It contains 9 rows of 9 boxes each. It also consists of 9 columns of 9 boxes each. The third way to look at it is that it's a 3 by 3 array of groups, each of which contains a 3 by 3 array of boxes. The solved puzzle has each of the digits 1 through 9 in each row, each column, and each group.
Here's an example of a simple Sudoku puzzle. You are given a partially filled array, and your challenge is to fill in the blank spaces such that the above rules are satisfied.
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
Although they contain numbers, these puzzles are really not mathematical in nature. The numbers in the boxes could just as well be characters of any kind. Successful completion simply requires a series of logical steps.
There are many Web sites that help you learn about Sudoku puzzles. The above example comes from Let's Play, which includes a number of hints to get you started and a solution to the puzzle shown above.
Some Sudoku puzzles are quite simple to solve, and others are extremely challenging. The level of difficulty is usually indicated by some number of stars. The puzzle above is rated as a single-star puzzle, indicating that it should be quite simple to complete. A very difficult problem might have a five-star rating.
It is extremely important that you strictly adhere to the input and output format requirements. This will allow us to efficiently and accurately judge your submissions.
Your Sudoku solver program will get its input from a file that contains one unsolved puzzle to analyze and complete. The files will be formatted as shown in this example file called sampleinput.txt. The contents of the file are shown below.
6 1 7 6 5 8 1 32 5 4 8 4 7 2 9 8 1 7 12 5 3 6 7 8 2 4
As you can see, an input file contains exactly nine lines of text, and each line of text contains exactly nine characters. (The lines that appear to be "short" actually have spaces at the end.) The rows and columns of input correspond in the obvious way to the squares in a Sudoku puzzle. A digit between 1 and 9 corresponds to a "given" square in the Sudoku puzzle: in other words, one that is given as part of the puzzle set-up. A space means that the value in the corresponding square is unknown. These, of course, are the squares that your Sudoku-solving program must fill in.
The name of the file you want to use will be specified on the command line as follows for C++:
sudoku sampleinput.txt
or in Java:
java Sudoku sampleinput.txt
The output of your program must be in the same format as the input. To repeat ourselves, there must be nine lines of nine characters each, and every character must be either a digit or a space. If your program was able to completely solve the puzzle, then there won't be any leftover squares with unknown values, and there won't be any spaces in your program's output.
So, given the sampleinput.txt file as input, your program should produce the following output:
536827941 172964358 894153267 715349826 643782195 928516734 481295673 369471582 257638419
This output is contained in sampleanswer.txt.
If your program isn't able to completely solve a puzzle, there will still be squares with unknown values. Those squares must be represented as spaces in your program's output. Your program should always output its final answer, even if that answer is incomplete. When we score your program, we will give partial credit for partially solved puzzles.
Your program must send its output to "standard output." In C++, the
standard output stream is known as cout. In Java, the standard
output stream is known as System.out. Your program must
not send anything other than its answer to standard output.
Finally, your program must produce its answer within ten seconds.
Now that you know what to do, you can get started! We are providing you with a basic Sudoku-solving program, implemented in both C++ and Java. You must use this program as the basis for your solution. The additions and enhancements that you make must be added to the structure provided. Before you start coding, be sure to carefully study the README file that comes with the basic program.
Except for the skeleton program that we give to you, all of the code that is part of your program must be written by you and your teammates. Because Sudoku is so popular, many programs for solving Sudoku puzzles are already available on the Web. We are familiar with many of those programs. Copying code from any program that you did not write is plagiarism. Copying someone else's work is cheating, even if you make changes to the code that you copy. So don't do it.
We will provide you with a set of test files (the Practice Set) that you can use to test your program. These files will contain Sudoku puzzles of varying difficulty. We will also give you the answers to these test puzzles, so you can compare your program's output to the correct answers. The test files and answers will be formatted as described above. These test files are available now.
Of course, you should test your program with puzzles beyond the ones that we give to you. Fortunately, because Sudoku is so popular, it is easy to find lots of puzzles on the Web. Some popular Sudoku sites include:
And there are many, many more sources of Sudoku puzzles as well, including books and other Web sites. As you add new and more powerful capabilities to your program, you can test it on increasingly difficult problems.
On March 17, we will test your program with a different set of input files (the Test Set). We will not make the Test Set available to you. A system that uses general techniques should work just as well on the Test Set as it does on the Practice Set. A system that has lots of hacks and tweaks based on the Practice Set, however, probably will perform very poorly on the Test Set. WARNING: You will be given the answers for the Practice Set, but your system is not allowed to use them when solving the puzzles!
Your solution to the take-home problem must be submitted on the day of the contest. Please follow these directions carefully, as improper submissions may prevent your program from being judged.
Bring the following with you when your team checks in:
Your source code must be commented liberally and use good programming style. Your comments must explain the key algorithms and design so that we can better understand your program.
For your compiled executable, if your submission is written in C++, you must submit a single executable file named sudoku so that we can run it with the command:
sudoku input.txt
If your submission is written in Java, you must ensure that you submit compiled .class files. The class that contains the main function must be called Sudoku so that we can run your program with the command:
java Sudoku input.txt
Your readme.txt file must contain the name of your school, the name of your team, and the names of the members in your team. It must indicate what development environment you used and instructions for recompiling your code. If it becomes necessary, we will recompile your code from source. It must compile with one of the following compilers: Microsoft Visual C++.NET 2005 or earlier, GCC/G++ 3.4 or earlier, or Sun's Java SDK 1.5 or earlier. Note that all C++ code must by ANSI C++ compliant, so you should not use features that are specific to an individual compiler and/or platform.
Additionally, your readme.txt file should briefly explain what you did and why, and anything else you tried that you didn't use in your final solution. Explain what you learned while working on the take-home problem.
Your feedback.txt file should contain information so that we can continue to improve the contest. What did you think about the problem? How difficult or easy was it? What were the hardest and easiest parts of the problem? Provide any other comments that you think may be useful to us as we develop future take-home problems.
Your Sudoku-solving program will be scored on two things: its ability to solve the Sudoku puzzles we give to it, and the quality of the code and documentation that you create.
When we test your program on a puzzle, we will award points based on the number of squares that were correctly filled in. Even if your program cannot find the value of every square, it should still output the partially completed board to show what is was able to discover. In this way, you can get "partial credit" for a puzzle.
We will deduct points for squares with incorrect values. Furthermore, if your program changes one of the given squares (i.e., one that is specified in the input), your program will receive zero points for that puzzle.
We will deduct points from your total score if your program fails to meet the I/O requirements described previously — so get them right! Also, as described previously, your program must output each of its answers in a timely manner. If your program exceeds the time limit for a puzzle, no points will be awarded for that input.
To compute the final scores for the take-home problem, each Sudoku-solving program will be ranked on the criteria listed above relative to the other programs in the competition. This score will be scaled so that the team with the highest average receives 200 points.
You may be wondering, "Okay, so now what do we do now?" For starters, you might find it useful to use your favorite Internet search engine to dig deeper into Sudoku problem-solver issues and techniques. (Google is your friend!) For example:
The README file in the skeleton program offers some initial advice for improving the basic code. The skeleton is designed to be extensible in several different ways, so that you can implement the whatever puzzle-solving strategies you invent or discover.
Solving Sudoku puzzles can be a tricky business, with many things to keep track of. Your program doesn't have to be perfect in order to be good. A really nice thing about Sudoku is that the puzzles range in difficulty from very easy to very hard. You can add strategies to your program in stages, so that it grows to handle harder and harder puzzles.
We encourage everyone to have fun with this project and experiment with lots of ideas. While there are some fairly standard ways of approaching this problem, creativity is highly encouraged!
Finally, we encourage you to start early!
If you have any questions, please check our Frequently Asked Questions page. If you don't find answers there, email your questions to hspc@cs.utah.edu.