Soo — Sudoku in C#

This is a simple open source implementation of a Sudoku solver, written in C# for v2.0 of Microsoft's .NET Framework. This language was chosen because it is readily available—the C# compiler is installed as part of the .NET Framework—and also because I was more interested in portability than performance. It also is my way of trying to repay all of the time, effort, and advice provided by the members of the Sudoku Programmer's Forum.

What Soo Will Do:

This version determines if an input string represents a valid puzzle, and will also ensure that it has a unique solution. It then tries the following strategies—in the order listed—to solve the puzzle:

• EASY Difficulty

• Naked Singles
• Hidden Singles

• NORMAL Difficulty

• Naked Pairs
• Box / Line Reduction (Pointing Pairs or Locked Candidates)

• HARD Difficulty

• Subsets (Pairs / Triplets / Quad / etc.)

• FIENDISH Difficulty

• Fish (Swordfish / Jellyfish / Squirmbag)
• Wings (X-Wing / XY-Wing / XYZ-Wing)
• Chaining
• Simple Coloring
• Unique Rectangles

Using these strategies, the ‘Soo’ solver will successfully solve about 30% of the Top 1465 puzzles, and will display the solution steps in human-readable form. With a little work, the Dancing Links (DLX) solver could be modified to solve 100% of the unique puzzles, but it wouldn't be able to provide any useful hints other than the answer.

What Soo Won't Do:

This software expects the user to have at least a rudimentary understanding of programming and/or the C# language. In other words, it's user-hostile, and hates everyone equally.

Installation & Usage

The source code includes several major classes:

• soo.cs: the Soo class which ties together the sub-classes and implements most of the actual solving logic.
• dlx.cs:   the DancingLinks class which implements an ‘Algorithm X’ exact cover solver used to check a puzzle for uniqueness.
• brute.cs:   the BruteForceSolver class which is a ‘Brute Force’ solver.
• grid.cs: the Grid class which keeps track of all of the squares and candidates (possible values) for each square.
• generator.cs: the Generator class which generates random puzzles.
• house.cs: the House class which keeps track of all of the squares within a single box, column, or row.
• square.cs: the Square class, which keeps track of a single square on the grid.
• utility.cs:  a collection of utility and helper classes, including application exceptions and the Bitset and Subset classes.

All of these source files—including a set of NUnit unit tests (*.test.cs) can be downloaded through the ‘Download’ link to the left.

Copy the indivual source files to a directory, then use the C# compiler distributed with the NET Framework to compile them. A simple batch file to compile everything might look like this:

@ECHO OFF
SET SRCNAME=Program.cs soo.cs dlx.cs generator.cs grid.cs house.cs square.cs utility.cs
SET EXENAME=soo.exe
CLS
IF EXIST %EXENAME% DEL %EXENAME%
C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\csc /nologo /o /t:exe /out:%EXENAME% %SRCNAME%

The source code is being released under version 2 of the GNU Public License and is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Latest Version

v0.00.0017 dated 05 Feb '07

• Added a primitive GUI;
• Added BruteForceSolver class;
• Optimized BitSet class to cache the bit count;

Change Log

v0.00.0016 dated 10 Jan '07

• Added Generator class;
• Refactored Soo.Display…() methods to the Grid class;
• Added FindNakedPairs() solving method to the House class;
• Added SetEmpty() method to the Grid class;
• Added logic to the Soo class to determine and report puzzle difficulty;

• v0.00.0015 dated 27 Dec '06

  • Fixed bug in “Simple Coloring” logic;
  • Added “Unique Rectangles” logic.

  v0.00.0014 / 17 Dec '06

  • Initial public release.

  System Requirements

  .NET Framework v2.0 or better