Sudoku Solver with LINQ (C# 3.0)

• Download source code - 299.6 KB

Introduction

In this article, I am presenting a solution for solving and creating Sudoku puzzles with LINQ which is Microsoft's latest enhancement to the C# language.

What is LINQ?

The LINQ project is a code name for a set of language extensions to the .NET Framework 2.0 that encompass language-integrated query, set, and transformation operations. The extensions enable the construction of expressive and powerful expressions in SQL-like syntax. In fact, Dlinq which is a component of the LINQ project, provides direct translation between SQL and LINQ objects which makes programming database applications much easier. All LINQ programs are compiled into IL which can be run directly under .NET Framework. There is no interpreter required.

What is Sudoku?

Sudoku is number puzzle. The aim of the puzzle is to enter numerical digits from 1 to 9 in each cell of a 9x9 grid made up of 3x3 region (as marked grey). The puzzle starts with various digits in pre-determined cells as shown in left hand side of the following diagram. A solution of the puzzle must ensure that each 3x3 region, each row and each column, must contain all the numbers 1 to 9 as shown in the right hand side of the following diagram.

LINQ constructor

I will introduce some of the LINQ "query expression" used in this project in this section from the easiest to the more complex one. For complete reference, you can find it in C# Version 3.0 Specification (May 2006).

Query expression is a language integrated syntax for queries that is similar to relational and hierarchical query languages such as SQL and XQuery. A query expression begins with a from clause and ends with select or group clause. A query expression has 3 properties which are useful in programming.

1. A query expression can be used as a data source for other query expression to further refine data
2. An query expression is an object with IEnumerable<t /> interface therefore it can used in foreach statement
3. An query expression is can be converted to Array<t /> or List<t /> via the ToArray() or ToList() method

In the above points 2 and 3, type T is a compiler inferred and created anonymous type based on the select or group clause of the query expression. For example for the following code:

var smallNumbers = from n in numbers
                   where n<5
                   select ( new { number=n, powerOf2=n*n }) ;

LINQ compiler will generate an anonymous type which canNOT be referenced anywhere in your code. It is shown as the following:

class __anonymouse_class
{
     public int number;
     public int powerOf2;
}

Then the following statement will loop through all the numbers that are less then 5 as stated in the query expression.

foreach( var n in smallNumbers )
     Console.WriteLine(n.number + " " + n.powerOf2);

Internally the LINQ compiler translates query expression into invocations of methods that adhere to the query expression pattern. In our example, it will be translated into the following code:

smallNumbers = numbers.Where( n => n<5 ).Select( n => new 
                    { number=n, powerOf2=n*n });

n => n<5 is a Lambda expression. It can be written explicitly as (int n) => { return n<5; } which will be further translated into delegate type bool (int n) and anonymous method {return n<5;}.
For details, please reference the C# Version 3.0 Specification (May 2006).

Before we start, let us look at another new feature in the C# version 3.0 called "implicitly typed local variable declaration". When a local variable declaration specifies var as the type and no type name var is in scope, the declaration is an implicitly type local variable declaration and the actual type of the local variable being declared is inferred from the expression used to initialize the variable. For example:

var i = 0 ;         // same as: int i = 0 ;
var s = "abc" ;     // same as: string s = "abc" ;
var sb = new StringBuilder() ; 
                    // same as: StringBuilder sb = new StringBuilder();

Introduction to query expression

Sequence

Let us start with Sequence. Sequence.Range(1, 9) is a method call that returns a query expression which represents an array of number from 1 to 9.

var numbers = Sequence.Range(1, 9) ;
foreach( var n in numbers )
   Console.WriteLine(n);

Result:

select

select clause in the query expression specifies the type (or anonymous type) that will be returned. In the following case it is of type int.

var numbers = Sequence.Range(1, 9);
var SameNumbers = from n in numbers
                  select n;
foreach( var n in SameNumbers )
   Console.WriteLine(n);

Result:
(same as the above output)

where

where clause in a query expression specifying a filtering condition of the query expression.

var numbers = Sequence.Range(1, 9) ;
var smallNumbers = from n in numbers
                   where n<5
                   select n ;
foreach( var n in smallNumbers )
    Console.WriteLine(n);

Result:

Except

Except is a set operator which returns a query expression that has all the elements of a query expression but not in another query expression.

var numbers = Sequence.Range(1, 9) ;
var smallNumbers = Sequence.Range(1, 4) ;
var bigNumbers = numbers.Except(smallNumbers);
foreach( var n in bigNumbers )
    Console.WriteLine(n);

Result:

Fold

Fold is an aggregate operator which takes every elements in the query expression and does something about it. In our example, a temp variable r will be created and assigned to 0, and for each elements r = r + n will be evaluated. Result will be assigned to variable sum.

var numbers = Sequence.Range(1, 9) ;
var sum = numbers.Fold(0, (r, n) => r+n);
Console.WriteLine("The sum is: "+sum);

Result:

How the program works?

A puzzle is represented in a one dimensional array (int []). The value of each cell can be 1 to 9 or 0 if the cell is empty. One dimensional array was chosen for easy data manipulation/transformation using LINQ language constructors as it is easy to implement a 16x16 puzzle solver and generator without changing much of the code. A Sudoku puzzle is declared as the following code:

int [] sudokuPuzzle =
{
                   0, 7, 1, 0, 9, 0, 8, 0, 0,
                   0, 0, 0, 3, 0, 6, 0, 0, 0,
                   4, 9, 0, 0, 0, 0, 7, 0, 5,
                   0, 1, 0, 9, 0, 0, 0, 0, 0,
                   9, 0, 2, 0, 0, 0, 6, 0, 3,
                   0, 0, 0, 0, 0, 8, 0, 2, 0,
                   8, 0, 5, 0, 0, 0, 0, 7, 6,
                   0, 0, 0, 6, 0, 7, 0, 0, 0,
                   0, 0, 7, 0, 4, 0, 3, 5, 0
};

The main routine is solvePuzzle which takes a puzzle as the single input parameter. Other auxiliary input variables will be used to determined the size of the puzzle, termination condition, whether we try to solve the puzzle by trying numbers in random order. Output variables are the return value of the solvePuzzle, true if it finds a solution and false if it finds no solution. Also it will set a variable if more than 1 solution found. It is mainly for generation of puzzles.

I will recommend to turn on the debugging output if you are curious to see how the solver works. The code is quite self-explanatory.

For creating a Sudoku puzzle, the approach I took had 2 steps:

1. Create a puzzle solution by invoking the solver with empty cells. It will return the same solution every time. To randomize, the solver will re-order the number to try as shown in the following code:
   C#

   if (_isRondomized)
           arrayOfAllNumber =
                  from  n in arrayOfAllNumber
                  orderby _random.Next()
                  select n ;

2. Try to take out numbers in each cell of the puzzle solution and see if the Sudoku puzzle still has a unique solution. If it still does, make the cell empty. Otherwise do not do anything. We have to do the same here to randomize the order in which the numbers are being taken out of cells. As shown below:
   C#

   var arrayOfNumberToRemove =
                  from  n in Sequence.Range(0,  size*size-1)
                  orderby _random.Next()
                  select n ;

Points of Interest

LINQ language constructor provides a higher abstraction and enables programmers to spend more time on the actual algorithm and/or problem domain. Common operations on transform/mesh array of elements can never be easier with LINQ.

All the code in this article has been compiled and tested with Microsoft LINQ project May 2006 CTP.