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