11,636,985 members (68,411 online)

# Sudoku Solver with LINQ (C# 3.0)

, 7 Jul 2006 CPOL 65.3K 1.8K 56
 Rate this:
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.

## 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:

```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:

```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.

## Share

Derek Liang is a senior technologist working in Vancouver, BC. He likes mind games very much and used to play Chinese Chess, Go, etc. Now he falls in love with chess. In his spare time, he likes to listen to classical music and play some computer games. Of course, he enjoys playing with his 8 year old son.

Here is his blog.

## You may also be interested in...

 First Prev Next
 Next step Bojan Banko28-Feb-12 10:44 Bojan Banko 28-Feb-12 10:44
 My vote of 5 thatraja2-Sep-10 4:10 thatraja 2-Sep-10 4:10
 Well done Derek Marcelo Ricardo de Oliveira5-Dec-09 4:00 Marcelo Ricardo de Oliveira 5-Dec-09 4:00
 Brute force Pierre Leclercq17-Jan-07 21:48 Pierre Leclercq 17-Jan-07 21:48
 Re: Brute force Richard Birkby5-Jun-08 10:31 Richard Birkby 5-Jun-08 10:31
 bad source MP3Observer13-Nov-06 12:02 MP3Observer 13-Nov-06 12:02
 Re: bad source derekliang14-Dec-06 11:48 derekliang 14-Dec-06 11:48
 Re: bad source ledtech39-Sep-12 3:38 ledtech3 9-Sep-12 3:38
 Re: bad source derekliang7-Nov-12 20:28 derekliang 7-Nov-12 20:28
 Re: bad source ledtech37-Nov-12 20:35 ledtech3 7-Nov-12 20:35
 Chinese Chess justin10810-Jul-06 3:10 justin108 10-Jul-06 3:10
 Last Visit: 31-Dec-99 18:00     Last Update: 30-Jul-15 4:39 Refresh 1