## ## 2006 Utah High School Programming Contest, University of Utah ## ## README ## ############################################################################### The files in this directory provide a "skeleton" for implementing your solution to this year's take-home problem for the Utah High School Programming Contest. The skeleton compiles and runs, but does a relatively poor job at solving Sudoku puzzles. You will need to add your own code to the skeleton in order to improve its puzzle-solving abilities! COMPILING AND RUNNING THE SKELETON ---------------------------------- The skeleton is written in standard Java (1.4), and so it should compile easily with any modern Java compiler or IDE. If you have the `Ant' build tool for Java, you can use the provided `build.xml' file to compile the program. Once you have compiled the program, you can run the program by giving it the name of a Sudoku file. A simple Sudoku is provided with the source code in the file `sample.txt'. Assuming your Java interpreter is named `java', running the command: java Sudoku sample.txt should produce the output: 967541283 381279564 452683197 295136748 746892351 138457629 879325416 623914875 514768932 If you have trouble compiling or running the skeleton program, send email to for assistance. OVERVIEW OF THE SKELETON SOURCE CODE ------------------------------------ The skeleton consists of the following classes: Sudoku defined in `Sudoku.java' This is the "main class" for the Sudoku-solving program. It contains the top-level logic for the program and implements the program's command-line interface. All the "real work" of solving puzzles, however, is performed by other classes. Board defined in `Board.java' A Board represents the overall state of a Sudoku puzzle. Basically, a board is an two-dimensional array of Square objects. The possible values of a square are represented by a Square object within the array. Additional constraints on the values of squares are represented by "group" objects: RowGroups, ColumnGroups, and BlockGroups. A Board collects all of these things that describe a board, and makes them available via "getter" methods. BoardIO defined in `BoardIO.java' This class contains methods for initializing Board objects from files and other input sources, and for printing Board objects. Placing these I/O methods in a separate class helps to keep the Board class simple. Square defined in `Square.java' A Square represents a space on a Sudoku Board. The primary job of a Square is to keep track of the values that it may contain. Initially, a square can contain any legal value. Over time, other objects tell a square what values it can and cannot have. Whenever a square learns something new about its possible values, it passes the information to a Solver, which is responsible for propagating the information along to other objects. ConstrainedGroup defined in `ConstrainedGroup.java' A ConstrainedGroup represents a group of squares within a Sudoku Board. Each Square within the group must have a unique value. ConstrainedGroup is the (abstract) superclass for other classes that represent particular kinds of groups on a Sudoku board: i.e., rows, columns, and blocks. Although the shapes of the various groups are different, all groups share the rule that every member of the group must have a unique value. The purpose of the ConstrainedGroup class is to capture and implement that rule. *** We have intentionally left an important part of this class unfinished. *** See the "TODO" in the `ConstrainedGroup.processIsNot()' method. RowGroup defined in `RowGroup.java' ColumnGroup defined in `ColumnGroup.java' BlockGroup defined in `BlockGroup.java' These classes represent groups of squares within a single row, column, or block, respectively. These are all kinds of ConstrainedGroup. Solver defined in `Solver.java' A Solver drives the solution steps for a particular Board. To do this, a Solver keeps track of facts that are learned about the values of the squares on the board. When a fact about a board becomes known, the Solver for the board is notified. The Solver remembers the facts as Updates, which are kept in a queue. The initial set of Updates for a board is generated when the Board object is initialized with data. *** The board may or may not be completely solved when the Solver runs out *** of updates to process! This should be fixed in some way: e.g., by having other objects make better updates, or by making the Solver more powerful in some way, or by creating new kinds of objects that can help a Solver get "unstuck." Update defined in `Update.java' An Update represents a fact that has become known about a Sudoku board. The are two kinds of facts. An "IS" fact says what the value of a square is, and an "IS_NOT" fact says what the value of a square is not. UpdateQueue defined in `UpdateQueue.java' An UpdateQueue is a straightforward container of Update objects. Updates are stored and retrieved in first-in, first-out order. The main steps of the program are brought together in the Sudoku class. + First, the program creates a Board object and a Solver object. + Second, the Board is initialized using data from the input file. The process of putting data into the Board causes a bunch of Updates to be created and queued up for the Solver. + Third, the Solver is invoked to solve the Board. This works by having the Solver process Updates, which puts more information into the board's objects (the squares and groups), which in turn causes more Updates to be given to the Solver. This process continues until the Solver runs out of updates to process. + Finally, the program prints the final Board. If the Solver managed to fill in every square correctly, then the puzzle was really solved. If not... well, you should do something about that! FINAL ADVICE ------------ There are two main "missing parts" of the skeleton. The first missing part is the code for the `ConstrainedGroup.processIsNot()' method. This method must deal with the consequences of "is-not" facts. An "is-not" fact says that a certain square cannot hold a particular value. There are comments in the code that describe what the method should do; you should turn those comments into working code! The second missing part is some facility to add more "power" to the Solver. After you implement `ConstrainedGroup.processIsNot()', you'll see that the current Solver can handle simple Sudoku puzzles but not very hard ones. You need to figure out why this happens and decide how to handle those cases! There are many possible ways to give the program more puzzle-solving power. You should do some research and learn about advanced techniques for solving Sudoku puzzles, including rules such as "X-Wing" and "Swordfish." You can implement any techniques that you want, but remember --- YOUR TEAM MUST WRITE *ALL* OF THE CODE IN THE PROGRAM THAT YOU HAND IN!!! Except for the skeleton program we provide, which we REQUIRE you to use, COPYING CODE FROM SOMEONE ELSE IS CHEATING!!! If we discover that your program contains code that your team did not author, your team will receive NO CREDIT for its solution to the take-home problem!!! As you work on your program, you will probably find it useful to put various "sanity checks" in the code. This technique is part of what programmers call "defensive programming," and it is extremely useful for finding bugs. If you have a question about the take-home problem, first check the list of frequently asked questions (FAQ) on the Web. With luck, your question will already be answered there! If you can't find an answer in the FAQ list, then contact us by sending email to . We will answer your question as soon as possible. We might also add your question to the frequently asked questions list. Finally, remember to check the 2006 Utah High School Programming Contest home page for late-breaking news and contest updates! Good luck! ############################################################################### ## End of file.