CodeFights Solves It: chessQueen

Our latest Interview Practice Task of the Week was chessQueen, which has been asked in technical interviews at Adobe. This question might seem fairly easy at first: Given the location of a queen piece on a standard 8 × 8 chess board, which spaces would be safe from being attacked by the queen? But as with any "easy" technical interview question, it's imperative that you think it through fully, watch out for potential traps, and be able to explain your reasoning as you solve it!

This question is a variation on a classic problem, Eight Queens. It’s very possible that you’ve encountered Eight Queens or a common variation, nQueens, in computer science classes or interviews in the past. Chess-based problems like this one come up a lot in interviews, there’s a good reason for that! If you think about a chess board, what does it look like? A grid. And chess pieces follow specific rules, making chess scenarios a great framework for questions that test your basic problem-solving and implementation skills.

If you haven’t solved chessQueen yet, now’s the time! Once you’ve written your own solution, head back here. I’ll discuss my solution, and why I chose it over other possible solutions to the problem.

Ready? Great, let’s get started!

The technical interview problem

chessQueen gives us the location of the queen in standard chess notation (e.g. “d4”). Our solution needs to return a list of all the locations on the board that are safe from the queen. The diagram below shows the locations that the queen could move to on her next move, which means that these cells are not safe from the queen.

Queen at D4

In this example, we’d need to have our function chessQueen("d4") return the following list:

chessQueen("d4") =
["a2","a3","a5","a6","a8",
 "b1","b3","b5","b7","b8",
 "c1","c2","c6","c7","c8",
 "e1","e2","e6","e7","e8",
 "f1","f3","f5","f7","f8",
 "g2","g3","g5","g6","g8",
 "h1","h2","h3","h5","h6","h7"]

Keep in mind that the output above has been formatted nicely to help us visualize the solution when looking at the diagram. The native output would put line breaks at locations dictated by the size the window.

What can the queen attack?

Remember that in chess, a queen can move any number of squares vertically, horizontally, or diagonally.

The rows are already numbered, so let’s number the columns as well. Internally, we can think of column A as ‘0’, column B as ‘1’, etc. We will call the queen’s location (qx,qy). Then the queen can take any location (x,y) that is:

1. Anything in the same row (i.e. qy == y)
2. Anything in the same column (i.e. qx == x)
3. Anything on the up-and-right diagonal from the queen’s location. (i.e. slope 1 lines though the queen's location: qx - qy == x - y)
4. Anything on the down-and right diagonal from the queen’s location. (i.e. slope -1 lines though the queen's location: qx + qy == x + y)

Any other location on the board is safe from the queen.

Our strategy

We see that we have to report and return all the squares that are safe from the queen for our solution. If we think of the chess board as N × N, we see that there are N squares excluded from the row, N excluded from the column, and at most N excluded from each of the diagonals. We are expected to return O(N^2) elements, so we know that we aren't going to find a solution shorter than O(N^2).

The creative parts of this solution will be how you choose to map between the column letters and the numbers — basically, how you do the arithmetic! My choice below was to use the hard-coded string "abcdefgh", where the position in the string maps to the index. I'll mention some alternatives below, as well as their advantages and disadvantages.

def chessQueen(q_loc):
    cols = list("abcdefgh")
    rows = range(1,9)

    # get the [numerical] location of the queen
    qx,qy = cols.index(q_loc[0]), int(q_loc[1])

    # remove the row that the queen is in
    #(none of those locations are safe)
    rows.remove(qy)

    # place to put "safe" squares
    safe = []

    # note that I want to maintain correspondence
    # between location in cols, and the column number.
    # If I remove an entry in cols, I eliminate this
    # correspondence!

    for colnum, colname in enumerate(cols):
        if colnum == qx:
            continue # don't bother with this column
        for row in rows:
            # we don't have to check row or column (the queen's row
            # was removed, and we skip this loop on the queen's col)
            if (qx + qy != colnum + row) and (qx - qy != colnum - row):
                safe.append( colname + str(row) )

    return safe

Other approaches to this coding challenge

My approach to translating between the column’s names and the numbers won’t be everyone’s favorite way. My approach to listing the elements isn’t elegant, but it gets the job done! And a lot of times, that’s exactly that an interviewer needs to see.

Here are some alternatives, and why I didn’t choose them:

• Using the built-in string library
  We can get rid of the hardcoded string by writing

cols = list(string.lowercase[:8])

You have to be a little careful that people running different locales will still have the same “first 8 characters” that you have! Note that you can use cols = list(string.ascii_lowercase[:8]) instead to be safe, but at that point I'd rather be explicit about the letters I'm using.

• Using “ASCII math”
  We can find the column numbers by subtracting the character code a from the letter. In Python, ord('a') will return the code for the letter 'a' (97 in ASCII). In C, the function casting the character to an integer does the same thing. So we can actually write code that is a lot smaller:

# using character codes, instead of a list to with indices
def chessQueen(q_loc):
    cols, rows = range(8), range(1,9)

    qx,qy = ord(q_loc[0]) - ord('a'), int(q_loc[1])

    # remove the queen's row and column
    cols.remove(qx)
    rows.remove(qy)

    safe = []

    for col in cols:
        for row in rows:
            # check that we are not on the dangerous diagonals
            if (col - row != qx - qy) and (col + row != qx + qy):
                safe.append( chr(col + ord('a')) + str(row) )
    return safe

Because we aren’t relying on the position in the list, and have a direct translation between the column letters and numbers, we’re able to remove the column directly, instead of having to use the continue keyword. I avoided this because I get nervous doing encoding math (what about the locales?!) but the Python documentation assures me I'd actually be fine!

• Using a dictionary for the conversion
  If I wanted to be fully explicit, I could make a dictionary {'a':0,'b':1, ..., 'h':7} to encode the values, and a separate dictionary to decode. This is a very flexible approach, but I would worry about what my interviewer might read into me setting up two hash tables for something that really only needed a little arithmetic! This is probably the easiest version to internationalize, so if you have a technical interview at a company that works in many different character sets, you could use this flexible code as a selling point. ("Oh, you want the names of the columns in Chinese? No problem, I just have to change the keys in this dictionary...")

Ready to tackle some other Adobe interview questions?

Now that you’ve solved chessQueen, try some of the other Adobe questions that we’ve got in Interview Practice! I suggest trying:

• equilibriumPoint
• classifyStrings
• graphDistances
• numberOf1Bits

(Once you’ve finished those Adobe challenges, don’t worry — we’ve got more!)

Tell us…

As you’ve seen, this is a challenge that can be solved in a number of different ways! How did you tackle it? How would you describe your reasoning for taking that approach to an interviewer? Let us know over on the CodeFights forum!

This article was originally posted on CodeFight On!, the official blog of CodeFights.

See what else we’re up to by following us on Twitter and Facebook!