N Queens in Python using backtracking

Question

I write this solution to the popular N Queens problem using backtracking algorithm. I am relatively new to Python. I would like to know what are the ways to refactor this code and also code style of Python in general.

def isSafe (board, row, col):
 # check left row
 for y in range(col):
 if board[row][y] == 1:
 return False
 # check diagonal left top
 for x, y in zip(range(row, -1, -1), range(col, -1, -1)):
 if board[x][y] == 1:
 return False
 # check diagonal left bottom
 for x, y in zip(range(row, N, 1), range(col, -1, -1)):
 if board[x][y] == 1:
 return False
 return True
def generateSolution(board, col):
 # terminating condition
 # all columns covered
 global N
 if col >= N:
 return True
 # loop over all the rows
 for i in range(N):
 if isSafe(board, i, col) == True:
 board[i][col] = 1
 # recursively place other queens
 if generateSolution(board, col + 1) == True:
 return True
 # unmark queen spot
 board[i][col] = 0
 # backtrack
 return False
N = int(input())
startCol = 0
board = [[0 for i in range(N)] for j in range(N)]
# print(board)
if generateSolution(board, startCol) == False:
 print("No Solution Exists")
else:
 print("Solution exists")
 print(board)

Answer 1

PEP 8

There is a generally accepted style for Python known as PEP 8. Most notably camelCase functions/methods should become snake_case. There are some other issues with stylistic conventions, I would give the document I linked to an overview.

Main Function

I would advise you add a main function to your program. The main reason being: If I want to use the functions from your script, when I import your script I probably don't want to actually run your program, just use generateSolution and isSafe. So:

N = int(input())
startCol = 0
board = [[0 for i in range(N)] for j in range(N)]
# print(board)
if generateSolution(board, startCol) == False:
 print("No Solution Exists")
else:
 print("Solution exists")
 print(board)

Becomes:

def main():
 N = int(input())
 startCol = 0
 board = [[0 for i in range(N)] for j in range(N)]
 if generateSolution(board, startCol) == False:
 print("No Solution Exists")
 else:
 print("Solution exists")
 print(board)
if __name__ == '__main__':
 main()

Avoid global

You should almost always not use the global keyword. In this case: just pass N into your generateSolution function, i.e. generate_solution(board, col, N).

Naming

I am not entirely sure how your code works (I am, ashamedly, unfamiliar with the N-Queen problem). I assume N refers to the number of queens? I would recommend that you call it queen_count or something of the sort. In addition, generate_solution is rather unspecific. I would call it (possibly) n_queen_solvable.

Does generate_solution actually do that?

I mentioned changing it to the name n_queen_solvable because you have return a truth value. I would expect a function like that to actually give me a configuration, not answer whether a solution exists or not. You may want to refactor this into two functions: n_queen_solvable and gen_queen_config or something of the sort.

Default parameters

You seem to want to start at the zeroith column. Makes sense. Instead of explicitly passing the startCol explicitly, I would just make col default to 0. This is done by changing:

def generateSolution(board, col):

to

def generateSolution(board, col=0):

• John B: There’s also the generate special meaning given Python’s generator objects, yet the method is not yielding anything.

Answer 2

+1 to @Dair's suggestions. Also, your isSafe (which should be called is_safe - snake_case is standard in Python) can be simplified, although I'm a little shaky on what you're trying to accomplish with your logic.

First, I'll suggest that you rename your arguments to row_index and col_index.

I had started re-writing your for loops as list comprehensions using any (which you should still do), but I ran into some questionable logic.

You say "check left row", by which I think you actually mean "check the left-hand side of the row containing (row_index, col_index)". If that's true, why are you iterating with y? Isn't that x?

Answer 3

@Dair's answer is good, but there was something else that hasn't been mentioned:

Don't compare to Boolean values

• Instead of if foo == True, write if foo
• Instead of if foo == False, write if not foo

Comparing to Boolean values is always unnecessary because the values will already be coerced into Boolean values in the appropriate contexts. While the Zen of Python does say "Explicit is better than implicit", Boolean comparison looks like nonstandard Python code, and is a bit of a code smell for me.