5
\$\begingroup\$

Write an algorithm to print all valid ways of arranging eight queens on an 8x8 chess board so that none of them attack any other.

Following is my code for this. Do you see any performance or coding style issue with it? How should I have used grid_size? It should not be a parameter to a function that is already called "eight queen". But global also doesn't feel quite right. I would also like suggestions on naming variables and methods.

def is_valid (proposed_row, proposed_col, already_placed_queen_cols):
    for earlier_row in range(0,proposed_row):
        already_placed_queen_col = already_placed_queen_cols[earlier_row]

        if proposed_col == already_placed_queen_col:
            return False

        column_dist = abs(proposed_col - already_placed_queen_col)
        row_dist = proposed_row - earlier_row

        if column_dist == row_dist:
            return False

    return True


def get_arrangements (row, already_placed_queen_cols, grid_size):
    if row == grid_size:
        yield already_placed_queen_cols
        return

    for col in range(0,grid_size):
        if is_valid(row,col, already_placed_queen_cols):
            already_placed_queen_cols[row] = col 
            yield from get_arrangements (row+1, already_placed_queen_cols, grid_size)

def eight_queen():
    global grid_size
    already_placed_queen_cols = [-1 for i in range(0,grid_size)]    
    return get_arrangements (0, already_placed_queen_cols, grid_size)

grid_size = 8
arrangements = eight_queen()

for arrangement in arrangements:
    position_list = []
    for row in range(0,grid_size):
        position_list.append((row, arrangement[row]))
    print (position_list)
\$\endgroup\$
2
\$\begingroup\$

Coding style

Don't put a space between a function name and the opening bracket for its parameters. You should also consistently have a space after the comma between parameters in a function, iterable, etc. So, that should have been range(0, stop). Incidentally, if your starting value is 0, you can simply use range(stop).

When you need to do

for i in range(stop):
    value = seq[i]
    # do stuff

you should use enumerate().

for i, value in enumerate(seq):
    # do stuff

Obviously you can also enumerate only a part of your iterable and if the starting index isn't 0, you can specify that as well, i.e., enumerate(seq[start:stop], start).

When you want to initialise a list with the same immutable object, you can do

[value] * n

instead of

[value for i in range(stop)]

Care must be taken here, because if you tried to do [[]] * n, you would create n references of the same empty list and when it is modified, it changes for each index in your list. In such a case, you would have to fall back to initialising your iterable the way you did it. Also, while it's a matter of preference, I find it more natural to initialise the queen positions to None than some arbitrary value.

Your main function is simply a wrapper for get_arrangements(), where you simply initialise some objects. You can make get_arrangements() your main function and simply check whether you're currently at row 0 so you can initialise said objects.

def eight_queen(grid_size, row=0, already_placed_queen_cols=None):
    if not row:
        already_placed_queen_cols = [None] * grid_size

    if row == grid_size:
        yield already_placed_queen_cols
    # ...

This way you also solve the problem of the global variable, which is indeed ugly. I don't understand why it shouldn't be a parameter of your main function. The say I see it, I'm tasked with finding the solution to the n-queens puzzle, so the one thing I need to define is the board size. If I'm only interested in the solution for size 8, I can give it a default value in the parameters, so to call the function with no inputs, but that still allows me to generalise the solution should I feel like it later on.

The is_valid() function is only supposed to be called by your main function, and someone has no use for it unless he can replicate an intermediate state of its input parameters. As such, you can add a leading underscore to its name to indicate the user has no interest in calling it directly.

Naming style

I would call the main function solve_queens_puzzle() as that's what you're doing.

is_valid() correctly describes that it returns a boolean, but it's somewhat vague about the validity of what it tests. is_valid_placement() should suffice.

already_placed_queen_cols does feel a bit awkward indeed. queens_coords sounds equally descriptive and less verbose. Following on that, already_placed_queen_col is deceptive for having only a letter different in such a long name. I wouldn't complicate things here, from a glance at the code it's obvious the rows/columns iterated are up to proposed_row. I would simplify that to

for row, col in enumerate(queen_coords[:proposed_row]):
    if col == proposed_col:
        return False
    # ...

This one is entirely subjective, but you can either stick with a row/column convention, since mathematically speaking you're dealing with a 2D array, or you can use rank/file, which are the respective chess terms.

Performance

In the context of the backtracking algorithm you've implemented, there is one inefficiency. For each new row, you iterate over all 8 squares and check whether there are any conflicts. However, you repeat a lot of the same computations for each square, e.g., the proposed row against all the earlier rows, etc. Instead, you should go over the earlier rows once, while calculating any restrictions for the current row along the way. Specifically, for the current row you can't use the column of any previous row, or the diagonals that result from them. That way in one pass you can collect the available squares and return that from the function for iteration. This yields an exponential improvement for grid sizes over 10, when the solutions aren't computed almost instantly. Obviously, this changes the intent of the function, so its naming has to follow accordingly.

Overall, this is what I got.

def _get_possible_squares(size, current_rank, queen_coords):
    # no restrictions for the first row
    if not current_rank:
        return range(size)

    restrictions = set()
    for rank, square in enumerate(queen_coords[:current_rank]):
        restrictions.add(square)
        diff = current_rank - rank
        left_diagonal = square - diff
        right_diagonal = square + diff
        if left_diagonal >= 0:
            restrictions.add(left_diagonal)
        if right_diagonal < size:
            restrictions.add(right_diagonal)
    return (square for square in range(size) if square not in restrictions)

def solve_queens_puzzle(size, rank=0, queen_coords=None):
    if not rank:
        queen_coords = [None] * size

    if rank == size:
        yield tuple(queen_coords)
        return

    for square in _get_possible_squares(size, rank, queen_coords):
        queen_coords[rank] = square
        for solution in solve_queens_puzzle(size, rank+1, queen_coords):
            yield solution


for solution in solve_queens_puzzle(8):
    print(solution)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.