An Eight Queens Puzzle Solution in Swift 2

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

 

Published by

David S

David Steuber

I'm the administrator of this facility.