Eight Queens Puzzle

A solution to the Eight Queens Puzzle.

Solution

""" eight_queens.py """

# usage: python3 eight_queens.py 8

import sys


def valid(p, n, data):
    """ placing a queen at p is valid for n x n board with data """
    row, col = divmod(p, n)

    # (*) not required if advancing to start of next row after placing queen
    # if 'Q' in data[p - col:p]:
    #     return False

    if 'Q' in [data[p - (i + 1) * size] for i in range(row)]:
        return False

    r, c = row, col
    while r > 0 and c > 0:
        r, c = r - 1, c - 1
        if data[r * n + c] == 'Q':
            return False

    r, c = row, col
    while r > 0 and c < n - 1:
        r, c = r - 1, c + 1
        if data[r * n + c] == 'Q':
            return False

    return True


def display(n, data):
    """ visualise n x n board with data """
    output = ''
    for i in range(n):
        output += ' '.join(data[i * n:(i + 1) * n] + ['\n'])
    return output


size = int(sys.argv[1])
assert size > 0

board = ['.' for _ in range(size * size)]

positions = []
pos = 0

count = 0
complete = False
while not complete:
    if valid(pos, size, board):
        board[pos] = 'Q'
        positions.append(pos)
        if positions[0] >= size:
            complete = True
        elif len(positions) == size:
            count += 1
            # print(display(size, board))
        else:
            pos = (pos // size + 1) * size  # (*) advance to start of next row
    else:
        pos += 1
    while pos == size * size:
        if positions:
            pos = positions.pop()
            board[pos] = '.'
            pos += 1
        else:
            complete = True
            pos = -1

print(count)