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