Sudoku Solver in C#

Another breakable toy, my variation of Sudoku solver. I’ve created it without previously googling the topic, and I was quite surprised when latter I realized that most solutions out there use just dumb trial and error. I was also glad that I can re-invent backtracking algorithm

Ok. let’s start, from having a Sudoku that we want to solve:

After a little consideration I decided to solve it by elimination of possible values. Let’s consider first block (by block I mean inner 3×3 cells squares), possible values for empty cells:

Cell \ Value	1	3	6	7	8	9
A1	x		x	x		x
A2		x	x	x		x
A3		x	x	x		x
B2		x	x	x
B3		x	x	x	x
C3		x	x		x

We can see that value 1 can be only in A1 cell so fill it in. Check remaining cells and no single value in a row or column. So we evaluate next block:

Cell \ Value	1	2	3	4	6
A5		x	x	x
B3		x	x	x	x
B4					x
B5	x	x	x	x
C3			x		x

Now value 1 and 6 are only possible in cells B5 and B4 so we fill them in. Check remaining cells after reduction – no single possible values – we go to the next block.

We cycle through all blocks until all cells are filled in (will happen only for very simple Sudoku) or number of empty cells is not changed after a cycle. In the second case, we filled what we could using simple elimination and it’s time for more advanced solving techniques or guessing. This time I choose guessing, maybe later I’ll implement something more original. So we take first empty cell pick its first possible value fill it in and use recursion and backtrack algorithm to check if we can complete the puzzle. If not go back pick next possible value and try again.

That’s it the whole working solution can be found on github. To test the solution I’ve used online solver at http://www.sudokuwiki.org/sudoku.htm . Beside of detail description of different techniques of solving Sudoku, it allows to import and export puzzle as string of numbers which is really helpful.

Next step for me is to implement the same algorithm using less familiar languages. I think of Python, Ruby, JavaScript and Dart, F# and maybe Haskell.

User defined rules and how to host IronPython in .NET application

Currently I’m working on a data processing slash financial application where user can define their own processing rules. Those rules are defined in specially created scripting language – sounds impressive, right? Well it’s really interesting piece of code especially for someone like me who never worked before on parsers, tokenizes and all other stuff that is needed to built a compiler/interpreter. But this is also a problem – writing custom language is not a core part of the business. In result language evolved in a direction that was picked as we saw fit at the given moment. That is why we have nice, lean syntactical Frankenstein monster that is working fine with one exception – it’s rather slow.

So conclusion from this situation – if something is not core part of a business and it’s pretty important – think twice before you go and build it. Most likely business won’t spare enough time/money/developers to do this right.

Realizing this we decided to retire our friendly Frankenstein baby and use Python instead.

Python is a dynamic programming language which is getting more traction in recent years. It is used by companies like Google, Yahoo and even NASA. In result of its growing popularity Microsoft decided to create Python implementation for .NET. The project is called IronPython and it was open-sourced not so long ago. Because it is built on .NET using Dynamic Runtime Extensions (DLR) it can be easily integrate with other managed applications.

To embed Python in .NET app it’s enough to reference following assemblies:

• Microsoft.Scripting.Metadata.dll
• Microsoft.Scripting.dll
• Microsoft.Dynamic.dll
• IronPython.Modules.dll
• IronPython.dll

And type two lines of code, like below, to execute you first script:

This is just simple evaluator – execution of something a bit more complicated let say mixing Python method and C# code, can be achieved like this:

After instantiation of necessary objects – ScriptingEngine, ScriptScope etc. about them in a moment, compile a Python method, obtain function delegate from ScriptScope and execute it.

There is four main classes that we need to work with IronPython or any language based on DLR for that matter:

• ScriptEngine – this is a DLR object that represents language semantics e.g. IronPython, IronRuby etc. It’s responsible for executing code.
• ScriptScope – essentially this class represents a namespace – it’s used for storing runtime variables. We can execute script in context of multiple ScriptScopes.
• ScriptSource – represents source code and offers a variety of ways to execute or compile the source.
• CompiledCode – represents compiled script – can improve performance in case we want to reuse it.

During integration of Python into the project one of the focuses was ability to reuse library of existing domain functions written in C# without burdening a user with knowledge about references, modules etc. How I choose to solve this problem was using ExpandoObject as a vessel for passing rule delegates into Python script. Let’s look at following example:

There are two important things here: first script defines function Add which sums two parameters a and b and third value that is obtained from C# function called GetValue(). GetValue in this example is as simple as it can gets:

Keyword RULE is global variable that we defined as ExpandoObject and passed to ScriptScope which is used to execute script. ExpandoObject holds delegates to functions we want to use in Python method.

It is possible to use dictionary or some other predefined object – instead Expando but first I think that syntax: variable.function(parameters) fit nicely with Python. Secondly we can add properties dynamically which in case of hundreds built in rules can come in handy. Just add some script analyzer and pass only delegates of required functions.

All above examples and some more can be found here.

Agatha and Request/Response pattern

Request/Response pattern is very simple pattern that can make our life easier when working with wcf services. The idea is to wrap all service operation parameters in one object that we call a request and return an object that we call a response. There is few advantages of such approach, the main ones (at least for me) are:

• You can inherit request and responses from base objects where you can put some common properties like user information, security token or error message.
• Simplifies versioning of a service
• Generated proxy is easier to read and understand

Simple right? Sure – that is why I was surprised when I’ve read about framework that was described as a ‘Request/Response Service Layer’. Why the strait forward pattern needs a framework? Is this one of those projects that were created just for sake of creating it? I was almost ready to close the page when I saw a little bit of code that I sub conscience liked:

One class one operation? Interesting I must admit most services which I was working with – looked like bunch different procedures putted in the same file – procedural, ugly hard to read and understand. Is this possibly a solution?

Please meet Agatha – she will make your life easier or not – depends your preferences. So what this framework is doing? – simply it’s request dispatcher. There is predefined contract with one operation:

All messages are send to this operation – and Agatha based on request object type is routing it to specific handler. Basic sample can be found here. So what we gain:

1. proper code separation for service operations – now we have handlers
2. we can publish only one service for all implemented handlers
3. no need to update client side proxy when service is changed
4. authentication, authorization, error logging – can be done just in one place
5. we can batch requests for traffic optimization – so ‘chatty’ services are not a problem anymore
6. framework handles client and server endpoints with minimal wcf configuration

So it is nice simple and easy – but only when both client and server are using Agatha. We can still consume service in other languages but it will be awkward – request types will indicate what operation we want to call. One more issue that was actually mentioned by one of my colleagues is lack of clearly defined interface which will make service even more difficult to use by 3rd party.

In summary interesting approach for handling services. Especially if you want to use them for internal clients that you can control. But I would think twice if I had to develop something for greater audience.

You can find Agatha on GitHub. Example application is described here, and here you can find series of post describing framework in more details.

Performance Counters i ich kategorie

Performance Counters to taki mechanizm Windows, dzięki któremu możemy oszacować wydajność naszej aplikacji (i nie tylko naszej). Świetnie się również sprawdzają, przy identyfikacji wszelkich problemów z wyciekami pamięci lub przy poszukiwaniu niezamkniętych połączeń do bazy danych. Pełną listę odstępnych ‘liczników’ podzielonych na kategorie można zobaczyć uruchamiając Performance Monitor umieszczony Control Panel -> Administrative Tools.

Wszystkie liczniki podzielone są na kategorie – i właśnie z tymi kategoriami miałem problem. Otóż przykładowo, aby stworzyć nową kategorię i dodać do niej nasze liczniki, wywołamy następującą metodą:

CounterCreationDataCollection counters = new CounterCreationDataCollection();

counters.Add(new CounterCreationData("Counter 1",
                                        "Counter 1 Description",
                                        PerformanceCounterType.NumberOfItems32));
counters.Add(new CounterCreationData("Counter 2",
                                        "Counter 2 Description",
                                        PerformanceCounterType.NumberOfItems32));

PerformanceCounterCategory.Create("Nowa Kategoria",
                                    "Nowe Kategoria Description",
                                    PerformanceCounterCategoryType.Unknown, counters);

Fajnie, a co jeśli teraz chcemy dodać nowy licznik do naszej kategorii? No cóż klops – nieco skostniałe API nam tego nie umożliwia, przynajmniej nie bezpośrednio. Otóż, co możemy zrobić to pobrać wszystkie istniejące liczniki, skasować kategorie i utworzyć ja ponownie wzbogacona o nowe liczniki. Przykładowo:

string categoryName = "Nowa Kategoria";

CounterCreationDataCollection counters = new CounterCreationDataCollection();

if (PerformanceCounterCategory.Exists(categoryName))
{
    PerformanceCounterCategory pcc = PerformanceCounterCategory.GetCategories()
                      .Where(c => c.CategoryName == categoryName).FirstOrDefault();

    if (pcc != null)
    {
        var existingCouters = pcc.GetCounters().
                        Select(c => new CounterCreationData()
        {
            CounterName = c.CounterName,
            CounterHelp = c.CounterHelp,
            CounterType = c.CounterType
        }).ToArray();

        counters.AddRange(existingCouters);
    }

    PerformanceCounterCategory.Delete(categoryName);
}

counters.Add(new CounterCreationData("Counter 3",
                                     "Counter 3 Description",
                                     PerformanceCounterType.NumberOfItems32));

PerformanceCounterCategory.Create(categoryName,
                                  categoryName + " Description",
                                  PerformanceCounterCategoryType.Unknown, counters);

Powinno grac i buczeć. Jedno, na co trzeba zwrócić uwagę to, ze możliwy jest mały poślizg z ‘publikacja’ nowego licznika przez Windows. Co może powodować problemy? Gdy instalujemy cos np. serwisy windowsowe z pliku batch – licznik z jednego serwisu jeszcze nie został opublikowany a drugi serwis juz pobiera ich listę, aby je zmodyfikować.

Więcej o Performance Counters można znaleźć tutaj.

OMG!! My knowledge is gone!!

Partial Methods

Codziennie można nauczyć się czegoś nowego. Dzisiaj odkryłem, że w .NET nie tylko klasy mogą być określane, jako partial, ale również metody. Wygląda to tak:

partial class Account
{
    private decimal _balance;

    public string Balance
    {
        get { return _balance; }
        set
        {
            OnBalanceChanging(value);
            _balance = value;
            OnBalanceChanged();
        }
    }

    partial void OnBalanceChanging(decimal balance);
    partial void OnBalanceChanged();
}

I klasa implementująca metody OnBalanceChanging i OnBalanceChanged:

partial class Account
{
    partial void OnBalanceChanging(decimal balance)
    {
        // do sth
    }

    partial void OnBalanceChanged()
    {
        // do sth
    }
}

Proste przejrzyste i przypominające eventy, prawda? Przykład wykorzystania można znaleźć np. w klasach generowanych przez Entity Framework 4.

Dokumentacja podaje zasady korzystania z partial methods (ciekawe jak by to przetłumaczyć metody cząstkowe, częściowe)?

· metoda musi być oznaczona słowem kluczowym partial i musi być private

· musi zwracać void

· metoda może mieć parametry oznaczone, jako ref, ale już nie, jako out (pewnie, dlatego, że niemożna zagwarantować, że zmienną oznaczoną, jako out zainicjujemy, co jest wymagane przy wykorzystaniu tego modyfikatora)

· metoda może być oznaczona, jako static bądź unsafe

Jeśli zdefiniujemy metodę partial, ale jej nie zaimplementujemy, kompilator po prostu usunie referencję do niej. Niestety, jeśli postąpimy na odwrót tj. będziemy mieli implementację a brak będzie jej definicji, kompilator zgłosi wyjątek.

Ceny na Amazonie

Od jakiegoś roku korzystam z Amazon Kindle DX – świetne urządzenie które polecam każdemu kto sporo czyta szczególnie w podróży. Jednak ceny jakie widzę na Amazonie po prostu mnie wkurzają:

Książka papierowa jest tańsza od elektronicznej? Jak to możliwe? Cały proces od ścięcia drzewa, zrobienia papieru, przygotowania farby, druku, magazynowania aż po wysyłkę do klienta – zawarty jest w cenie wersji papierowej – a ta jest niższa od wersji elektronicznej? Dobra tylko o 9c, ale zakładając, że połowa ceny wersji papierowej to koszty przygotowania i druku – to na elektronicznej przepłacamy 50%. Ile kosztuje przygotowanie wersji elektronicznej, tyle co nic, bo jak książka została złożona i przygotowana do druku – to konwersja do formatu prc, mobi etc. to jest jedno kliknięcie. Dla mnie to już tylko czysta pazerność …

Problem z localhost

Dostałem nową maszynę w pracy z świeżo wgranym image systemu. Zdążyłem sobie ją skonfigurować, zainstalowałem co trzeba, pobrałem kod z repozytorium – wszystko fajne się buduje, działa jak należy – do czasu … pierwszego restartu.

Po ponownym uruchomieniu – strona nad którą jeszcze chwilę wcześniej pracowałem odmawia współpracy wyświetlają błąd 404. Ok. pewnie coś ze ścieżkami nie tak, ale nie, wszystko jest tak jak być powinno. Strona nadal wyświetla 404 – dziwne, robię iisreset nadal nic.

Wszystko idealnie się składa – za chwilę mam spotkanie z analitykiem i potrzebuję działającej strony – awaryjnie włączam laptopa i nadal szukam problemu.

Próbuję załadować inną stronę – problem ten sam 404. Ok. to już coś z IIS’em – działa (bo wyświetla 404). Czytam stronę błędu nieco dokładniej i mamy Status Code 101 – ok. sprawdzamy w Google co to znaczy – http://support.microsoft.com/kb/943891

101 – Switching protocols.

Niewiele mi to mówi ale zaczynam- grzebać w konfiguracji IIS’a – i w sumie od razu, widzę problem:

Próba ponownego startu, zwróciła kolejny wyjątek:

IIS Manager Error: The process cannot access the file because it is being used by another process. (Exception from HRESULT: 0×80070020)

Jakiego pliku? Dalszych poszukiwaniach w Internecie – okazało się, że może tu chodzić nie tyle o plik co o port Teraz już było z górki – z linii komend, wystukałem:

netstat -ano

aby sprawdzić czy coś korzysta z portu 80 – Bingo! Przechodzę do Process Explorera i sprawdzam PID procesu korzystającego z mego portu i … okazuje się, że to Chrome OK. zamykamy przeglądarkę, restartujemy IIS’a i znowu wszystko gra!!

Wszystko było by pięknie, gdyby nie zmarnowana godzina i uczucie, że już kiedyś chyba walczyłem z podobnym problemem.

Maroko

Od dłuższego czasu milczałem na blogu, o przyczynach, próbuję napisać w przyszłości, teraz tylko krótka uwaga – złe środowisko pracy negatywnie wpływa na moją kreatywność czasem do tego stopnia, że tracę (oczywiście na jakiś czas) radość z tego czym się zajmuję. Dobra tyle o pracy, dzisiaj coś o Maroku z którego niedawno wróciłem.

Witaj Afryko

To była moja pierwsza wizyta w Afryce i nie bardzo wiedziałem czego się spodziewać. Wybór miejsca był nieco problematyczny z jednej strony chciałem poleżeć trochę na plaży i zakosztować błogiego lenistwa, z drugiej chciałem zobaczyć coś więcej niż ośrodek turystyczny. Agadir w Maroko całkowicie spełniło moje oczekiwania.

Bezpośredni lot z Dublina do Agadiru oferowany przez jet4you trwa około trzech i pół godziny. Klasa linii lotniczej powiedział bym ryanair’owska, co przy długości lotu i ilości miejsca na nogi – pozostawia nieco do życzenia. Na lotnisku przywitało nas zachód słońca (ok. 7 wieczorem) i sucha, ciepła bryza, przyjemna odmiana od wilgoci Dublina. Droga do hotelu zajęła nam jakieś pół-godziny, w zachodzącym słońcu, obserwowaliśmy przedsmak tego co nas czeka.

Agadir

Agadir to nadmorskie miasto w regionie Sous, które zostało praktycznie całkowicie odbudowane po trzęsieniu ziemi w 1960 roku. Zatrzymaliśmy się w bardzo przyjemnym hotelu Intouriste. Jeśli ktoś by się tam wybierał, to nie polecam tylko lodów w restauracji, i śniadań ok. godziny 7 rano (jeśli w ogóle takowe uda się dostać Hotel jest położony nieco na uboczu, ale do centrum czy do plaży można się dostać w niecałe 10 minut.

Dzielnica turystyczna rozciąga się wzdłuż plaży, i nie różni się niczym od innych resortów nastawionych na plażowiczów, ale wystarczy tylko przekroczyć ulicę Kennedego, aby zobaczyć jak żyją miejscowi. Nie będą to lepianki z gliny, niemniej jednak od razu widać, że turyści często tam nie zaglądają, śmieci są wyrzucane prosto na ulicę a jedzenie jest zdecydowanie inne od tego co podają w hotelu. Kręcąc się tam wąskimi uliczkami i straganami, notabene przypominających mi zapachami Łódzki Górniak tak z przed 20 lat, mamy przedsmak tego co nas czeka w Marrakeszu.

Marrakesz

Marrakesz leży jakieś 3 godziny drogi od Agadiru, można tam zobaczyć trochę zabytków Starego Miasta (Mediny) w tym meczet i pałac sułtana. Do meczetów w Maroko, niewiernym nie wolno wchodzić, za wyjątkiem jednego który bodaj znajduje się w Casablance. Targ starego miasta, ciekawe doświadczenie, ale mi raz wystarczy. Głównie ze względu na ciągłe nagabywanie ze strony straganiarzy. Jeden to chyba się uparł, że sprzeda mi pasek, bo gdzie bym nie skręcił to czekał i wciskał mi w ręce to czego nie chciałem. Jeszcze nikt tak się nie martwił żeby mi spodnie nie spadły.

Acha informacja, dla wszystkich których bliski kontakt z wężami, małpami i tym podobnymi , przyprawia o dreszcze (bynajmniej nie radości). Nam to się nie przydarzyło, ale są tam osobnicy który potrafią, bez waszej zgody, zarzucić wam takie stworzenie na ramiona i oczekiwać, że zrobicie sobie zdjęcie i im za to zapłacicie.

Poza Medina, Marrakesz niczym nie różni się od innych europejskich miast, podsumowując byłem zobaczyłem i nieprędko tam się pojawię ponownie.

Tafraout

Mateczko położone w górach Atlas. Jakby domy były z drewna a drogi piaszczyste nie asfaltowe, to byśmy mieli idealną scenerię do kręcenia westernów. Tak mi się jakoś skojarzyło. Gorąco termometr wskazywał 45 stopni Celsjusza, ale aż tyle to chyba nie było. Pomimo wszystko, panowie drogowcy, da się zrobić asfalt który się nie topi w temperaturach powyżej 30 stopni. Miejsce jest lokalną stolicą ręcznie robionych kocy i dywanów jeśli ktoś byłby zainteresowany. Poza tym wspaniałe formacje skalne i górskie widoki. Wracając drogą do Agadiru można podziwiać, nadal zamieszkaną, warowną twierdzę Kasbah.

Jedzenie

Kulinarnym aspektem wycieczki muszę przyznać byłem trochę rozczarowany.

Spodziewałem się bogatej kuchni a okazało się, że wszystko co oferują turystom, oprócz typowo europejskich dań to trzy popisowe potrawy: kuskus, tajine i zupa z soczewicy. Albo kuchnia uboga jak w Irlandii albo po więcej trzeba zapuścić się do typowo miejscowych lokali.

Z napojów, popisowo parzą herbatę miętowa, a właściwie mix herbaty zielonej, suszonej i świeżej mięty – pite na gorąco z duża ilością cukru. Wbrew pozorom świetne na upały. W Maroko, standardowy europejczyk, powinien pic tylko wodę mineralna, butelkowana bądź przegotowana, lepiej nie ryzykować rozstroju żołądka czy w najgorszym przypadku jakiejś ameby. To samo się tyczy lodu w kostkach i lodów – do których dodawany jest zwykły lód.

Ceny

Ceny są porównywalne jak w Europie. Z początku myślałem, ze tylko w centrum są takie wysokie, aby golić naiwnych turystów – jednak nie. Zrobiliśmy sobie wycieczkę kulturoznawcza do jednego z hipermarketów Marjane i byłem zaskoczony.

W sklepie praktycznie sami miejscowi, od czasu do czasu w tłumie mignie tylko jakiś europejczyk, a ceny takie jak w Irlandii a czasem droższe. Paczka Pringels, kosztuje przeszło 3 euro. Podejrzewam, że na lokalnych bazarach (po ichniemu souk’ach) ceny są dużo niższe. I dlatego pewnie jedzenie w restauracjach nie było przesadnie drogie, za 3 daniowy obiad z butelka wina przyszło mi zapłacić 17 euro.

Niestety w hipermarkecie nie można się targować, wszędzie indziej jest to wręcz wskazane – bo jeszcze kogoś się obrazi Ot taki sport narodowy – zwykle pierwsza cenę, należy podzielić przez 4 i będziemy w okolicy ceny dla turysty. Nie problem jest z targować się z 30 do 7-8 euro, pewnie można i więcej ale to już wymaga cierpliwości, czasu, poczucia humoru i gawędziarskiego zacięcia. Podobnie z taksówkami, trzeba się targować bo próbują zdzierać – zwykle płaciłem stałą stawkę ‘turystyczną’ 20 dirchamów, ale cena wyjściowa bywała 30 a nawet 40. Są dwa rodzaje taksówek małe pomarańczowe ‘petit taxi’, kursujące w obrębie jednego miasta i ‘grand taxi’ które są większe, droższe i mogące kursować miedzi miastami. Oba rodzaje strasznie rozklekotane.

Pogoda

Bez zarzutu, szczególnie o tej porze roku. Temperatura w granicach 30 stopni, piękne słońce i wiaterek od morza. Pomimo, że koniec września to u nich pora deszczowa, nie uświadczyliśmy ani jednej kropli – z reszta nic dziwnego, cierpią tam na susze od jakiś 12 lat. Zdarzyły się nam dwa poranki pochmurne, ale do godziny 13 już świeciło słońce.

Podsumowanie

Świetne miejsce na wakacje, idealna pora roku i wszystkiego po trochu plażowania i wycieczek. Teraz pozostaje mi nic innego jak uzbroić się w nieprzemakalne wdzianko i cierpliwość. Następny wyjazd dopiero w przyszłym roku – nie pozostaje nic innego jak wspominać i planować kolejne wakacje.

Nagrania z Øredev

Wyszperałem w sieci nagrania z ubiegłorocznej konferencji Øredev. Dostępne są pod tym adresem i być może kogoś zainteresują.

Øredev odbywa się już od kilku lat i ma miejsce w Szwecji. Skupia się na zagadnieniach dotyczących Javy, .NET, Agile, DDD, architektury aplikacji.