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)

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.

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