Python solution for the N-Queens challenge 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 &gt; 0 and col &gt; 0:
        rw -= 1
        col -= 1
        chess_board[rw, col] = 0
    # Block L down-diag
    rw = row
    col = column
    while rw &lt; limit - 1 and col &gt; 0:
        rw += 1
        col -= 1
        chess_board[rw, col] = 0
    # Block R up-diag
    rw = row
    col = column
    while rw &gt; 0 and col &lt; limit - 1:
        rw -= 1
        col += 1
        chess_board[rw, col] = 0
    # Block R down-diag
    rw = row
    col = column
    while rw &lt; limit - 1 and col &lt; 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 &lt; 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")
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 &lt;= row &lt; boardsize and 0 &lt;= column &lt; 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")