As WWDC 15 week comes to a close, I thought I would try my hand at writing a Swift 2 solver for the Eight Queens Puzzle. My inspiration is actually due to the fact that I am watching the MIT SICP Lecture Series. Eight Queens was mentioned by Hal Abelson during one of the lectures after assignment was introduced. The solution I am presenting is not a good one. But it does the job. It does a brute force search through 16,777,216 (that is, 8^{8}) combinations and produces the 92 distinct solutions.

The code is in this Gist followed by the output as produced from running in the Xcode 7 beta (7A120f) debugger. Then I will proceed to discuss the code.

[gist user=”DavidSteuber” id=”f85e6a6487e3d40bb01e”]

Solution 1: [3, 1, 6, 2, 5, 7, 4, 0] in 1299851 steps Solution 2: [4, 1, 3, 6, 2, 7, 5, 0] in 1551564 steps Solution 3: [2, 4, 1, 7, 5, 3, 6, 0] in 1695330 steps Solution 4: [2, 5, 3, 1, 7, 4, 6, 0] in 1733354 steps Solution 5: [4, 6, 0, 2, 7, 5, 3, 1] in 3077172 steps Solution 6: [3, 5, 7, 2, 0, 6, 4, 1] in 3343851 steps Solution 7: [2, 5, 7, 0, 3, 6, 4, 1] in 3355114 steps Solution 8: [4, 2, 7, 3, 6, 0, 5, 1] in 3434452 steps Solution 9: [4, 6, 3, 0, 2, 7, 5, 1] in 3645684 steps Solution 10: [3, 0, 4, 7, 5, 2, 6, 1] in 3759875 steps Solution 11: [2, 5, 3, 0, 7, 4, 6, 1] in 3829994 steps Solution 12: [3, 6, 4, 2, 0, 5, 7, 1] in 4097331 steps Solution 13: [5, 3, 1, 7, 4, 6, 0, 2] in 4410973 steps Solution 14: [5, 3, 6, 0, 7, 1, 4, 2] in 5304733 steps Solution 15: [0, 6, 3, 5, 7, 1, 4, 2] in 5307120 steps Solution 16: [5, 7, 1, 3, 0, 6, 4, 2] in 5441149 steps Solution 17: [5, 1, 6, 0, 3, 7, 4, 2] in 5484941 steps Solution 18: [3, 6, 0, 7, 4, 1, 5, 2] in 5557811 steps Solution 19: [4, 7, 3, 0, 6, 1, 5, 2] in 5562620 steps Solution 20: [3, 7, 0, 4, 6, 1, 5, 2] in 5564475 steps Solution 21: [1, 6, 4, 7, 0, 3, 5, 2] in 5607217 steps Solution 22: [0, 6, 4, 7, 1, 3, 5, 2] in 5611312 steps Solution 23: [1, 4, 6, 3, 0, 7, 5, 2] in 5736353 steps Solution 24: [3, 1, 6, 4, 0, 7, 5, 2] in 5736843 steps Solution 25: [4, 6, 0, 3, 1, 7, 5, 2] in 5740084 steps Solution 26: [5, 3, 0, 4, 7, 1, 6, 2] in 5830685 steps Solution 27: [4, 0, 3, 5, 7, 1, 6, 2] in 5831364 steps Solution 28: [4, 1, 5, 0, 6, 3, 7, 2] in 6152524 steps Solution 29: [5, 2, 6, 1, 7, 4, 0, 3] in 6452117 steps Solution 30: [1, 6, 2, 5, 7, 4, 0, 3] in 6453937 steps Solution 31: [6, 2, 0, 5, 7, 4, 1, 3] in 6715926 steps Solution 32: [4, 0, 7, 5, 2, 6, 1, 3] in 6761412 steps Solution 33: [0, 4, 7, 5, 2, 6, 1, 3] in 6761440 steps Solution 34: [2, 5, 7, 0, 4, 6, 1, 3] in 6767082 steps Solution 35: [5, 2, 0, 6, 4, 7, 1, 3] in 6802453 steps Solution 36: [6, 4, 2, 0, 5, 7, 1, 3] in 6803622 steps Solution 37: [6, 2, 7, 1, 4, 0, 5, 3] in 7619542 steps Solution 38: [4, 2, 0, 6, 1, 7, 5, 3] in 7838740 steps Solution 39: [1, 4, 6, 0, 2, 7, 5, 3] in 7840161 steps Solution 40: [2, 5, 1, 4, 7, 0, 6, 3] in 7895146 steps Solution 41: [5, 0, 4, 1, 7, 2, 6, 3] in 7959301 steps Solution 42: [7, 2, 0, 5, 1, 4, 6, 3] in 8002071 steps Solution 43: [1, 7, 5, 0, 2, 4, 6, 3] in 8003961 steps Solution 44: [4, 6, 1, 5, 2, 0, 7, 3] in 8137332 steps Solution 45: [2, 5, 1, 6, 4, 0, 7, 3] in 8146026 steps Solution 46: [5, 1, 6, 0, 2, 4, 7, 3] in 8266125 steps Solution 47: [2, 6, 1, 7, 5, 3, 0, 4] in 8511090 steps Solution 48: [5, 2, 6, 1, 3, 7, 0, 4] in 8631189 steps Solution 49: [3, 1, 6, 2, 5, 7, 0, 4] in 8639883 steps Solution 50: [6, 0, 2, 7, 5, 3, 1, 4] in 8773254 steps Solution 51: [0, 5, 7, 2, 6, 3, 1, 4] in 8775144 steps Solution 52: [2, 7, 3, 6, 0, 5, 1, 4] in 8817914 steps Solution 53: [5, 2, 6, 3, 0, 7, 1, 4] in 8882069 steps Solution 54: [6, 3, 1, 7, 5, 0, 2, 4] in 8937054 steps Solution 55: [3, 5, 7, 1, 6, 0, 2, 4] in 8938475 steps Solution 56: [1, 5, 0, 6, 3, 7, 2, 4] in 9157673 steps Solution 57: [1, 3, 5, 7, 2, 0, 6, 4] in 9973593 steps Solution 58: [2, 5, 7, 1, 3, 0, 6, 4] in 9974762 steps Solution 59: [5, 2, 0, 7, 3, 1, 6, 4] in 10010133 steps Solution 60: [7, 3, 0, 2, 5, 1, 6, 4] in 10015775 steps Solution 61: [3, 7, 0, 2, 5, 1, 6, 4] in 10015803 steps Solution 62: [1, 5, 7, 2, 0, 3, 6, 4] in 10061289 steps Solution 63: [6, 1, 5, 2, 0, 3, 7, 4] in 10323278 steps Solution 64: [2, 5, 1, 6, 0, 3, 7, 4] in 10325098 steps Solution 65: [3, 6, 2, 7, 1, 4, 0, 5] in 10624691 steps Solution 66: [3, 7, 4, 2, 0, 6, 1, 5] in 10945851 steps Solution 67: [2, 4, 7, 3, 0, 6, 1, 5] in 10946530 steps Solution 68: [3, 1, 7, 4, 6, 0, 2, 5] in 11037131 steps Solution 69: [4, 6, 1, 3, 7, 0, 2, 5] in 11040372 steps Solution 70: [6, 3, 1, 4, 7, 0, 2, 5] in 11040862 steps Solution 71: [7, 1, 3, 0, 6, 4, 2, 5] in 11165903 steps Solution 72: [6, 1, 3, 0, 7, 4, 2, 5] in 11169998 steps Solution 73: [4, 0, 7, 3, 1, 6, 2, 5] in 11212740 steps Solution 74: [3, 0, 4, 7, 1, 6, 2, 5] in 11214595 steps Solution 75: [4, 1, 7, 0, 3, 6, 2, 5] in 11219404 steps Solution 76: [2, 6, 1, 7, 4, 0, 3, 5] in 11292274 steps Solution 77: [2, 0, 6, 4, 7, 1, 3, 5] in 11336066 steps Solution 78: [7, 1, 4, 2, 0, 6, 3, 5] in 11470095 steps Solution 79: [2, 4, 1, 7, 0, 6, 3, 5] in 11472482 steps Solution 80: [2, 4, 6, 0, 3, 1, 7, 5] in 12366242 steps Solution 81: [4, 1, 3, 5, 7, 2, 0, 6] in 12679884 steps Solution 82: [5, 2, 4, 7, 0, 3, 1, 6] in 12947221 steps Solution 83: [4, 7, 3, 0, 2, 5, 1, 6] in 13017340 steps Solution 84: [3, 1, 4, 7, 5, 0, 2, 6] in 13131531 steps Solution 85: [3, 5, 0, 4, 1, 7, 2, 6] in 13342763 steps Solution 86: [5, 2, 0, 7, 4, 1, 3, 6] in 13422101 steps Solution 87: [4, 2, 0, 5, 7, 1, 3, 6] in 13433364 steps Solution 88: [3, 1, 7, 5, 0, 2, 4, 6] in 13700043 steps Solution 89: [5, 2, 4, 6, 0, 3, 1, 7] in 15043861 steps Solution 90: [5, 3, 6, 0, 2, 4, 1, 7] in 15081885 steps Solution 91: [3, 6, 4, 1, 5, 0, 2, 7] in 15225651 steps Solution 92: [4, 6, 1, 5, 2, 0, 3, 7] in 15477364 steps DONE Program ended with exit code: 0

First off, I would like to say that the program ran surprisingly quickly considering how poor the code is. At least I think it’s poor. I will point out a few places where the code could be improved in just a bit. Most of the surprise comes from the fact that I was running a brute force algorithm. This is because I’m not very good at math. You may have heard otherwise or even have a differing opinion, but solving interesting problems requires some math ability. On to the code.

Even though Apple is pushing Protocol Oriented Programming (about time too!), I did very little of that in this program. My only use of protocols was to inherit from ErrorType for the one error that my program can produce. That also brings up exception handling which is one of the new Swift features I use. I shall defer that discussion until after I have described in high level detail how the program works. Yes, that pun was intended. I didn’t use it in the program.

The first step to the puzzle was working out a strategy. There are a number available. Due to my lack of math ability, I went with one of the brute force approaches. I don’t know how it fairs compared to the Pascal code written by Niklaus Wirth published in the Wikipedia article. At least I can understand it, unlike Wirth’s solution which is totally befuddling. I reduced the level of brute force required by deciding to start with all eight queens on the board, each in its own file. I would then find some way of orderly iterating through all the possible combinations and finding the ones that passed the test.

To implement that strategy, I created a data type called Chessboard. As you can see, it is a struct that inherits no protocols. Within the scope of that struct, I defined an ErrorType to handle the one serious error I could expect and a single data member which happens to be an array of eight Ints. I should mention at this point that it would not be too difficult to generalize the program to deal with an NxN board where N > 3 and N is not so large that the program won’t complete in your lifetime. As this is a quadratic algorithm, that means N has to remain fairly small.

Conveniently enough, the array of integers can easily be interpreted to represent a number of arbitrary radix. I also chose to use a “big-endian” interpretation so I could work left to right. That was fairly arbitrary but also probably a bit easier to deal with than a “little-endian” representation. Each member of the array represents a file (column). The value represents the rank (row) that the queen is in. The member functions of the Chessboard struct manage the array accordingly. I made it private to mark that it should not be messed with by the outside world.

In this example, the numbers are from 0 – 7 (8 values like in Octal notation) to represent the eight ranks on the chessboard. There are eight of them to represent the eight files on the chessboard. This leads directly to going from one board position to the next. It’s a simple increment. The member function nextBoard() returns an incremented position. The work is handed off to init(b: Chessboard) which is labeled both private, because it does not state that it is delivering a different chessboard, and also labeled with throws because there is a situation where it may fail.

Let’s look at that. The private function inc() is responsible for doing the math of incrementing the board array as if it is an integer in big-endian format. It does no error checking. A guard is therefor placed in the initializer to throw an exception if all the queens are in the last rank. This is the one time the initializer may fail. Notice that I’m not using the failable initializer syntax from Swift 1.2. I’m using exception handling instead. This is a pattern I am familiar with and will certainly stick to. I’ve never even used the failable syntax before. nextBoard() handles the exception by simply returning self. This could lead to an infinite loop if there was no way to check that you had run out of board positions. That is what the isLast() method is for. It is used in the loop at the end to terminate the loop. The loop uses the new repeat-while syntax.

One other thing has to be done. The board position needs to be evaluated to see if it is a solution to the puzzle. isSolution() does that in two steps with the aid of the helper methods (which should be private) rankAttacks() and diagonalAttacks(). A little more work goes into diagonalAttacks() so it is on the tail end of the || operator for short circuiting purposes. That’s just a micro-optimization that probably doesn’t make much difference. I haven’t bothered to profile the program.

A quick word on rankAttacks() and diagonalAttacks(). They both have the same pattern. Only the contents of the inner loop differ. This is a screaming invitation to factor out the common functionality and use either Lisp style macros (which don’t exist in Swift) or a method that accepts a function as its argument to compute the Boolean result. Obviously I didn’t bother. Still, it should be possible to do with little to no performance impact. Something to think about.

There is also a method in Chessboard that breaks the abstraction barrier. That is getBoardRep(). It returns the board array. This is for simple convenience to run in the debugger without having to do any real work. Real work would mean passing back an object that is specified in such a way that another function or object could then present a textual or graphical representation of the chessboard and queen positions. This idea can be taken even further if the chessboard was to represent an actual chess game.

I think I have pretty much described the entire program in depth now. In summary, eight queens are positioned in the 0th rank of the board. Each queen is confined to its file. The state of the board is iterated as if it is a number in big-endian notation. Each state is evaluated to see if it is a solution state. Solution states get printed out in the debugger. When all the states are exhausted, the program is finished. The run time is surprisingly short. A better algorithm would run in even less time (fewer steps). Some Swift 2 features are used, namely for error handling.

I hope you enjoyed this posting and the program. I was hoping for something that could run in a playground, but I’m not that clever.