onsdag 28 november 2018

My first project in Python: a sudoku solver


It was a weekend a few weeks ago when my youngest child saw a sudoku in the paper and wanted to solve it. It was a hard one. And when they are hard I can't keep it all in the head and need to write remaning possible numbers down, but most often I don't find room for that. And for hard sudokus you sometimes have to guess for a number and try that out. When that guess turns out to be wrong, it is no fun at all to backtrack to how the sudoku board looked like before the guess. Both problems can be solved by a computer though! :)

Last time I wrote a sudoku solver was back in 2006 when learning Ruby. I've looked in all my stashes for that code, but it seems to be lost forever. This time the language that I've been looking at besides C# was Python, but so far I hadn't written anything else than short exercises, so it seemed like a good fit to try using it for a small project like this.

I don't even dare to google for sudoku solvers, there probably exist thousands of them, but I want to do this small project in my own little bubble.

Used techniques


This is what the board looks like. The nine squares on the board will be called "big squares", and the dots represents the squares that will be called just "squares" or "small squares".
In this example the user has entered two known values, a 9 and a 5. 

When running the solver in knockout mode it will knock out the known values from the list of possible values for all other squares. In the example below the value 9 has been knocked out from all squares inside the yellow marking which contains:
1. the big square that the 9 is in,
2. the row the 9 is in
3. and the column the 9 is in

The same goes for the 5, which affect all squares inside the red marking.

When there is a list of numbers in a small square, it is a list of values that still is valid to try out for that small square for solving the sudoku. Therefore, the lists of possible values inside the yellow marking all lacks the number nine, and all the lists inside the red marking lacks the number 5. Small squares that are inside both the yellow and red marking lacks both 9 and 5.

When the knockout runs and a value is knocked out from a square which value list suddenly only contains a single value, that square has become solved by the algorithm. Another round of knockout will be run for that square so its new value will be knocked out from all the squares the solved square affects.

Find unique value

When no more squares can be solved using the knockout technique, the next thing to look for is a list which contains a value that is unique in its big square. In the example in the image below, the square inside the red marking is the only square inside its big square (yellow) that still has the value 7 as a possible value. Therefore the square can be solved with that value and might kick off a new round of knockouts. This example won't though

Brute force

When no more can be done by the other two techniques, it's guessing time. For this, the solver goes looking for the first square with the lowest count of remaining possible numbers. In the board below it is the square marked with red that contains possible numbers 3 and 7.

The solver will begin to try with the number 3. So it sets the square to that value and then runs the "knockout" and "find unique value" routines. 
For this guess the board ends up looking like the board in the top of the image below. This board state is a fail because of the solved numbers the big square in the middle of the bottom row, there are two occurences of the number 8.

That erroneus state makes the solver understand that it has to backtrack to the last guess and try out the other value, in this case number 7.

Some sudokus requires multiple squares to be solved using the brute force routine. In the example above the printout says "Brute forcing 4 squares", which means that three other squares has gotten their value by guessing before the processing of the current square.

The code

The solution is a bit unfocused because I never decided if I wanted to build a complete solver or just a helper that could help us a little bit when trying to solve hard sudokus during the weekends. 

Another reason the code might seem strange is that I wanted to investigate the functional side of Python, but didn't get any relevation. Which isn't too strange I just found out, reading the answers in the link below. 

Over all I would say that Python isn’t very functional at all, and if you try to force a functional style into python it doesn’t feel very natural, and you will have to break out of it each time you want to use a third party library.

So writing a solver in F# or Haskell might be material for another project, but currently I'm a bit fed up with sudokus :)

torsdag 22 november 2018

Do you know the keyboard shortcuts for the kanban board in TFS?

Here's a list with lots of keyboard shortcuts for TFS and Azure DevOps (former Visual Studio Team Services former Visual Studio Online).

The shortcuts below are the ones I've been missing the most. Sometimes it takes quite a bit of patience to move a work item around the board, especially if there is scrolling involved. I'll try them out first thing at work tomorrow!

And there seems to be a rich text editor coming up!

tisdag 13 november 2018

Alter template for "Create and initialize field" in Visual Studio to get fields prefixed with underscore

I've got a fresh installation of Visual Studio and this time I haven't added Resharper. And so far I don't miss it! I haven't been hammering out that much code, but it seems like the built in code assistent in Visual Studio has become way better, because I usually, almost immediately, greatly miss the extra help I get from Resharper.

What I've already found though, is that its auto generation of fields from parameters to the constructor needs some tweaking. Well, if you like to prefix your fields with an underscore that is.

In case you didn't know, you can position the marker on a new constructor parameter and press "Ctrl + ." to open up the Quick Actions and Refactorings menu.
Then you can choose to Create and initialize field and get presented with a preview of what the result will look like.
The images below shows what it looks like with the default setting.

Visual Studio automatically creates the field "arg1" and assigns it with the constructor parameter.

I prefer fields to be prefixed with underscore to make it possible to immediately distinguish fields from local variables when reading the code, which I think is a great help when trying to get a grip of what the code does. And it seems to be the standard for .net core.

To change the template for this, go to 
Tools -> Options -> Text Editor -> C# -> Code Style -> Naming

Click Manage naming styles. Add a naming style like the one below.

Add a new row by clicking the plus. 
Select Private or Internal Field as Specification.
Select your new naming style as the Required Style.

Click OK. 
I had to restart Visual Studio make the update work.

Now it looks like this:

And the result is:

Of course Stack Overflow had the remedy when I became tired of renaming my auto generated fields and removing "this.". So thanks for that kspearrin and Maciek! :)

onsdag 7 november 2018

Fun fact: Origin of "upper-case" and "lower-case"

UPPER-CASE and lower-case

These terms originated from the common layouts of the shallow drawers called type cases used to hold the movable type for letterpress printing. Traditionally, the capital letters were stored in a separate shallow tray or "case" that was located above the case that held the small letters.

Info from https://en.wikipedia.org/wiki/Letter_case

Original image from https://upload.wikimedia.org/wikipedia/commons/1/1a/Upper_case_and_lower_case_types.jpg

söndag 4 november 2018

Just finished Fran Bow, a game from Killmonday Games in Hedemora

After reading in the local paper that there is a computer game studio, Killmonday Games, in Hedemora now, (probably the very first, with a released game anyway), I felt that I had to try the game they'd produced. I found their game Fran Bow on Steam, it is a point and click adventure game with a really dark, bloody and insane feeling to it. I think you understand by looking at the trailer.

Luckily I like point and click games, so now, after a total of 10 hours of playing according to Steam I've finished it.

I liked the varied puzzles and that you only got a handful of items in the inventory and that the different places visited were pretty restricted. During the last year I've been replaying the first episodes of Monkey Island with my daughter and many times got rather frustrated over how many things Guybrush carries around and how many places he can go to. It leads to too much trial and error and that's avoided in Fran Bow!

I also liked that you could double click when walking to the next scene, which instantly takes you there.
What I disliked though, was the sluggish conversations, which also could be sped up some by well-timed double clicks though, but led to lots of clicking during conversations and it was hard to get the timing right and you still have to wait a while before the next text showed up.

I've got the impression that the game has a big fan base. I didn't become a fan, but found it playable and wish Killmonday Games good luck with their upcoming games!

Are the line numbers missing in the call stack of your logged exceptions?

Sometimes when being on a bug hunt it can be a great help to read the call stack of a logged exception and to be able to see which line the exception was thrown from.

So, if your logs lacks line numbers like this one below, you don't get that extra help...

System.NullReferenceException: Object reference not set to an instance of an object.
   at LineNumberDemo.Program.ThirdMethod(Int32 value)
   at LineNumberDemo.Program.SecondMethod(Int32 value)
   at LineNumberDemo.Program.FirstMethod(Int32 value)
   at LineNumberDemo.Program.Main(String[] args)

To fix that you have to change the Debugging information setting in the project's build settings. 
- Open the Properties for your project. 
- Click Build > Advanced and change "Debugging information" from "None" to "Pdb-only".

The pdb (Program database) files contains the infomation needed to map an instruction in your program to the original line in the source file. After changing that setting the log now looks like this:

System.NullReferenceException: Object reference not set to an instance of an object.
   at LineNumberDemo.Program.ThirdMethod(Int32 value) in C:\Code\LineNumberDemo\LineNumberDemo\Program.cs:line 42
   at LineNumberDemo.Program.SecondMethod(Int32 value) in C:\Code\LineNumberDemo\LineNumberDemo\Program.cs:line 35
   at LineNumberDemo.Program.FirstMethod(Int32 value) in C:\Code\LineNumberDemo\LineNumberDemo\Program.cs:line 29
   at LineNumberDemo.Program.Main(String[] args) in C:\Code\LineNumberDemo\LineNumberDemo\Program.cs:line 16

In Visual Studio 2017, "Pdb-only" is the default setting for the Release configuration, but I'm not sure it always has been, because I've seen lots of projects that did not include the pdb-files. They make the release bigger, but as long as that isn't a problem, I don't see any reason to not include them.

Good bug hunting!