Sudoku Solver (SSolver) - Assistant to the Sudoku Player

Sudoku Solver

		Assistant to the Sudoku Player


		If you have any questions about our open source programs, or wish to obtain more information on our products, then please send a message to OpenSource@artige.com and we will happy to handle your request.



		The Sudoku Solver is an open source program that allows one to solve a Sudoku (or Soduko for us dyslexic folks) puzzle. This program does not generate new Sudoku puzzles. Rather, it will solve any valid game data set that is entered into the program. It is based upon our Ziffern mathematical game, and uses a similar look and feel, including the custom static control built to behave like a selector wheel. Game files can be created from the user interface, or typed into a text file using a text editor like Notepad. The SSolver program will generate the answers for a valid game, and allow the user to toggle between views of the game board with and without the answers. This way the user can determine what hints showed be used to figure out the game they are having difficulty in solving.

		The SSolver program is being offered under open source license (GPL), so that the user as could extend it as need be. One such extension would be to generate new Sudoku games. This solver application provides more then half the logic and wherewithal to write such a game program. There is a secondary purpose behind the drive to compose the Sudoku Solver. It was written to demonstrate how Operations Research principles could be applied to everyday activities, even in game design, which is one of the areas of specialty for the Artige Company. It also demonstrates the use of heuristics to figure out games, as well as solve business problems.

Available on this page:




Preview		Screen shots

		Below are twelve screen shots. They were all taken during a typical session working with the Sudoku Solver application. These screen shots were generated from a Windows* 2000 workstation.

		The first screenshot reveals what the user will see when the program is launched, after the splash screen times out. The user is presented with a traditional MFC GUI window that contains a menu bar, dockable toolbar, a status bar, and the playing area. This application uses the single document interface (SDI), so there can only be one puzzle open at a time. When launched, a blank 9*9 game board will be generated and ready for data entry.


		Typical view of SSolver upon successful launch


		If the player wishes to, a person's name can be entered into the program. This is accomplished by selecting the "View" menu item and then clicking on the "Player" submenu item. This is shown below.


		Selecting the option to name a player


		At this point the program will launch a dialog allowing the player to enter the desired name, as shown below.


		The player name dialog


		Now the player can observe that a name will appear at the top of all games in this session, as shown below.


		Playing area now shows the player's name


		In addition, the player can indicate the source of the Sudoku puzzle being entered into the solver. This is recommended if one is keeping track of the puzzles they are solving. This is accomplished by selecting the "View" menu item and then clicking on the "Source" submenu item, in a similar manner that was used to select the player's name above.

		At this point the program will launch a dialog allowing the player to enter the desired source of this puzzle, as shown below.


		The puzzle source identity dialog


		Now the player can observe that the puzzle source will appear at the top of all games in this session, as shown below.


		Playing area now shows both the player's name and puzzle source


		At this point the player can begin assigning digits to the cells. This is done by clicking on the desired symbol with the left mouse button. This action will bring up the number wheel selector control, as shown below. Here one will be able to select the desired digit by clicking on the appropriate sector. A selected digit will appear as a red sector. You can also review which digit was previously selected, as it will appear as a gray sector. The grayed sectors will no longer be available for selection. One can also unselect a selected digit at this point, by selecting the question mark.


		Assigning a digit to a cell using the number wheel selector control


		The number wheel will allow the user to replace the contents of a cell with the desired digit, regardless whether the cell held a question mark or a different digit, on a cell by cell basis. The result of assigning the digit "5" to the third cell of the top row is shown below.


		Result of depositing a digit in the third cell of the top row


		The alternative method of entering digits into a Sudoku game is to type them into a textfile, using a standalone text editor, such as Windows* Notepad. The format of such a file is shown below. The Sudoku data file is read from the "File - Open" menu item or from the open folder icon on the toolbar. The format shown must be followed exactly, or the program will fail to load your data.


		The contents of a Sudoku game data file, viewed through Windows* Notepad


		Once data entry is complete, one can prepare to generate the answers. This is shown below.

		By the way, if the questions marks are bothersome, you can set an option so that the SSolver program does not show them, and displays the cells without digits as blank. This is accomplished by pressing the question mark icon on the toolbar. This button acts as a toggle, so pressing it in will display the questions marks and leaving it out will hide them. The below figure also shows the result of hiding the question marks.


		Sudoku game with data entry complete


		To generate the answers, one will press the exclamation mark icon on the toolbar. In short order (less than 2 seconds, if even that long) the answers will be generated. The program will indicate the success of the answer generation in the status bar. If the phrase "Solved " appears, then the answer generation run was successful. If an answer could not be generated, the status bar will read "Not possible". At this point one will need to purposefully press the eye icon on the toolbar to view the generated answers. The below figure also shows the generated answers to the Sudoku puzzle keyed in earlier.


		Sudoku game showing generated answers


		The eye toolbar button acts as a toggle, to switch between two views, that of the puzzle entered in by the user, and the subsequent view of generated answers. This allows the user to switch back and forth at will, to discern hints from the answers as desired. In addition, one can highlight the answers in an alternate font color by pressing the two-toned rectangle icon on the toolbar. This view of highlighted answers is shown in the figure below.


		Sudoku game with answers highlighted


		One can print the current Sudoku game using the printer icon on the toolbar. The current view will be printed, so the question mark, answer and font color toggle settings will affect the printout. If one wishes to print the unsolved puzzle, it will need to be displayed first. If the answers are to be printed instead, then the answers must be on the screen prior to pressing the print button. From the "File" menu, one can also perform a print preview function.

		One can save the puzzle that was entered into the solver application by pressing the disk icon on the toolbar, or by selecting the "File" menu item and then select the "Save" submenu item. In addition, one can save off the answers in a separate file by selecting the "File" menu item and then select the "Save with Answers" submenu item.

		On the other hand, if you wish to play a brand new game, just press the new document icon on the toolbar, or select the "File" menu item and then select the "New" submenu item. As explained earlier, one can also begin a new game by pressing the open folder icon on the toolbar to open a different Sudoku data document (as described above).


Blank Grid		On occasion we get requests for blank Sudoku sheets or blank Sudoku grids. Our Sudoku Solver is quite capable of doing that, just by opening the program and de-selecting the "Question Marks" item in the View Menu, or toggling the question mark in the toolbar. In addition, a blank user name and blank source can be inserted by selecting both options in the View Menu and entering a single space character. If you perform or these steps, you should get a blank Sudoku grid just like the one in this image. Or you can just copy this image onto your system and print it as many times as you wish.



Background		Rules

		For those not aware of what Sudoku is, it is a logic puzzle based upon a square grid that is of a size (nn) by (nn), where n is an integer. The grid is sub-divided into square groups of size nn (we call them cubes, even though they are technically squares). Most people will have seen the version of n=3, which produces a 99 grid, consisting of 3 rows by 3 columns of 33 squares. A puzzle is generated that will have only a portion of the grid filled in with integer values from 1 to nn, which in the popular case of n=3, would be the range of digits from 1 to 9. The idea here is to solve a puzzle such that every row, column and cube has no duplicate values.


		Business Background

		We did not write this solver application just to have fun. It also serves as an example of applied Operations Research (OR), something we specialize at the Artige Company. A Sudoku puzzle is an instance of a warehousing problem, which is why we will use Operations Research (OR) technology to solve it. Say a cross-functional team sat together in a meeting (mostly marketing types, as they were the only ones unoccupied at the moment) to discuss the need to insure that a wide range of products, say nine in number, were available for quick delivery to customers covering a broad geographical area. Say also that this firm has nine warehouses at their disposal. So the brilliant cross-functional team resolves that at least one of each of these nine products or Stock Keeping Units (SKUs) is stored and kept on hand in each of the nine warehouses.

		Now some background on these warehouses: just so happens that they are the exact same size. So the cross-functional team concludes that in order for every warehouse to store at least one unit of each product, but allow for variable quantities to be ready for delivery, then every warehouse must be allocated a varying number of units of these products, otherwise they will not be able to hold the proper quantity of SKUs. Note that one cannot break down an SKU, so when this problem is solved, it must be done using integer values and not using real numbers (also known as floating point or decimal values).

		So say you have the nine warehouses and they need to keep nine products or SKUs on hand. The rule for storage is that one warehouse must keep one of the products, another warehouse must keep two units of the product, another warehouse must keep three units of the product, and so on. This follows for all nine products. Another rule is that if a warehouse is keeping one unit of an product, then it must keep not keep just one unit of any of the other products. This rule also follows for all of the other quantities. This may sound strange, but for example, one could consider a case where all of the products were of the same size, and the warehouses are all the same size. This means the warehouses can store 45 units of products. If the warehouses are supposed stock all of the products, and the quantities will be different for of that product in each warehouse, it will follow that the quantities for the remaining products in any given warehouse will need to be just as variable. So one ends up with a nine by nine grid or matrix of warehouse to product quantity mapping, that is identical to the Sudoku puzzle grid. Mind you, we have seen much more complicated warehousing rules in our consultancy.


The Math		Linear algebra is insufficient for Sudoku

		So how does one approach the solution to a warehousing problem? Well, we will not be able to rely on linear algebra. A nine by nine grid presents us with 81 unknowns to solve for, which will require 81 unique equations. The first thought to the person considering the application of linear algebra might be that through symmetry, one will only need 27 revealed values in order to solve the problem. In case you were wondering, we have come across valid Sudoku puzzles having a unique solution, and only 22 values were provided. So one will need some more help to use linear algebra.

		On top of that, for the 9*9 Sudoku puzzle, we only have three sets of nine equations, where nine variables in a row, column or cube will sum up to 45. Just so happens that these 27 equations are sparse, and will collapse down to three unique equations. One can obtain another 27 equations through the concept of triples. Just so happens that mirrored triples in this puzzle will have identical values. Problem here is that these 27 equations of six variables will also collapse down to three unique equations. So one will only have a total of six unique equations to solve for 81 variables. This problem set does not lend itself to being solved using linear algebra.


		Operations Research to the Rescue

		The big hint that a management science approach to solving the Sudoku puzzle would be a good idea is the large set of constraints that are given to us that cannot be used to create linear algebra equations. This would include the constraints of one digit per row, column or cube, and that cells in any given row, column or cube must not be equal to any other digit in that row, column or cube. Simultaneous equations cannot use such information to eliminate variables.

		Note that we modeled the Sudoku puzzle as a warehousing problem. That is because we intend to use heuristic warehousing algorithms to solve the problem. We call this methodology the warehouse method, but others will recognize the term transportation simplex method as the quintessential method for solving network problems.

		What the reader will need to keep in mind about a Sudoku puzzle is that each instance has a single solution. Warehousing problems normally have ranges of solutions, although on occasion they will have single solution. Because of this need to find an exact solution for Sudoku, we have had to insert additional algorithms that are not normally associated with warehousing problems. These algorithms establish certain what-if scenarios into automated routines. In the program we call these algorithms coin-flipping routines, but they are not randomizers. Rather, at times we can narrow down the possible digits that can occupy a cell into two values. So we run through two scenarios to see which one will work. In other words, a what-if scenario. Now that we mention it, we do not use any random number generators in the Sudoku Solver application. The logic is all driven by OR algorithms.

		OR heuristic algorithms require that a problem be setup as a table, typically taking the variable parameters and laying them out in equally as rows and columns, resulting in a square table. This provides one with a table of cells containing pairs of variables that can be acted upon individually. In some instances, one will need to see if data is present or not. This is the behavior that a Sudoku puzzle will require. Other instances one can perform mathematical operations between the pairs of variables. The results can be mapped as a path through the table, showing the least or greatest values to consider. The traveling salesman routine takes this approach.

		So, instead of summing the rows, columns and cubes to 45 (which is obvious for linear algebra but lacking in information), we will focus on the digits themselves, and the lack thereof. What we will do is in turn cycle through each row, column and cube, seeking to find out what we have been given and then fill in the missing digits through a process of deduction. Since we know what digits we can have in a cell, and the sets for a row, column or cube, we can determine what digits we have and which are missing, and what the candidate digits are for any given location in the Sudoku playing grid.

		The Sudoku Solver application will cycle through a Sudoku grid by row, column and cube. For each run, it will collect the digits that have not been used in every row/column/cube. We call these collections working sets. Then for each location within the row/column/cube we determine what the possible candidates are, looking at the perpendicular direction. If we find that any one location has been whittled down to a single candidate digit left, we fill that digit in, and strike it from the working sets.

		This resolution process is repeated in all three directions until we locate the digit for every location. This provides us with the solution for the puzzle. Otherwise, if we cycle through three directions for three times without resolving a location, then we consider the puzzle unsolvable. Before we give up though, we resort to coin flipping routines, as there are instances where we will have two digits for a single location in the grid. We keep snapshots of the solution in progress when we resort to the coin-flipping routines. So far, we have been able to solve in short order all Sudoku puzzles using this methodology.


		Technical Background

		The Sudoku Solver (SSolver) application was written for a wide audience, which required that the platform be one in widespread use. This would point to either a web application or a Windows desktop application. With the graphical requirements, we leaned towards writing the first version of SSolver as a Windows desktop application. It also helped that we have a few heavy GUI client side VC++/MFC applications that we could draw upon for a framework to write SSolver against. So this is the reason why SSolver appears first as a Windows application. We are holding onto the option to migrate the game to other platforms, such as Linux or Java.

		The SSolver application was written using Visual Studio. It uses the MFC single document interface (SDI) architecture, and would qualify as a MVC (model-view-controller) application. There was no need to have multiple games run simultaneously, so the MDI architecture was skipped this time around. This program is written as a straight "C++" program, and currently does not use any web technology, not even XML. We might consider writing an XML vocabulary in the future to store off Sudoku games. In the meantime we will stick to a text file format for serializing the games. Main point though, is that the SSolver source code is almost identical between Visual Studio 6 and Visual Studio 7 (2003 .Net) versions. We have provided the source code for both versions below.

		This application has many of the same requirements that our Ziffern math puzzle had, such as an SDI document methodology and game playing area, the need to enter digits into specific spots on the playing area using a custom control, and the ability to process large number sets. So we took the Ziffern application and modified it to display Sudoku puzzles and seek out answers for them.

		Most of the effort was placed on locating solution sets for the Sudoku puzzles. As we stated above, we have heuristic algorithms at our disposal that will run through tables of data and process them using warehousing problem or traveling salesman routines, to locate the sets of (pick one) fastest, cheapest, shortest, fewest items, routes or hours. When working with business problems, one likes to see multiple answers and do what-if scenarios with them (business people do not like to be locked into single solutions). What was really different about working out solutions to a Sudoku puzzle was the fact that there was only one solution to be found.

		So we had to come up with algorithms that resulted in the one and only solution. Using heuristics is not trivial. What you end up doing is generating the solution sets as normal, and then automating the execution of parsing through the what-if scenarios until the one and only solution is located. What we ended up doing was writing what we called "coin-flipping" routines, which would see what would happen when we tried out both answers to a scenario that had two solutions. Unfortunately, one coin flipping routine was not sufficient, so we ended up nesting three levels of coin flipping routines.

		At this point we feel with the algorithms delivered in SSolver that we can solve any valid Sudoku puzzle that has a single solution. It may be possible that there is a puzzle that we are unable to solve. Feel free to send us such a puzzle if you come across one. Please make sure it is a truly a valid Sudoku puzzle that has a single solution before submitting it to us. A note about using the SSolver program. If you enter an invalid dataset, the program may end up in an infinite loop. There is a cancel button, so please use it to stop the program when it runs for a lengthy amount of time. So far we have found that all solutions are found within 5 seconds, if not in less than one second.

		As this is a beta program, so there may be a few quirks in its operation. The selector wheel bitmap could use some prettying-up, the status bar needs some attention, plus the help file is not present.



Release Schedule		Trial Version 0.6.0 (Beta 1) SSolver Release [latest release]

		This version is now complete and can be collected below.

		It is intended that this program will be posted to SourceForge, assuming that they will have us there.

		Expected to be addressed in the SSolver Version 0.7 (Beta 2) Release:

		1- Memory leak check

		2- Separate thread for splash screen

		3- Add help files

		Expected to be addressed in the SSolver Version 0.8 (Beta 3) Release:

		4- Improve number wheel digit entry (remove OK/Cancel buttons)

		5- Have answer screen come up automatically if solution set was successfully generated

		6- Allow user to select font colors

		7- Provide for printing of games with and without answers on the same page

		Possible enhancements after first version release:

		8- Generate new Sudoku games

		9- Provide game sizes of n=2 and n=4

		10- Improve the graphics



Downloads		Prerequisites:

		1- Windows* operating system (Windows XP, Windows 2000, Windows 98)

			We are providing two installation files for SSlover. One version will only run on Windows* 2000 or Windows* XP. The second installation file will run on Windows* 98, plus Windows* 2000 and Windows* XP. If you are going to run the game on the newer Windows* OS, please select the Windows* 2000 version. The Windows* 98 version runs a bit slower, as we had to use a GDI MaskBlt replacement function that is not available on Windows* 98.

			Note: it is always good practice to uninstall a previous version of the SSolver program using the Windows* control panel "Add/Remove Programs" applet before installing a newer version!

			Really Important Note: Our apologies to those who had tried to install without being logged on as an administrator. We forgot to mention that you MUST be logged on as the administrator, or an account with administrative privileges. The installation will fail should you install with privileges less than administrator!

		Version 0.6.0 Program - W2K Latest	This zip file contains an installation file set to install SSolver on a Windows* 2000 or Windows* XP workstation. Just save the zip file to a directory and unzip it. Then run setup.exe, and answer the instructions as you would any other installation program. Pretty much no options, other than where to install the executable.
		Version 0.6.0 Program - W98 Latest	This zip file contains an installation file set to install SSolver on a Windows* 98 workstation. Just save the zip file to a directory and unzip it. Then run setup.exe, and answer the instructions as you would any other installation program. Pretty much no options, other than where to install the executable.
		Version 0.6.0 Source - VS7 Latest	This zip file contains the Visual Studio 2003 .Net (version 7) project that was used to create the SSolver application, which provides the XML-based project files. It includes only the main project source folder, the "res" resource folder and the "hlp" help folders, along with all of their contents. It does not include any of the generated debug or release folders, nor the precompiled headers. We will let you generate those yourself.
		Version 0.6.0 Source - VS6 Latest	This zip file contains the Visual Studio 6 project that was used to create the SSolver application. It includes only the main project source folder, the "res" resource folder and the "hlp" help folders, along with all of their contents. It does not include any of the generated debug or release folders, nor the very large precompiled headers. We will let you generate those yourself.
		Sample data files	This zip file contains some data files saved during testing of the SSolver applications. This way you can see what the exact format for the Sudoku data files should look like.


		* - Windows is a trademark of the Microsoft Corporation.




		Return to open source page	Navigate to home page

Legal

Last updated:
8-February-2006 00:50z