N queens variation recursion Python 3

Question

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) squares of the board. A queen cannot be placed at a square with a hole, but can still attack "over" a hole.

I believe to have solved the problem at a conceptual level, but there is a time constraint that I have yet to fulfil. To my understanding there is no algorithm that has a lower time complexity than backtracking for N<8, so that is what I have done. I wonder if there is something in my code that seems to demand excessive operations?

The input is handled separately and creates an instance of a board of size N with the appropriate set holes and the rest of the init sets as empty.

Any sort of pointer would be greatly appreciated!

class Board:
    """
    The main class, a chess board of size (size) from __init__.
    An instance:
        Stores the chess board in self.rows
        Modifies the chess board by placing holes or queens
        Checks if a square is safe to place a queen in (i.e. not on a hole or being attacked by another queen)
        Solves the holey-n-queens problem recursively with solve.
    """
    def __init__(self, size):
        self.size = size
        self.holes = set()
        self.bad_columns = set()
        self.right_diagonal = set()
        self.left_diagonal = set()
        self.solutions = 0

    def place_queen(self, r, c):
        """
        Adds the column of the queen in self.bad_columns, and the conditions for right and left diagonal.
        :param r: row
        :param c: column
        :return: Nothing
        """
        self.bad_columns.add(c)
        self.right_diagonal.add(r-c)
        self.left_diagonal.add(r+c)

    def remove_queen(self, r, c):
        self.bad_columns.remove(c)
        self.right_diagonal.remove(r-c)
        self.left_diagonal.remove(r+c)

    def place_hole(self, r, c):
        """
        Places a hole in self.holes as a tuple (r, c)
        :param r: row
        :param c: column
        :return: nothing, modifies the class instance's set self.holes
        """
        self.holes.add((r, c))

    def is_safe(self, r, c):
        """
        Checks if the square (r, c) is safe to place 
        :param r: row
        :param c: column
        :return: True if safe, False if not
        """
        # Given two cells (i1, j1) and (i2, j2) , you can say they are on the same diagonal if | i1 - i2 | = | j1 - j2 |

        # The diagonals can be also saved on two boolean one dimensional array / matrix and accessed with x - y and
        #  x + y numbers (where x is the number of the row / column of the queen and y is the number of the line).
        # The upper left queen has x = 1 and y = 1 and the lower right queen has x = N and y = N for a table size of N).
        # The diagonals accessed with x - y are those with positive slope whereas x + y accessed the negative slope
        # diagonals

        if r-c in self.right_diagonal or r+c in self.left_diagonal or c in self.bad_columns or (r, c) in self.holes:
            return False
        return True

    def solve(self, row):
        """
        Recursively solves the problem by backtracking
        :param row: The current row where we are trying to place a queen
        :return: Nothing, but increments the self.solutions integer for every solution
        """

        # Base case for the function.
        if row >= self.size:
            return

        for i in range(self.size):  # Iterate over all the columns in row (row) and tries to place it.
            if self.is_safe(row, i):  # Self explanatory
                self.place_queen(row, i)  # Self explanatory
                if row == self.size - 1:  # Check to see if we are on the last row, if so we have a solution!
                    self.solutions += 1  # Increment number of solutions for this particular board
                    self.remove_queen(row, i)
                    continue  # Continue iteration, are there any more solutions for the same board?
                # This runs if we are not in the last row
                self.solve(row + 1)  # We know that we are able to place a queen at row (row), thus we go on to next one
                # Backtracks
                self.remove_queen(row, i)

Inspiration for the solve function has been taken from here: ploggingdev[dot]com/2016/11/n-queens-solver-in-python-3/.

Answer 1

• Speedwise it is better to keep track of free columns instead of occupied ones. Then you don't need to check if a column is free as you can iterate directly over the free columns in solve.
• You can simplify solve by taking advantage of the base case of recursion and remove the if from inside the loop.
• It would be clearer to return a value from solve instead of modifying self.solutions.

Revised:

def solve(self, row=0):
    # Base case
    if row >= self.size:
        return 1

    solutions = 0
    for i in list(self.free_columns): 
        if self.is_safe(row, i):  
            self.place_queen(row, i)  
            solutions += self.solve(row + 1)  
            self.remove_queen(row, i)
    return solutions