nQueens – another approach.

I was recently given then problem, “Given an N-sized chess board, give us an example of one solution where you can place N queens on the board so that they wont attack each other, or tell us how many possible solutions there are to a board of N size.”

When I look up documentation on CS problems, higher level math, or even music, they exhibit a few tendencies that make reading the document a slog-fest. They are dry, dense, and steeped in jargon. I feel like I already need to know the answers I’m looking for, in order to parse what they are saying. This catch-22 is terrible. So this post, and hopefully all future ones, will be more casual and full of pictures.

Let’s rephrase the above question in a more approachable fashion, I am also going to condense them into one question. “If I give you a 5×5 grid, show me all the different ways you can place 5 queens on that board so that they can’t attack each other.” Queens are prone to unprovoked attacks it would seem.

Lets take a second here to analyze the question, take out any hints we can from the question, and break the problem down into some simpler chunks.

The first bit to notice, is that the problem asks you to place 5 queens on a 5×5 grid. (I know the original problem is n, but we are sticking with the 5. I drew up pictures, they say 5, not N.) Why only 5? Why not more? As you may have deduced, every time you place a queen on the first row, because the queen can move any number of squares horizontally, there are no more safe places on the first row. With this logic alone, we can safely say that on a 5×5 grid you can never have more than 5 queens without some aggression.

Queens can move vertically as well as diagonally any number of squares. Our logic so far looks like, “If you place a queen on row ‘a’, then no other queens can on row ‘a’. ” Is really easy to port over to columns, “If you place a queen on column ‘1’, then no other queens can be placed on column ‘1’.” However it doesn’t port nearly as well to diagonals. So let’s put diagonals on hold for a second and concentrate on rook movement (horizontal and vertical.)

Let’s now break up all possible solutions into 2 arrays that look like:

Rows – [a,b,c,d,e]

Columns – [1,2,3,4,5]

Before we placed our first rook at ‘a,1’, our possibility space looked like the above 2 arrays. You can pick any letter from the first array, and any number from the second array and the result is a valid spot.

Let’s now update the array to reflect our choice of ‘a,1’, we should also save our choice somewhere for later reference.

Rows – [b,c,d,e]

Columns – [2,3,4,5]

Occupied – [‘a,1’]

If we were running this in a computer, the next logical choice would be ‘b,2’, but I am feeling more like ‘c,3’. For no particular reason. Let’s see what that looks like

Rows – [b,d,e]

Columns – [2,4,5]

Occupied – [‘a,1’ : ‘c,3’]

At this point, I’m confident that our logic is sound for horizontal. Whenever we pick a spot, we remove that spot’s letter from the Rows array, and that spot’s number from the Column’s array. We then move that spot into our occupied array. Following this method there can never be any conflicts. When we convert this to code, as we loop over our column’s array, at every step, every combination we can make is valid. So there is no wasted computation, and very little to store. That’s pretty cool.

Rows – []

Columns – []

Occupied – [‘a,1’ : ‘c,3’ : ‘e,2’ : ‘b,4’ : ‘d,5’]

Now it’s time to dive into diagonals. The whole crux of this method is that any point I want to not want to have to store data about every spot, and loop over that data to see if a spot is valid. That just sounds like a lot of wasted time. In keeping with the spirit my above approach to rooks, I tried to figure out if there was a simple way to store diagonals as a whole. I found that if we switch from using letters for rows to numbers, and start at 0, we can do some very simple arithmetic to figure out what diagonal we are at.

I mapped out the diagonals on 2 different images. One that goes from upper-left to lower-right, and one that goes from lower-left to upper-right. We will refer to the first one as the major diagonal, and the second as minor. There isn’t any significance to these names, it’s just convention. It also reminds me of music, so I like it.

Take a moment to look over the images and see if you can put the formula together, and know where we are going next.

If you look at the major diagonal, and you add the row number (r) to the column number (c), your result is the diagonal. Makes a simple sort of sense right? 3+2 = 5 and 1 + 4 = 5, so both of these are on the same major diagonal. You’ll also notice that this is conveniently set up with a 0. So when we store / look up these results we can pass in our result as index, and get our value in constant time. No looping for us!

Minor is the same as major, but instead of adding, we will subtract. Though -4 to 4 isn’t the best range, so we will add 4 (n -1) to that formula. Just to reiterate where we are at:

c + r = major array index

c – r + 4 = minor array index

(I realize now that I have column first instead of array, and for all the earlier examples in the post, I had row first. But the picture is already drawn, so what is done is done. It’s doesn’t change anything, just note we are swapping which comes first now.)

Let’s put it all together, and start from the top. In our open board our values will look something like:

Columns – [0,1,2,3,4]

Rows – [0,1,2,3,4]

Major – [o,o,o,o,o,o,o,o,o]

Minor – [o,o,o,o,o,o,o,o,o]

Occupied – []

To start, I’ll pick ‘0,0’

That means we do a look up of (0+0) in major and (0-0+4) in minor. Both are (o)pen. That means we can place it, and mark those diagonals as crossed (x).

Columns – [1,2,3,4]

Rows – [1,2,3,4]

Major – [x,o,o,o,o,o,o,o,o]

Minor – [o,o,o,o,x,o,o,o,o]

Occupied – [0,0]

If we continue with our computer picking method, the next option is ‘1,1’. Looking at the picture, you and I know that it’s not valid, but let’s see if our algorithm will figure it out. ‘1,1’ is an option, so it’s a valid rook solution. But now that we are doing queens we need to go look up our major/minor arrays. (1 + 1) in major gives us the (o).k. (1-1+4) in the minor, however, (x)’s out and tells us it’s not valid.

Dreams dashed, we pick ourselves up and move on, to ‘2,1’. (2+1) in the major returns us ‘o’. (2-1+4) in minor returns us o as well! it’s a valid spot. Let’s put our next queen there, and forget about ‘1,1’.

Columns – [1,3,4]

Rows – [2,3,4]

Major – [x,o,x,o,o,o,o,o,o]

Minor – [o,o,o,o,x,x,o,o,o]

Occupied – [0,0 : 2,1]

Looking at this, I’m sure you can tell where the remaining 3 have to go, given the choices we’ve made so far. The algorithm will figure it as well.

Is there a better solution out there? Almost definitely. But with this method: we only have to keep track of a small amount of date, we iterate a minimal amount of times, our look ups are in constant time, and at each successive step, we get to sift through less options.

Part 2 to come later, implementation!