N Queens in Python

Question

I used Python very occasionally, today I solved n queens in Python just for fun. I am sure there are better way of doing certain things in Python and can't wait for improvement suggestions!

#!/usr/bin/python3
def print_board(board):
 for row in board:
 for field in row:
 print('Q ', end='') if field else print('X ', end='')
 print()
 print()
def can_place_queen(board, row, col):
 for field in board[row]:
 if field: return False
 for i in range(len(board[0])):
 if board[i][col]: return False
 i, j = row, col
 l = len(board)
 while i < l and j < l:
 if board[i][j]: return False
 i, j = i + 1, j + 1
 i, j = row, col
 while i < l and j >= 0:
 if board[i][j]: return False
 i, j = i + 1, j - 1
 i, j = row, col
 while i >= 0 and j < l:
 if board[i][j]: return False
 i, j = i - 1, j + 1
 i, j = row, col
 while i >= 0 and j >= 0:
 if board[i][j]: return False
 i, j = i - 1, j - 1
 return True
def place_queens(board, row=0):
 global nSolutions
 if row >= len(board):
 print_board(board)
 nSolutions += 1
 return
 for col, field in enumerate(board):
 if can_place_queen(board, row, col):
 board[row][col] = True
 place_queens(board, row + 1)
 board[row][col] = False
nSolutions = 0
# Note that [[False]*8]*8 does not work since * will just copy the address
# of the row!
board = [[False] * 8 for i in range(8)]
place_queens(board)
print("Found %s solutions!" % nSolutions)

• Vogel612: I have rolled back the last edit to avoid confusing readers of the question with two different versions of the same code. Please see what you may and may not do after receiving answers .

Answer 1

One option that might help speed things up would be to include a bit of redundant metadata with your board. Rather than just representing an array of 8*8 Booleans representing whether a Queen is in play on a given cell, you could also have 8 Boolean arrays indicating whether a Queen is in play anywhere on a given row, column, or diagonal. That would make it marginally more complicated to actually play the piece, but considerably easier to check whether a move is legal.

Especially if you were looking to have a more complex representation of a board state, it would probably be worthwhile encapsulating it into a class.

---

A second area that is worth thinking about exploiting symmetry. If you have found one solution, that layout reflected vertically, reflected horizontally, or rotated this way or that will also be a valid solution. It takes a little bit of care to confirm that it's a distinct solution, but avoiding even checking the majority of board positions because you've already checked reflections or rotations is a big win.

---

One of the many elegant tricks that Python provides is list comprehensions, for manipulating whole lists at once. For example, to convert a list row of booleans into a list of "Q" and "X" you can use this.

["Q" if i else "X" for i in row]

This means that your inner loop in print_board can be written

print("".join(["Q" if i else "X" for i in row]))

---

Another handy trick for avoiding explicit loops is the any and all reduction functions. These take a collection of Booleans (or things that can be converted to Boolean) and returns True if any or all respectively are True.

For example (ignoring my first suggestion) the first check in can_place_queen can be changed from

for field in board[row]:
 if field: return False

to

if any(board[row]): return False

However writing the other checks quite so succinctly would not work as well.

---

Finally, the conventional way of writing a script to run on its own is

def main():
 nSolutions = 0
 # Note that [[False]*8]*8 does not work since * will just copy the address
 # of the row!
 board = [[False] * 8 for i in range(8)]
 place_queens(board)
 print("Found %s solutions!" % nSolutions)
if __name__ == "__main__": main()

The primary purpose of this is so that if someone imports the python file as a module, they don't get the results of running the script.

• Nils: Thanks for such an elaborate answer! I was not aware that any and all are available as free standing functions.
• Maarten Fabré: no need for the brackets in print("".join(["Q" if i else "X" for i in row])). Join can accept a generator expression

Answer 2

I would suggest either commenting each of your check loops, to explain which check they're doing ("Checking diagonal to bottom right for queens") or perhaps putting each of these sub checks in a function of their own.

It is also possible that you are able to do both the bottom-right and top-left strides in a single loop, or even abstract all of the searches into a single function which takes strides, since there is a lot of code duplication there:

def diagonal_search(row, col, board, x_stride, y_stride):
 i, j = row, col
 l = len(board)
 while i < l and i >= 0 and j < l and j >= 0:
 if board[i][j]: return False
 i, j = i + x_stride, j + y_stride
 return True

and use it as:

# Search the row
if not diagonal_search(row, col, board, 1, 0):
 return False
# Search the column
if not diagonal_search(row, col, board, 0, 1):
 return False
# Search the right-down diagonal
if not diagonal_search(row, col, board, 1, 1):
 return False

etc..

• Nils: Thx! I like the idea of a generalized diagonal_search(...) function :-)
• Nils: Although the first two examples are not exactly a diagonal search.