( Index )

Brief Information about the April '11 CSIG Meeting

Sudoku Solver - A Program to Solve a Sudoku Puzzle        by B. Arnold

Puzzle Image

Welcome to the CSIG, a Special Interest Group of the ACGNJ. This is an exciting time for the C Language programming since Microsoft now has 4 different language compilers: C++, C++ Express, C-Sharp, and C-Sharp Express. These are all capable of creating Windows (tm) programs. (Some are FREE!)

New for this month will be significant programming enhancements to the last month's Suduko program. A DETERMINISTIC ALGORITHM using HINTS, SINGLETONS, and PAIRS has been added along with new C++ classes, printing routines, debugging techniques, and other features.  The program is a "work in progress" since everyone from this author through Donald Knuth has attempted a "concise" solution. Last month I presented the following application. In addition to normal .Net code, we will be addressing "MULTI-THREAD ISSUES" since the calculation loop of the program runs in the background.

Sudoku Solver 0.99 by B.Arnold 3/15/2011
Sudoku Solver 1.00 A multi-thread Background Worker has been added.

Object: To solve the given Sudoku Puzzle using the following rules.

Every row, column, and 3x3 box contains every digit from 1 to 9 inclusively. The program uses a Monte Carlo technique with a custom algorithm to solve the hard coded puzzle. The program iterates through thousands of trial solutions in order to find one that matches the rules of the game. This simplified approach allows explaining the program without discussing higher math.

There is a wealth of programming information on the Internet showing dozens of possible algorithms. Most of the more sophisticated ones use deterministic methods to improve the number of "hints" and leave "trial and error" for later stages of the solution.

From http://en.wikipedia.org/wiki/Sudoku
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

From Microsoft:
The BackgroundWorker class allows you to run an operation on a separate, dedicated thread. Time-consuming operations like downloads and database transactions can cause your user interface (UI) to seem as though it has stopped responding while they are running. When you want a responsive UI and you are faced with long delays associated with such operations, the BackgroundWorker class provides a convenient solution.

The program uses some of the most sophisticated Dot Net Library functions including the following:

Dialog Box Functions and Objects, Drawing, Pens, SystemBrushes, DrawLine, PictureBox, Threads, WorkerThreads, and others.

There are a number of ways to refer to Microsoft's latest compilers and code. Here's what Wikipedia says: The Common Language Infrastructure (CLI) is an open specification developed by Microsoft that describes the executable code and runtime environment that form the core of the Microsoft .NET Framework. The specification defines an environment that allows multiple high-level languages to be used on different computer platforms without being rewritten for specific architectures.

Microsoft .Net Framework 3.5
C++ 9.0, etc.
.Net 3.5, etc.
Common Language Infrastructure

Sample Code

// Rule Checker Procedure // private: int RulesOK(void) { int n[9]; // count of values flag result = flag::good; int data; // Check each row. (Only 1 of each digit.) // =============== for (int y=0; y<9 && result==flag::good; y++) { for (int i=0; i<9; i++) n[i] = 0; // zero counters. for (int x=0; x<9; x++) { data = *value[x,y]; if (data > 0) { ++n[data-1]; // indexes go from 0 .. 8 if (n[data-1] > 1) // woops: found 2 or more of a number. { result = flag::bad; y=9; break; } } } } // Check each column. ( Like above but move vertically. ) // ================== for (int x=0; x<9 && result==flag::good; x++) { for (int i=0; i<9; i++) n[i] = 0; // zero counters. for (int y=0; y<9; y++) { data = *value[x,y]; if (data > 0) { ++n[data-1]; // indexes go from 0 .. 8 if (n[data-1] > 1) { result = flag::bad; x=9; break; } } } }


Source Code Files

For help, email me at b a r n o l d @ i e e e . o r g
Back to C++ Main Page