Figuring out N-Queens with Swift

I've been programming for quite a few years now, and consider myself pretty decent at it. I'm fluent in several languages, have shipped quite a few apps, and feel I can solve most problems presented to me in a good way. As most people I also have a lot left to learn. Current endeavors includes things like finding a good balance for when to write tests and checking out the MVVM pattern.

One of the things I find myself not that good at, however, are purely theoretical tasks, like you would find in programming challenges, at school and at interviews. This is probably because I don't have a formal programming education, and as such haven't been introduced to these, as they don't appear in my day to day challenges making apps.

That's one of the reasons I've done side projects like Mine Searcher, so I could do more theoretical and logical work.

N-Queens is one of those, and it recently got mentioned to me during a chat with some iOS dev colleagues from another company. They told me that they use rendering a chess board and solving the N-Queens challenge as a part of their interview process. I thought to myself that I might be able to solve it, but I wondered how long it would take me and what kind of issues I would find.

In the last week I've been ill, and as such haven't done much work. I figured that solving the N-Queens challenge would be a good, non-critical task to get back up to speed again. So a few hours ago I opened Xcode and got to work. I figured this might be a good use for Playgrounds.

I set a few goals for myself:

  • It should solve the N-Queens properly, with an input for N (not just 8)
  • Readability should be prioritized before brevity and speed (because of this blog post)
  • I should be able to take a peek under the hood and see it working
  • It shouldn't take more than a few hours to do

Challenges during development

I hit quite a few challenges on my way. Nothing too serious, but fun to discuss nonetheless. 

Picking an environment

I knew I wanted to do this project in Swift, mainly because it's the future of Apple platform development, and I haven't written more than a few thousand lines of code in it yet.

I figured that I might as well use playgrounds as well, which I'll come back to. I figured following best practices regarding use of classes etc. wouldn't help my code that much, so I wrote everything in a single file for simplicity. When I ended up adding a normal Xcode project, I went with iOS because of familiarity, although doing it as an OS X project probably wouldn't have changed it much.

How to add chess rules

For the challenge you need to implement the movement rules of the queen piece of chess. It's not that complicated, but being away from code for a bit and still being a bit under the weather, I got caught on how to check for diagonals. Specifically, after quite quickly implementing the left-to-right diagonal, I couldn't figure out what was wrong with my check for the right-to-left diagonal.

Specifically, I had a hard time figuring out that I needed to use the board size twice when calculating which column the square would be in at this point. Of course this is one of these challenges where you suddenly get an "aha, of course" moment and feel kind of stupid afterwards. I find it interesting how these rules compare to MineSweeper, where you also need to check diagonals. The math is quite similar.

Playgrounds are slow

When I got the rules in place, I first attempted to do a brute force, to see how far I got. At this point it hit me how slow playgrounds are. I figured I could continue working in the playground until I got more of the code working, but that I might need to build a project to compile the code properly without all the playground debug voodoo enabled to run through large boards in a reasonable time.

Solving it with a bug

The first time I solved a board, I was pretty happy with myself. It was a 8x8 board, and it solved in a little more than 100.000 placement attempts. I figured that must be to much, and a few minutes later I figured out that I was right. The bug that accidentally made my code work was quite interesting though. 

The bug was here, and instead of doing like it says now, I was passing in the unchanged array of placements to the placeNewQueen function. This meant that the function would have a much harder time finding a valid place. Incidentally, another bug, or rather logical flaw, was masked by this. When I found this bug and fixed it, suddenly my code went back to looping infinitely. 

Solving the correct bug

The reason for my last infinite loop was quite hard to find. What I did to find it was enable the debugging mode I built in, so I could see what kind of moves it was making. What I found was that it followed the rules, and moved the pieces as expected, with one big flaw: When placing the last 4 pieces, it would move around piece 6 and 7 to find a place for 8, figure out that it didn't work, then move 5. Just as expected. But after moving 5 a couple of places, 6 or 7 would take it's place, because it was now valid for them.

Another "aha" moment, and a quick fix: Only check available places above the highest square with a queen. This works because of how the back stepping works. It pops the last queen of the board, and tries to find a new place for it. That way, it will only try each combination once, regardless of if it's the first, fourth or seventh piece added to the board.

Computers are fast

After fixing the last bug I tried to run my code and timing it. Now it runs in less than 1 second on my laptop, in a Swift debug build (not a Playground). It uses less than 20.000 placement attempts, which sounds way more reasonable.

Conclusion

I had fun doing this challenge. It refreshed some rarely used skills regarding logical problem solving that doesn't get flexed as much in day-to-day coding, and I got to work with Swift again, which is always a lot of fun.

Check out the project on GitHub, and add an issue if you want something clarified or have a suggestion for improvements (especially performance related, I would love to see how fast it can be if we really try).

Vaccination

Preamble

Lets start off this new blog with a light and uncontroversial topic: Vaccination. Why? Because I'm worried. I'm worried that a catastrophe is needed before the current anti-vaccination movement slows down.

Let's back up for a few minutes. Why is there an anti-vaccination movement at all? It comes down to a few unlucky coincidences. In short, after vaccination has become so commonplace that we don't think much of it, a study came along and said it might be linked to autism. This study has since been retracted, debunked and rebuffed, but that's beside the point. The train has left the station.

You see, the problem here is that a seed of uncertainty has been sown. If you combine a seed of uncertainty, based on something that sound probable to most people, with a good excuse (big pharma, government control, etc.), you've got all the ingredients for a viral conspiracy theory. And at that point, turning back becomes exceedingly difficult.

The lack of history

One of the reasons this hasn't happen, and probably couldn't happen, before somewhat recently, is the need for a lack of history. Go back just a generation or two, and you'll find people who knows someone that has died from a now preventable disease. In fact, if you talk to some of the older people in your family, they might very well tell you a story or two.

The current with-children generation, however, haven't seen friends and family die of these diseases. Their experience with illness in general is that most things are curable these days, and your doctor will probably have a pill for your ailment. So in that sense, we've got the first generation now that might consider not vaccinating their children.

Another related issue is that they'll probably be right at first, that nothing will happen to them. Because many of the diseases we vaccinate against, have been eradicated in the industrialized world. There is just one problem.

Herd immunity

Herd immunity is the effect we get when so many people are vaccinated, that we protect even those who aren't, because the chance of catching the illness in the first place is so low. This means that people who for whatever reason can't get vaccinated, are still protected, as long as they don't travel to exposed areas. 

What has happened lately though, is that this herd immunity has begun to break down in the seams. The incident that has gotten the most attention so far, is the measles outbreak at Disneyland

The math

One of the things that fascinates me the most about this whole situation is how the anti-vaccination people totally ignore any attempt at correcting their views. Be it the debunking of the autism-connection, or more information about how vaccines work, or anything else. But beyond that, for me it's the math. 

The math of vaccination is pretty simple. There are two big points to take make using math. First of all, vaccines work. The diseases they prevent are mostly extinct or all but.

The chart above speaks for itself. There are similar charts for other diseases as well. This ties in with the lack-of-history part of the problem. 

The other bit of math is the side effects math. The thing is, even if there were more adverse side effects than there actually are, vaccines would still be worth it. In fact, in many cases, even if you increase the instances of side effects ten fold, you'd still be better of taking your vaccines. And the government rules covering vaccines in most countries are erring on the side of caution by a large margin.

My guess is that people ignoring these obvious numbers are doing so because of psychological reasons. Either they are reading with confirmation bias, and only taking in things they read that confirm what they believe. So if they read something to the contrary, they will immediately discard it without really considering it. Or, they are acting illogically based on perceived severity. Many of the side effects, real or imagined, may seem so severe, that some people think they must be worse than the alternative, whatever that is. This also leads back to the lack of history, not knowing the severity of the diseases, and also probably correlates with believing that side effects are worse than they actually are. Combine this with not understanding probability and statistics, and the facts might just slip by without anyone noticing.

This kind of reminds me of the fear of flying. This is clearly an illogical fear, since being in an airplane is one of the safest places you can be, statistically. The biggest difference is that although some people choose not to fly, you won't see many aviophobians telling you that you should consider giving up flying.

The other stuff

I've got a lot of other thoughts about this subject as well, but my main point was to summarize my thoughts about the mathematics of this phenomenon, so I'll keep these other points short.

Poison in vaccines

One often cited "fact" is that there are poisonous substances in vaccines. This is based on a combination of old information and a lack of understanding of biology. Many of the dangerous substances that people are citing have at some point been in vaccines. But they are now mostly gone, or have been reduced to so low amounts (often referred to as trace amounts) that there are less of them in vaccines than we find in some of the food we eat. You should be much more worried about the lack of research and regulatory oversight in some parts of the food industry, for example.

The media

The media is somewhat to blame for this phenomenon. They have often made big stories about any hints of problem with vaccines, and if what they report is later proven wrong, they aren't good enough to admit it. This is a problem in general with the media, that any corrections turns up in a small notice far back in the newspaper or on a special, rarely linked to part of their website.

Too many media outlets have also fallen into the "everything has two sides" trap of thinking that this means that every story has two sides that are 50/50. This is really enough for a post of its own, which I'd like to come back to at some point. John Oliver pointed this out in his excellent walkthrough of the climate change debate.

What to do

I don't really have a definitive answer, and honestly, I don't think there is one. I've seen debates where facts are presented and ignored, where myths are presented and debunked, only to have the whole thing end up in a shouting match, every time. A few do recognize facts when they are presented well enough, but I don't think that will convince everybody. 

I think the biggest impact would be if the media changed their tune. The first part would be to present the factual research without also giving equal space to the myths, as well as keep reporting the effects we are starting to see with outbreaks. 

Schools and other authorities that some parents listen to can also have a good influence, and as such their voice need to get out there. 

As for each of us? Keep on answering questions with facts. Don't get angry. Don't allow discussions to become shouting matches. Try to keep it calm and civil, and some points might come across. 

If this anti-vaccination movement doesn't stop in time, I'm afraid that it will be stopped by a catastrophic outbreak, too late for us to avoid the severe consequences that may entail. Let's hope we don't have to find out what that looks like.

Update: @kimroen sent me this excellent video over at the SciShow YouTube channel, where Hank Green goes into more of the underlying psychological reasons for why people are predisposed to believe that vaccines are dangerous. I highly recommend watching it.