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