Solving Minesweeper – Part 1: The Plan

Posted on by

What i will attempt in this multi part post, is to write an application that will be able to play and solve Microsoft Minesweeper. I know it feels ambitious but i think we can make it happen. Since this is my first post where i don’t actually know how and what will i do, i cannot promise i won’t change technologies or frameworks in the meantime. So strap yourselves in and lets think it through.

I approach this like any other larger scale work i need to do, i break it down to smaller more manageable items, then devise an approach for each of them.

  1. I need to get the current image of Minesweeper. Whenever you press ALT + PRINTSCR in a window, the contents of that window gets copied into the clipboard. I know i will find something in WinAPI that will help me with that.
  2. I need to analyze the image and extract the current state of the board. I can approach this by doing pattern matching on the image either writing it myself or using an image analysis library like OpenCV
  3. I need to write the logic which detects where the mines are. I will probably use an approach like what i used in the Solving Sudoku post.
  4. I need to make actions in the game. In the past i worked with moving the mouse and issuing click commands from my application using WinAPI

A lot of time past since my last post and you probably think i was slacking off. It’s nothing like that. I had this idea a while ago and i spent some time researching each problem we need to solve, in my after work and after family hours.

I’m looking forward to this and see you soon.

The Mandelbrot Set with CUDA

Posted on by

Back in my high school days, i was into distributed computing. It was the era when computers pretty much consumed the same amount of power even if they were idle. I’ve chosen to dedicate my CPU cycles to SETI@home (yeah i was a big fan of Contact). First through the dedicated installer, later through BOINC. My contribution was pretty average but around 2007 i’ve noticed that some users spiked and started to produce pretty awesome numbers.

It was the year when NVIDIA launched their first CUDA enabled GPU which meant that you could use your card for more than gaming. The CPU is a general purpose processing unit and i’ts really good at doing anything. As you know when you are good at a lot of things you cannot be great at anything. The GPU on the other hand does the same type of mathematical computations over and over again. Practically each pixel in a game is rendered in the same way. So in short the GPU is optimized architecturally to carry out a lot of parallel tasks.

In my Mandelbrot set generator last time you saw that we do the same mathematical calculations for each pixel in the image. Since you know i love performance optimizations, let’s try to use CUDA to offload these intensive computations onto our GPU.

Continue reading →

Solving Sudoku

Posted on by

I like to write puzzle solvers, they refreshes my thinking. You probably learned in your algorithm classes that in these cases you can resort to backtracking. While backtracking is surely a solution in many theoretical cases, it can rarely be utilized in real life applications since the performance impact is huge.

Sudoku is one of those kind of puzzles which seem trivial to solve with a backtracking but lets think about it. There are 81 positions, each position can have 9 different values, generating through the space of potential solutions and validating each and every step could take ages.

Let’s instead of backtracking, track the possible values that each cell can have. This is how humans solve it and it will bring us very far in the solution. Here are the data structures i propose.

Continue reading →

Let’s care about performance

Posted on by

Performance of applications I write was always something I deeply cared about. I’m talking about using as few resources as possible, but of course not in the detriment of other important things. Teams often neglect this and take action only when there is a perceivable performance issue.

When is the right time to optimize?

I would say it always need to be on your mind, but before you wrap up the project it is always good to tighten the screws and optimize what you can.

Decisions around your data model will have a big impact on performance and it is very hard to change at the end phase of a project. This is the reason why I say, you need to be mindful about performance all the time.

In the last sprints of the project, most of the important flows are already there. You understand the application a lot better then you did in the beginning. Since everything is there this period is a good opportunity to poke around and see how some important flows perform. Also you are in a better position to form and educated opinion whether something needs improvement or not.

Continue reading →

Have fun with post build events

Posted on by

It’s important to have some fun in the project you work on. It helps in releasing some stress. Our project goes through a stressful phase now. Deadlines are getting closer and some of our arguments get more heated then they should. It would be a good idea that we go out for some beers but we work in different cities so it’s not that easy. After a meeting like I mentioned, a colleague and me thought it would be nice to play a little trick on another colleague. I took up the challenge and I promised I would think of something.

I figured, let’s me mess with him in a harmless but funny manner. My first thought was to implement some kind of Easter egg, but I didn’t wanted to affect the code. Our current client might not enjoy it as much as I would hope. So I had to think of something that only applies to him and not the code, so this is what I ended up doing.

for /f %%i in ('whoami') do (
IF "%%i" == “DOMAIN\user" (
IF %RANDOM% LEQ 12000 (
start chrome "https://youtu.be/_4IRMYuE1hI"
)))

These are a few simple CMD commands that you can place in the post build event for any Visual Studio project (other editors probably have a similar feature). You can collapse it to one line, I have it like this just to show you better what it does.

I wanted the trick to apply only to him without people around him knowing. The first command requests the currently logged in users name from the system. The second if checks the returned username and compares it to the targeted user. I wanted it to execute only roughly 33% of the time so I achieve that by rolling a random number between 0 and 32768. That is what the third check achieves. If these two conditions are met, I start chrome on a specific link: Beethoven’s 5th symphony. It is harmless, but I’m sure you can think of something darker, if you wish to do so.

This code will reach the server next week. I’ll keep you posted of its effect. Stay tuned!

Posted in Fun