News for hackers. Stuff that matters.
Re:Programming Interview Question: Eight Queens by yetanotherphd on Tuesday December 31, 2013 @03:45PM (#6992735)
I did this in about 20 minutes in Python in an interview.

The trick to solving things fast is to use the structure of the problem to make your problem solving procedure less general. That is, you do premature optimization, except instead of trading readability for runtime speed, your are trading readability for program length.

With real problems, there is a similar tradeoff, so I think this is a useful skill to demonstrate. But it does take practice to find the tradeoff that works best for interview questions, which is not the same as for real life coding.

In my solution, I use mutable state to reduce the amount of code. board is mutated to avoid the boilerplate of copying objects. valid is mutated as a kind of optimization, but the real reason is it makes the program simpler.

  def complete_board(board, l):
    """If possible, completes a board (whose first l rows
    have been filled with 1 queen per row).  Returns
    true if this is possible, false otherwise

    board is a list of ints representing the position
    (0-based) of each queen"""

    N = len(board)

    if l == N:
      return True

    # determine the valid positions for a queen in the r'th row
    valid = [True] * N
    for row, col in enumerate(board[:l]):
      valid[col] = False
      s = l - row
      if col + s < N:
        valid[col + s] = False
      if col - s >= 0:
        valid[col - s] = False

    for col, v in enumerate(valid):
      if v:
        board[l] = col
        if complete_board(board, l + 1):
          return True
    return False

There are no comments on this comment yet.