5
\$\begingroup\$

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/.

\$\endgroup\$
  • 2
    \$\begingroup\$ Unclear, what the hole means (as if you can't place a queen in the hole, or does the hole shadow queen's action, or both, or none of the above)? \$\endgroup\$ – vnp Oct 8 '17 at 1:44
  • \$\begingroup\$ @vnp My mistake, thank you for pointing this out. A queen cannot be placed at a square with a hole, but can still attack "over" a hole. \$\endgroup\$ – bolmgren Oct 8 '17 at 12:18
1
\$\begingroup\$
  • 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        
\$\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.