Sudoku Solver Using Threads in Java

Sudoku Solver Using Threads in Java

System Design

Jeff Russo

Dr. Beidler

10/15/2010

Submitted in partial fulfillment of the requirements of CMPS 490 – Computer Projects

My Sudoku solver is designed for performance as well as user-friendliness. It is a threaded program written in Java which makes use of many concurrency tools and principles. The program is designed to run many logical components concurrently while displaying this to the user through a GUI developed using swing. The GUI is designed to prevent any possible user errors and make input easier to do. I am splitting up my logic into different classes extending thread which are each implemented as individual solving techniques. Each individual square is a thread as well for GUI and object creation reasons. To contain and synchronize all these threads, there is a main controlling thread.

A. Static Driver

The first level in the design is a static driver. This runs the whole program. It prompts the user, asking him/her if they would like to enter a puzzle and if they would like the computer to solve it. It then sends these boolean values to the main driver thread which runs the game.

B. Main Controlling thread

The second level of design is the main controlling thread. It will display the GUI for the user to enter a puzzle if he/she wishes to. Once the puzzle is received from this GUI, the main thread will begin solving the puzzle. If a user-puzzle is not entered, a random one will be selected from a database of puzzles. This main thread is responsible for controlling the flow of the program as well as synchronizing all other threads. I am using java’s wait/notify system for synchronization. It is very efficient and does not use up any resources.

This thread will create a puzzleGetter class if the user would like to enter a puzzle. This class is not threaded, because there is no reason or need to do it. At all times while this class is being used there is only one thing going on at a time. The class contains a similar GUI to the solving one, but it is used differently. There is a nine by nine grid of squares, each containing a three by three grid of JButtons which have the numbers 1 through 9 on them. This represents the possibilities for that square. When a user clicks one of these buttons, that number is selected for that square and that possibility is removed from neighboring squares where it can no longer go. This prevents the user from putting the same number in the same row, column, or sub-square. There is an undo on this GUI. Moves are put on a stack as they are made. The undo button will pop the most recent and do the reverse of it. This system eliminates the use of the keyboard to enter moves and prevents unwanted input.

If the user decides to get a puzzle from the database, this thread will chose a random one and then solve for it. This will be a simple database using JDBC. There will only be one table with index and board columns.

The main controlling thread is then used to start the solving process. All square threads are created. The main thread waits until they are all made and is then notified. After this, the GUI is created and shown. Finally, the solving threads are created and started. They will run until the puzzle is completed.

C. Solving threads

The final level of my design is the low level solving techniques. There are six in use in my program. They are all run as separate threads independent of one another, but dependent on the current state of the solving process on the puzzle. This causes the need for concurrency tools and a way of working off the board in a given state instead of just working off the original. In all solving techniques that use more than one square at a time, I created a method to essentially copy the board to a new board object. This is a hindrance to performance, but is necessary to avoid mistakes.

Another concurrency tool I am using from Java’s libraries is the AtomicInteger. This was extremely helpful to my project as I was having errors from thread interference. The AtomicInteger is guaranteed by Java to do its operation atomicly. This removes the need for semaphores. There seemed to be a slight gain in performance from using the AtomicIntegers over semaphores.

D. Data structures

I am using basic data structures in most of my program. BitSets are used to represent the possibilities for a given square because there are many operations relevant to solving the puzzle than can be done to them. Java’s BitSet library gives operations like and, or, Xor, and andNot. These operations combined give results needed to run the most difficult solving techniques. Without using these, there is over double the code and many more nested for loops. This caused a performance increase in my program and made the discrete math of solving Sudoku’s much easier to code.

E. Algorithm Design

There are many different algorithms used in this project, each being completely unique. Each solving thread runs through its algorithm until the puzzle is completed. It repeats the same process until it cannot do anything else.

The simplest algorithm is to look at every individual square and see if it has a single possibility or the only occurrence of a possibility in a solution set. A solution set is defined as a row, column, or sub-square. This technique is done with the square threads. After a possibility is removed from a given square, it checks itself to see if it has been narrowed down to one and will then solve itself if it is. There is also a separate thread running simultaneously looking for squares with multiple possibilities, but only a unique possibility to a given solution set.

Moving up in difficulty, the set finder looks for a subset of squares within a solution set with a number of possibilities equal to the number of squares in the subset. The solving thread looks at a solution set and then takes every possible combination of squares out of it as a subset. From here, it looks for the above mention occurrence. When it is found, that set of possibilities can be removed from the possibilities of the surrounding squares in the solution set. To do this, I am using a removeSet() method instead of my original removePoss() method as it is less code and makes better use of the BitSet library.

The remaining solving techniques are related to the set finding technique, but combines into multiple solution sets. In essence, a subset can be found within three or four separate solution sets that are “linked”, meaning the squares are located in both solution sets. These techniques take the most time and resources to run, and are not used very often, so I put them to sleep for a short amount of time (less than a tenth of a second) every time they enter the algorithm.

F. Real-Tine Design

To ensure my GUI is being updated properly, all my methods modifying it are written as runnable. This adds the method as a thread to the queue and Java makes sure it gets executed. This is important in Java swing as the method would have to be otherwise synchronized which would put a huge hindrance on performance.

G. User Interface Design

The user interface of my project is a simple Java swing application. It is designed for user-friendliness and to avoid user error. It displays the puzzle as a 9 by 9 grid of squares, each containing a 3 by 3 grid of possibilities, which are solved or unsolved according to the current state of the puzzle. When the computer solves the puzzle, the GUI cannot be modified by the user. When the user is entering the puzzle, each possibility is enabled. To select a number for a given square a user clicks on it. If the user makes a mistake, there is a fully functional undo button. As numbers are selected, they are removed from surrounding solution sets to avoid the user from entering a bad puzzle. This ensures my solver is being given a legitimate puzzle. This is much safer than having the user enter text as letters, escape characters, and other unwanted strings could be entered. My design also eliminates the need for the keyboard which adds to user-friendliness.

H. Help System

Throughout the process of selecting a puzzle and watching it get solved and solving it him/herself, the user is prompted with message boxes. These are messages giving the user directions or letting the user know they have made a wrong move. I think this process is simply enough that I would not need a separate help system. If I find in final testing that people are confused or need more direction I will add a help button to the GUI which will display further instructions.