# N queens variation recursion Python 3

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

def remove_queen(self, r, 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
"""

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

• 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)? – vnp Oct 8 '17 at 1:44
• @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. – bolmgren Oct 8 '17 at 12:18

• 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