queens-recursive.py

def queens(n):
    queens_helper([], 1, n)

def queens_helper(occupied, col_to_test, n):
    if len(occupied) == n:
        print occupied
    else:

        # attempt to place queen
        if is_free(col_to_test, occupied):
            occupied.append(col_to_test)
            queens_helper(occupied, 1, n)

        # no space available
        else:
            next_col = col_to_test + 1

            # try next space in same row
            if next_col <= n:
                queens_helper(occupied, next_col, n)

            # backtrack to previous row
            else:
                occupied, next_col = backtrack(occupied, n)
                queens_helper(occupied, next_col, n)


def is_free(col_to_test, occupied):
    if col_to_test in occupied:
        return False
    else:
        return safe_diagonals(col_to_test, occupied)


def safe_diagonals(space, occupied):
    for i in range(0, len(occupied)):
        j = len(occupied) - i
        if (occupied[i] == (space + j)) \
            or (occupied[i] == (space - j)):
            return False
    return True


def backtrack(occupied, n):
    last_col_tried = n

    while last_col_tried >= n:
        occupied, last_col_tried = \
            back_one_step(occupied, last_col_tried)

    next_col = last_col_tried + 1
    return occupied, next_col


def back_one_step(occupied, last_col_tried):
    if occupied is not []:
        last_col_tried = occupied[-1]
        occupied.pop()
    return occupied, last_col_tried

queens(4)