.NET i takie tam

Posts Tagged ‘C#

Sudoku Solver in C#

2 Komentarze

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:

sudoku

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.

Reklamy

Written by sakowicz

Styczeń 2, 2012 at 10:22 pm

Napisane w .NET, Aplikacje

Tagged with , , , , , ,

Performance Counters i ich kategorie

leave a comment »

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.

image

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.

Written by sakowicz

Marzec 14, 2011 at 9:39 pm

Napisane w .NET, Aplikacje

Tagged with , , ,

Partial Methods

leave a comment »

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.

Written by sakowicz

Luty 28, 2011 at 11:48 pm

Napisane w .NET

Tagged with , , ,