Click here to Skip to main content
Click here to Skip to main content

Sudoku Solver with LINQ (C# 3.0)

, 7 Jul 2006 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

Sample image

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:

Sample image

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:

Sample image

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:

Sample image

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:

Sample image

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

derekliang
Software Developer (Senior)
Canada Canada
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.

Comments and Discussions

 
SuggestionNext step PinmvpBojan Banko28-Feb-12 11:44 
GeneralMy vote of 5 Pinmemberthatraja2-Sep-10 5:10 
GeneralWell done Derek PinmemberMarcelo Ricardo de Oliveira5-Dec-09 5:00 
GeneralBrute force PinmemberPierre Leclercq17-Jan-07 22:48 
GeneralRe: Brute force PinmemberRichard Birkby5-Jun-08 11:31 
Generalbad source PinmemberMP3Observer13-Nov-06 13:02 
check the file!
no .cs sources, only pdb,dll!!Mad | :mad:
GeneralRe: bad source Pinmemberderekliang14-Dec-06 12:48 
GeneralRe: bad source Pinmemberledtech39-Sep-12 4:38 
GeneralRe: bad source Pinmemberderekliang7-Nov-12 21:28 
GeneralRe: bad source Pinmemberledtech37-Nov-12 21:35 
GeneralChinese Chess Pinmemberjustin10810-Jul-06 4:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.1411023.1 | Last Updated 7 Jul 2006
Article Copyright 2006 by derekliang
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid