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
When you need to do
for i in range(stop):
value = seq[i]
# do stuff
you should use
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.,
When you want to initialise a list with the same immutable object, you can do
[value] * n
[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:
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.
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.
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:
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.
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:
restrictions = set()
for rank, square in enumerate(queen_coords[:current_rank]):
diff = current_rank - rank
left_diagonal = square - diff
right_diagonal = square + diff
if left_diagonal >= 0:
if right_diagonal < size:
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:
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):
for solution in solve_queens_puzzle(8):