My first project in Python: a sudoku solver

Background

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

Knockout

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

https://github.com/carlbjorknas/sudoku_solver_in_python

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. 

https://www.quora.com/Is-Python-a-functional-language

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 :)

Portal site to blogs by municipality-politicians

During a period of less than a year I was an active municipality-politician with a place in the strategy committee of the City Council. It was an interesting time and I learned a lot about the politics of the municipality that I really hadn't had a clue about before. It was also a really frustrating time, feeling that I never had enough time to study the matters brought up in the committee that I should have an opinion about to be able to know how to vote. The majority of the municipality-politicians have to do their politic work at their free time and that was also the case for me.

As a software developer I'm used to find bits and parts of solutions to tasks I have to solve by searching the web. But in municipality politics I don't think it's common that you can find things by googling them. I wanted to find history about some of the matters, well, when there existed a history it was hidden in the heads of the politicians that had been in the game for quite a while. They sure wanted to talk about the past, but it is really time consuming to learn by finding people that have the knowledge and then have a chat about it. There probably exists lots of information in the archives too, but I'm not sure it would be any faster to find it there.

On the municipality home page you can at least find summonses and protocols in pdf-format for a few years back. The problem was that the content of the pdf-files was images of texts instead of normal, searchable, copy-and-paste-able text.

After experiencing the breadth of the matters dealt with in the committee, I finally understood that to have any constructive influence on the politics I would have to devote much more time for it than I had done so far. I wasn't up for that.

Anyway, my time as a politician made a small impact on information findability. I wrote a motion about the need to have the content of the summonses and protocols files in text format instead of images of text. The motion was approved and after that it became possible to find content in the files created afterwards by just googling some keywords! (... but sadly it just worked for a few months and then it was images of text again, probably caused by bad rooting of the new routines. Sometimes I try to remind them, but I usually have a hard time describing that the text really is images...)

So why did I tell you all this? Well, probably as an introduction to why I coded and published the site Blogging Municipality-Politicians. I want to make information regarding municipality-politics to be easier to find, and one way to do it I thought, was to create a portal site that lists all living blogs that are written by municipality-politicians. I didn't do much research beforehand, so I'm not sure there are that many blogs to add to the list, really. But it's worth a try and I probably will learn something along the way! :)


UPDATE 2017-05-30

None of the people I've been in contact with about this has shown any interest at all in a site like this. So, I'll leave it abandoned.

SignalR laboration: Reaction Time Game

About two years ago I decided to learn the basics of SignalR by doing a small laboration. The laboration became this Reaction Time Game where the players try to be the fastest to click a button after it has changed color from yellow to green. It has a high score list and a chat.

When playing on my smart phone, a Samsung S3, it is impossible to get an good honest reaction time registration. On the computer I get around 300 ms and on the phone around 800 ms, I'm not sure why this is the case. Maybe because of less CPU power, slower wifi or slow tap registration on the screen?

Of course @ordbajsarn had to hack it almost at once. The SignalR hub sends a signal to all clients when it's time for the button to change color. He changed the java script on his client to simulate a click on the button as soon as the color-change signal was received. This way he got really low reaction times registered on the server side. I guess I could guard against this by setting a limit on how many times in a row a client is allowed to have an unreasonable low reaction time. But the code is open source now and therefore a user can see whatever cheat guards are used. So, two questions from this laboration is: is it possible to have the source code open and still catch cheaters? How then?

Btw, the repository is here.

Interactive Alchemy Walkthrough

Me and two of my colleagues were lunching. One of them talks about games he remembers.

In one of the games you could design a creature and then send it off to a world you couldn't see, to live with other creatures created by other players. Then you got to see statistics about the creature's life, how many other creatures it had encountered, how many it had eaten and so on. And finally the creature got eaten by one of the other creatures, The End.

In another similar game you got your creature by scanning the bar code of any product, the bar code coded the properties of the creature. And then you send it off to fight other creatures. The bar code of one product created an invincible creature with enormous powers! And that bar code could be scanned from a ... packet of noodles! :)

I told them that I've been thinking to and from about creating a similar game, where the players can design a creature or anything that lives or builds up a world. Not really fighting each other, more helping each other. And I'd also like genetic algorithms so that the players creations can mix and become new creations with new properties. So far I haven't had a sufficient good idea to start coding on anything.

Suddenly the other colleague whips out his smart phone and shows me a game he's been playing, Alchemy. You start with the four elements Earth, Wind, Fire and Water and then combine them to get new elements. Then you can use the new elements in new combinations. The game seemed so simple that I LOLed at it. But then I tried it myself and instantly got hooked!

It didn't take long though before I found out that this game really could eat my time and that it behind the scenes existed a rather simple tree with combination rules. I wanted to see that tree! I searched for cheats, and of course there existed multiple sites with complete solutions to all possible combinations. But all sites I found more or less plainly listed the combinations, sorted alphabetically, often with hyperlinks (like this and this). A great help and time saver for sure, but not as clear as I pictured it in my head.

So, I used the combination recipes from one of the sites and created an interactive walk-through instead, which made the inheritance tree visible. And I got rid of the want-it-out-of-my-head itch :)