Python solution for the N-Queens challenge

Question

Here is my coded solution for the N-queens challenge

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

The program outputs all valid chess boards, where the queen is represented by the digit 2.

Are there any improvements that can be made to my code?

One of the main things I want to improve is the counter. I have to make the variable global because I can't work out any other way to do it.

"""Find all possible chess-board combinations of size n*n with n queens,
where queens are represented by the digit 2"""
from collections import Counter
import numpy as np


def block_positions(chess_board, row, column, limit):
    """Fills all squares that can no longer contain a queen with the value -1
    There are a maximum of 8 directions that must be blocked from a given square"""
    # Block left
    for col in range(column - 1, -1, -1):
        chess_board[row, col] = 0
    # Block right
    for col in range(column + 1, limit):
        chess_board[row, col] = 0
    # Block up
    for rw in range(row - 1, -1, -1):
        chess_board[rw, column] = 0
    # Block down
    for rw in range(row + 1, limit):
        chess_board[rw, column] = 0
    # Block L up-diag
    rw = row
    col = column
    while rw > 0 and col > 0:
        rw -= 1
        col -= 1
        chess_board[rw, col] = 0
    # Block L down-diag
    rw = row
    col = column
    while rw < limit - 1 and col > 0:
        rw += 1
        col -= 1
        chess_board[rw, col] = 0
    # Block R up-diag
    rw = row
    col = column
    while rw > 0 and col < limit - 1:
        rw -= 1
        col += 1
        chess_board[rw, col] = 0
    # Block R down-diag
    rw = row
    col = column
    while rw < limit - 1 and col < limit - 1:
        rw += 1
        col += 1
        chess_board[rw, col] = 0
    return chess_board


def initialise_board(num):
    """Build the empty board"""
    board = np.ones(num * num).reshape(num, num)
    return board


def valid_boards(board, row, num):
    """Find all valid N-queen boards"""
    global counter
    while row < num:
        indices = [index for index in range(num) if board[row, index] == 1]
        if indices == []:
            return False
        for index in indices:
            old_board = board.copy()
            board[row, index] = 2
            board = block_positions(board, row, index, num)
            is_possible = valid_boards(board, row + 1, num)
            board = old_board
            if not is_possible and index == indices[-1]:
                return False
    flattened = Counter(board.flatten())
    if flattened[2] == num:
        print(board)
        print()
        counter += 1


if __name__ == "__main__":
    counter = 0
    num = 5
    board = initialise_board(num)
    valid_boards(board, row=0, num=num)
    print(counter, "solutions")
    print("Finished")

Answer 1

One of the main things I want to improve is the counter. I have to make the variable global because I can't work out any other way to do it.

You could declare a global variable, and then increment on it, but that clutters the module namespace. So the idiomatic workaround to avoid declaring a global variable is to point to a mutable object that contains the integer on which you wish to increment so that you're not attempting to reassign the variable name -

def valid_boards(board, row, num):
    #rest of the code
    counter[0] += 1

if __name__ == "__main__":
    counter = [0]
    num = 5
    board = initialise_board(num)
    valid_boards(board, row = 0, num = num)
    print(counter[0], "solutions")
    print("Finished")

OR

Use an attribute on the function. Set a counter attribute on your function manually after creating it -

def valid_boards(board, row, num):
    #rest of the code
    valid_boards.counter += 1

if __name__ == "__main__":
    valid_boards.counter = 0
    num = 5
    board = initialise_board(num)
    valid_boards(board, row = 0, num = num)
    print(valid_boards.counter, "solutions")
    print("Finished")

Hope this helps!

Answer 2

Get classy

In the generation process, you have three things to keep track of: the size of the board, the location of the queens, and the blocked/unblocked status of the individual cells.

This is two things too many.

When you're managing multiple data items, trying to keep them all in sync with each other, that's an indicator you need a class or a separate module. I'll suggest you maintain all this data in a class.

Make it snappy

Next, I'll suggest that you reconsider your storage. Python has a good mechanism for smoothly and transparently scaling the size of integer values. I suggest that you can manage your arrays and positions as integer bitmasks.

How would this work?

First, use generator functions to iterate over everything. Only at dire need will you convert from a bitmask to a position tuple.

Thus, write code that just "assumes" you have whatever it is you want:

for q in board.available_queen_positions():
    new_board = board.with_queen(q)

What is the type of q? I don't know! What is the type of new_board? Presumably the same type as board, but ... I don't know! Maybe it's class Board?

With that approach in mind, now you can make things fast. Let's imaging a 5x5 board. That's 25 cells, which means a 25-bit number. Should be no problem, right? Assume you'll always use the least-significant bits, so 1 << 24 ... 1 << 0 in this case. How you map them is up to you, but I'll suggest 1 << (row * 5 + col). Similarly for unmapping them: row, col = divmod(log2(position), 5)

So a Position(4, 1) would be expressed as 1 << 21.

What does that give you? Well, integers are hashable. So you can perform bitops with them, and lookups in a dict with them.

Iterate over all the available queen positions:

class Board:
    def available_queen_positions(self):
        pos = self.max_pos    # Computed at __init__

        while True:
            if not (pos & self.blocked):
                yield pos
            if pos == 0:
                break
            pos >>= 1

    def cells_blocked_by_pos(self, pos):
        if pos in self.cell_block_cache:
            return self.cell_block_cache[pos]

        # Dicts created at __init__, or make them functions?
        blocks = (self.row_blocks[pos] 
                 | self.col_blocks[pos]
                 | self.right_diag_blocks[pos] 
                 | self.left_diag_blocks[pos])
        self.cell_block_cache[pos] = blocks
        return blocks

You might find that storing positions as integers (such that 4,1 -> 21) is faster than as a bitmask -- that deserves a little timing research. But I expect you'll find that using bitwise operations to perform your blocking will speed things up considerably, and enable you to run with larger board sizes.

Optimize

It's important that you perform timing tests before you start chasing performance. Use timeit, or just print the time before and after your runs - whatever seems appropriate to you. This way you'll be able to avoid going down a non-productive branch. (And the branches which are non-productive will surprise you!)

With that said, one "algorithmic" optimization springs to mind: symmetry. If a particular configuration of queens is valid, then performing various rotations and reflections of that board configuration should also be valid. You should be able to reduce the number of configurations that you check, because of this- you know that if board A is valid then automatically you know that rot90(A) and rot180(A) and rot270(A) are also valid, etc.

Answer 3

Separate generation and presentation

valid_boards both generates the solutions, prints and counts them. Better would be to have 1 method to generate the solutions, another to present the result. The simplest way to do this is to make a generator that yields the solutions, and another method that prints and counts them

reversed

reversed(range(row)) is a lot more clear than range(row - 1, -1, -1)

magical values

you use 0 for blocked, 1 for free and 2 for an occupied tile. defining these as global constants would be a lot clearer

BLOCKED = 0
FREE = 1
OCCUPIED = 2

and then use if for example

chess_board[row, col] = BLOCKED

board size

You use num and limit for the same value, the size of the board. Lat's just call this boardsize

DRY

In block_positions you do a lot of repetition for the different directions to block. More clear would be to use a generator that yields all the neighbour of a tile, and use the coordinates yielded to block those

To do this you need a method to check whether a coordinate is valid:

def valid_coord(coordinate, boardsize=5):
    row, column = coordinate
    return 0 <= row < boardsize and 0 <= column < boardsize

then using itertools.takewhile, functools.partial and itertools.count

def neighbours(row, column, boardsize):
    validator = partial(valid_coord, boardsize=boardsize)
    yield from ((row, i) for i in range(0, column))
    yield from ((row, i) for i in range(column + 1, boardsize))
    yield from ((i, column) for i in range(0, row))
    yield from ((i, column) for i in range(row + 1, boardsize))
    yield from takewhile(validator, ((row - i, column - i) for i in count(1)))
    yield from takewhile(validator, ((row + i, column + i) for i in count(1)))
    yield from takewhile(validator, ((row - i, column + i) for i in count(1)))
    yield from takewhile(validator, ((row + i, column - i) for i in count(1)))

list(neighbours(2, 3, boardsize=5))

[(2, 0), (2, 1), (2, 2), (2, 4), (0, 3), (1, 3), (3, 3), (4, 3), (1, 2), (0, 1), (3, 4), (1, 4), (3, 2), (4, 1)]

Then the block_positions suddenly becomes very simple

def block_positions(chess_board, row, column, boardsize):
    """Fills all squares that can no longer contain a queen with the value -1
    There are a maximum of 8 directions that must be blocked from a given square"""
    for x, y in neighbours(row, column, boardsize):
        chess_board[x, y] = BLOCKED

This method doesn't need to return the board. The standard library's convention is that if a method changes the object, it doesn't return something. If it returns a new object, that is returned.

By just changing the neighbours, you can easily change this to find the solutions for [related puzzles(https://en.wikipedia.org/wiki/Eight_queens_puzzle#Related_problems)

numpy

You hardly use any of the numpy strengts, but even then this can be simpler You can pass a tuple to np.one, so initialise_board can be as simple as

def initialise_board(num):
    """Build the empty board"""
    return  np.ones((num, num)) * FREE

Counting the number of places queens can be simpler too: (board == OCCUPIED).sum() == num instead of np.flatten and Counter

generator

Now the valid_boards method both generates the solutions, prints them and augments the counter. Simpler would be to have them just generate the solutions, and have something else take care of the printing and counting.

Slightly adapting your algorithm to a generator approach:

def add_queen(board, row, boardsize):
    if row == boardsize:
        yield board
        return
    free_columns = (index for index in range(boardsize) if board[row, index] == FREE)
    for column in free_columns:
        new_board = board.copy()
        new_board[row, column] = OCCUPIED
        block_positions(new_board, row, column, boardsize)
        yield from add_queen(new_board, row + 1, boardsize)

and call it like this:

if __name__ == "__main__":
    boardsize = 5
    board = initialise_board(boardsize)
    for solution_count, solution in enumerate(
        add_queen(board, row=0, boardsize=boardsize), 1
    ):
        print(solution)
        print()
    print(f"{solution_count} solutions")