Jesper Niedermann's .NET Blog
about .NET and related technologies RSS 2.0
# Monday, 03 August 2009

I must admit that I have never understood why it was fun to solve Sudoku's. But as a programmer I was fascinated with the idea of making the perfect Sudoku puzzle generator algorithm from the very first time I heard of Sudoku. Of course I wanted to make it so general that it could not only make the boring old 9x9 sudoku. But sodukus of any size 4x4, 9x9, 16x16, 25x25 and so on...

This resulted in a .NET 1.1 WinForms program 4-5 years ago in which I could randomly generate all sudoku combinations from 4x4 to 36x36. I created an algorithm that started in the upper left corner and put in a random number then moving to the next square put in a new random number from the remaining numbers. This meant that the algorithm had to backtrack when coming to a deadend where no number was valid. This approach guaranteed that all possible Sudokus could be generated, but it was extremely slow. Well for 9x9 sudokus it was less than a second but for 36x36 sudokus it was around 16 hours :O)

A few weeks ago I thought it was time to try out Silverlight and make a small program to test Microsofts "new" programming platform, but I had to come up with an idea for a small program. And for some reason Sudoku popped up again.

And I came up with a novel idea for an extremely fast generator (try it here). It has been said that no ideas are new anymore and I am pretty sure that I am not the first to think of this since the algorithm is pretty obvious. I start with a valid Sudoku as a template and then apply transformations of the columns, the rows and the numbers themselves.

To generate a valid Sudoku I first generate the template. The template is generated by starting with 1 in the upper left corner and then counting upwards. Next I go to the 4th row and start in the second column counting from 1 again like this:

s1

Next I go to the 7th row and the 3rd columm and so on. So I add 3 rows (the square root of 9) each time. In a 16x16 sudoku I add 4 rows each time. The final template is generated in a few milliseconds even in a 400x400 Sudoku. The final template for a 9x9 sudoku looks like this:

s2

The template is itself a valid Sudoku.

Now I make the transformation using an observation I have made. In any valid Sudoku I can make another valid Sudoku by switching the columns within each block of 3 columns. As indicated in red colour for the first block above.

Secondly I can do the same for the rows.

And last I can transform the numbers themselves so that all 1's are transformed to a number from 1 to 9. all 2's are transformed to one of the remaining 8 numbers and so on.

I could also have applied a 4th transformation  that switched the big blocks as columns and rows, but I don't think that it will add much value.

In all this the entire puzzle can be generated in milliseconds for even extremely big Sudokus.

Try it out yourself at http://www.niedermann.dk/Sudoku/Sudoku.aspx

A few calculations

Now for some thoughts on completeness.

A 4x4 Sudoku has 4x3x2x3x2x2 = 288 possible combinations. Not counting combinations for empty tiles. In my original algorithm I was sure I covered all these combinations.

When using my new algorithm I can generate 2x2x2x2x4x3x2 = 384 possible transformations for a 4x4 Sudoku. This is more than the number of possible Sudokus. Which means that some of these transformations must result in the same Sudokus. And furthermore I do not know if there are Sudokus not covered by the transformations.

In a 9x9 Sudoku there are 1,83493E+21 possible Sudokus and I can generate 264.539.520 of those or 2.380.855.680 if I had used the extra big block transformations. Not complete at all, but on the other hand a very large amount of Sudokus and at lightning speed.

Empty tiles

A Sudoku isn't really a Sudoku without the empty tiles left for the person to fill out.

I just generate the empty tiles by choosing them at random. This method could probably lead to either very boring Sudokus or Sudokus that are impossible to solve. One day I might device some clever algorithm for emptying tiles in a more interesting fashion :O)

Silverlight

My conlusions on this my very first silverlight project is that it is extremely easy to make something appealing in silverlight. On the other hand there are som downsides. It is difficult to communicate between different silverlight hosts. I can only pass strings. When you hit the print button I open another browser window. And I actually have to serialize the Sudoku Grid and deserialize it again in the print window.

Another downside is that is not really browser agnostic. I have tried with 3 browsers IE8, IE7 and Firefox 3.5. Right now the only one working properly is IE8. In IE7 the new browser I open for printing has no menu, and so you cannot really print :O) In Firefox the silverlighthost cannot be resized, which is apparently a known issue. But it is a problem in the Sudoku generator because I offer Sudokus of any size. This means that in Firefox only 4x4 and 9x9 Sudokus will look good.

BTW: The rendering of a very large Sudoku takes some time of course even though the generation is over in milliseconds.

For my next silverlight project I think I will try out Prism and also the Out-of-browser experience.

Monday, 03 August 2009 22:16:48 (GMT Daylight Time, UTC+01:00)  #    Comments [5] -
Games & Puzzles
# Wednesday, 15 July 2009

Just released version 1.2 of SolZip my convenient tool for Zipping Visual Studio 2008 solutions

The major is a single install for SolZipMME, so you won't have to install ManagedMenuExtensions beforehand.

The release notes are here:

  1. Bug Fix: when multiple projects where referering to the same file it was added to the archive multiple times.
  2. SolZipMME uses SaveFileDialog instead of FolderBrowserDialog for Zip files.
  3. A single file installer for SolZipMME.
  4. Clipboard functionality now works on Vista / Windows Server 2008.
  5. SolZipGuidance changed. The menu will no longer appear on projects that are not C# projects. SolZipMME not changed.
  6. Support for $(SolutionDir) and $(ProjectDir) placeholders added
  7. Now works on Windows Vista even if UAC is not turned off

Enjoy...

Wednesday, 15 July 2009 16:05:27 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
Tools | Visual Studio
# Monday, 29 June 2009

I just released version 1.1 of SolZip which can be downloaded from the download page at the SolZip site.

The new action packed version contains one major improvement, one bug fix, and a few name changes:

  1. Now Source Control bindings for TFS and SCC can be removed from sln and csproj files. The default for all 3 UI's is that the bindings are removed, but you can optionally choose not to remove them. Feel free to contact me if you need bindings from other source control vendors removed.
  2. A bug fixed that made WinZip clients give a warning when unzipping certain archives made by SolZip. The warning was given when there was .. (2 dots) in a path in one of the zipped files.
  3. The Name SunZip.exe for the commandline tool was changed to SolZip.exe. Because SunZip sounded too much like UnZip.
  4. The Name SolutionZipper changed to SolZip everywhere. Except for SolutionZipper.dll which has been changed to SolZipBasis.dll

In the next version I will try to include ManagedMenuExtensions in the install so you won't have to run more than one setup to install SolZipMME.

Enjoy the new version :O)

Monday, 29 June 2009 20:44:48 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
Tools | Visual Studio
# Thursday, 18 June 2009

Here is my take on the Best practice Dispose pattern for most situations. It is heavily influenced by Juval Löwy from IDesigns book "Programming .NET Components", and some other sources which I no longer remember, since I made it a few years ago and have stuck to it ever since. Here it is:

public class Class1 : IDisposable
{
private bool m_IsDisposed;

~Class1()
{
Dispose(false);
}


[MethodImpl(MethodImplOptions.Synchronized)]
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}

private void Dispose(bool isDisposing)
{
if (m_IsDisposed)
return;

if (isDisposing)
{
FreeManagedRessources();
}
FreeUnmanagedRessources();
m_IsDisposed = true;
}

protected virtual void FreeManagedRessources()
{
//Free managed ressources here. Typically by calling Dispose on them
}

protected virtual void FreeUnmanagedRessources()
{
//Free unmanaged ressources here.
}
}

Another thing is that you can inherit the class and override the FreeManagedRessources and FreeUnmanagedRessources as needed.

Thursday, 18 June 2009 21:38:51 (GMT Daylight Time, UTC+01:00)  #    Comments [6] -
.NET
# Monday, 15 June 2009

I just released a new codeplex project SolutionZipper which makes it a breeze to zip compress your visual studio solutions and projects. "What's wrong with WinZip you might Ask". Well WinZip has no knowledge of Visual Studio Solutions, which means it will compress everything in the folder, including bin / obj folders and other random debris.

I accomplish the compression by using the following algorithm:

1. Iterate over all items and projects in the sln file and zip each of these.
2. Zip the sln file itself.
3. Iterate over all items in the csproj files and zip each of these. The iteration is done using Linq to Xml of course.
4. Zip the csproj file itself.

As you might have guessed SolutionZipper only works for C# projects, and is only tested with VS2008.

I offer three UI's for SolutionZipper

SunZip - A commandline tool.

 

SolZipMME - Providing Right click menus for Visual Studio 2008 using Managed Menu Extensions .

 

SolZipGuidance - Providing Right click menus for Visual Studio 2008 using Guidance Automation (GAX).

 

For the actual zipping I use the excellent open source framework SharpZipLib.

Monday, 15 June 2009 22:46:31 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
Tools | Visual Studio
# Sunday, 14 June 2009

I was using my codeplex project ManagedMenuExtensions recently when I realized that it threw an Exception, when clicking on a menu attached to a C# project under a solution folder. The reason was that the object which normally contained an EnvDTE.Project when a project was clicked contained null, when this project was contained in a solution folder.

I normally use this code to get at the selected project (m_VSStudio is the DTE object of the current solution):

private UIHierarchyItem SelectedItem
{
get
{
UIHierarchy uiHierarchy = m_VSStudio.ToolWindows.SolutionExplorer;
if(uiHierarchy == null)
return null;

object[] items = uiHierarchy.SelectedItems as object[];
if(items == null || items.Length == 0)
return null;

return items[0] as UIHierarchyItem;
}
}

The SelectedItem.Object of type object now contains a EnvDTE.Solution object if the solution is selected in the solution explorer, and guess what :O) it contains an EnvDTE.Project if a project is selected. It is this SelectedItem.Object that contains null, if the project is contained in a solution folder.

I googled this problem and found others who had the same problem, but none with a solution, so I had to come up with my own. I don't know if this behaviour is by design from Microsoft, or if it is a bug.

My Solution

Normally I would test if a project is selected with this code:

var project = SelectedItem.Object as Project;
if (project != null)
{
//Do something with the project
}

Now I use this code instead:

Project project = GetProject(SelectedItem.Object);
if (project != null)
{
//Do something with the project
}

Where I implemented GetProject(...) as:

private Project GetProject(object selectedItemObject)
{
var project = selectedItemObject as Project;
if (project != null)
return project;

var item = selectedItemObject as ProjectItem;
if (item == null)
return null;

return item.SubProject;
}

Not exactly beautiful, but that is to be expected when playing with Visual Studios AddIn model, and the kind of thing I try to hide in ManagedMenuExtensions. I haven't had a chance to look at Visual Studio 2010 yet, one could hope that they have done a better job of hiding the ugly underlying COM stuff.

 

Anyway, I hope this helps the next person who tries to search for a workaround for this rather weird behaviour.

Sunday, 14 June 2009 18:33:04 (GMT Daylight Time, UTC+01:00)  #    Comments [3] -
.NET | Tips & Tricks | Visual Studio
# Wednesday, 06 May 2009

My favourite RSS reader is GreatNews. First of all it is a standalone application, and secondly it is portable, which means I can install it on a USB key or better yet in my Dropbox which is what I do.

Well to be fair it is not portable in the purist way because it caches some stuff on the computers harddrive, but that is only for performance, so functionally GreatNews IS portable.

And GreatNews is very fast, which is just one more reason to love it.

In fact it has only one drawback, the database tends to get corrupt every 2-3 months, and there is no obvious way to repair it. I guess it will be corrected at some point in time (?) but for now it nearly made me give up on this otherwise great product.

After some googling I found that GreatNews uses an sqlite database called newsfeed.db. I couldn't really find a repair tool for it, even though I found a page which lots of tools for sqlite.

So I had to repair it in a more indirect way.

I downloaded one called sqliteman and with this I was able to make a new database called newsfeed.db and export all content from the old database and import it to the new one.

One nice sideeffect was that the database was only 1/10 in size after the import. Apparently either GreatNews or Sqllite tends to bloat the database.

After the import I replaced the old database with the new one (you should make a backup of course !), and viola it worked perfectly. So once more I am a happy user of GreatNews :O).

I cannot guarantee that this method will work for you too, perhaps I was just lucky. I advice you to keep your backup of the old newsfeed.db just in case.

P.S: To export the database you just choose "Dump database..." as shown below in a screenshot from sqliteman, which generates an SQL script that can be opened and run in the new database:

newsfeed1

Wednesday, 06 May 2009 21:34:53 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
Tips & Tricks | Tools
# Friday, 01 May 2009

If you want to Execute something on each element of the result of a Linq expression. You can either loop over the result using foreach(...) or turn the result into a List using .ToList(), and then use .Foreach(...) on the resulting list. Like this:

(from excep in ErrorList
where excep is ArgumentException select excep)
.ToList().ForEach(e => Console.WriteLine(e.Message));

This is ugly, and I prefer to make my own Extension method for IEnumerable<T> called Execute(...):

public static void Execute<T>(this IEnumerable<T> list, Action<T> action)
{
foreach(T element in list)
{
action(element);
}
}

This means you can do this instead:

(from excep in ErrorList
where excep is ArgumentException select excep)
.Execute(e => Console.WriteLine(e.Message));

Back in the days when I used Linq in a program for the first time, I wondered why there was no way to execute an action on each element of a list, so I implemented the Execute method.

It was only later that I discovered that the default way was .ToList().Foreach(...)

I must say I still prefer my original approach.

BTW: In a small none scientific test I have tested the two approaches.

With Linq To Objects iterating over 100000 integers and printing them to the Console takes about 21 seconds with the Foreach method and about 20 seconds with the Execute method, so it is even faster at least for this particular example. Though nothing to get excited about. :O)

The test was done in a Vista VPC with VS2008,

Small performance test: LinqPerfTest.zip

Friday, 01 May 2009 21:12:40 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
.NET | Linq | Tips & Tricks
# Tuesday, 14 April 2009

This site uses Google Adsense. And Google has informed me that I have to update my privacy policy, because they have started to use the DoubleClick DART cookie. I didn't really have one till now. But here it is containing all the legal mumbo jumbo that Google requires:

This site uses Google adsense to serve ads when you visit www.niedermann.dk. Google may use information (not including your name, address, email address, or telephone number) about your visits to this and other websites in order to provide advertisements about goods and services of interest to you. If you would like more information about this practice and to know your choices about not having this information used by Google, click here.

Tuesday, 14 April 2009 10:46:22 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -

# Tuesday, 07 April 2009

I recently was in a company where I created the coding standard. Mostly by referring to the great standard from IDesign but with a twist of company specific things. When C#3.0 came out I couldn't find any coding standard material on the new stuff out there on the web. So I was forced to think...

My thoughts on the var keyword, is that it should be used extensively. But I place a restriction on it. You should only use it if the type of the object is explicitly readable from the line.

So this is allowed:

var person = new Person();

And this is not allowed:

var person = PersonFactory.Create();

And similar for a Linq expression.

Allowed (actually it is required because of the anonymous type):

var person = 
from c in Customers
select new { c.FirstName, c.LastName };

Not allowed:

var person = 
from c in Customers
select Person.Create(c.FirstName, c.LastName);

Otherwise I place no restriction on the use. This way you get maximum readability without comprising that you should always know the type of what you are dealing with. Even when not using intellisense.

At the meeting I mentioned in "The Missing Linq" I asked Anders Hejlsberg why var is not possible on member variables in C#. He told me that they are looking into parallelizing the compiler. And it would be impossible to infer the type across assemblies compiled by different threads of the compiler.

Tuesday, 07 April 2009 09:01:55 (GMT Daylight Time, UTC+01:00)  #    Comments [0] -
.NET
Archive
<2009 August>
SunMonTueWedThuFriSat
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345
About the author/Disclaimer
I am a software architect with focus on Microsoft Technologies. I have been working with these in different large companies since 1995. I am currently employed at UVdata A/S.
Here is my View Jesper Niedermann's profile on LinkedIn

Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

Privacy policy
The privacy policy of this site.

© Copyright 2017
Jesper Niedermann
Sign In
Statistics
Total Posts: 28
This Year: 0
This Month: 0
This Week: 0
Comments: 32
All Content © 2017, Jesper Niedermann
DasBlog theme 'Niedermann' created by Jesper Niedermann, based on 'Business' created by Christoph De Baene (delarou)