.NET i takie tam

Sudoku Solver in C#

with 2 comments

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.

About these ads

Written by sakowicz

Styczeń 2, 2012 at 10:22 pm

Napisane w .NET, Aplikacje

Tagged with , , , , , ,

Odpowiedzi: 2

Subscribe to comments with RSS.

  1. Pisałem ze 3 lata temu sudoku generator i solver w Javie korzystając z podobnych technik :) Jeśli jesteś zainteresowany tematem mam ebooka opisującego algorytmiczne podejście do sudoku, mogę się podzielić.

    Daniel Dymek

    Listopad 8, 2012 at 10:50 am


Dodaj komentarz

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

Obserwuj

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

%d bloggers like this: