Eight queens solver (single solution). Adapted from Wirth's pseudo-Algol 60 algorithm presented in *Program Development by Stepwise Refinement*. http://oberoncore.ru/_media/library/wirth_program_development_by_stepwise_refinement2.pdf

eight_queens.py

"""Eight queens solver (single solution)

Adapted from Wirth's pseudo-Algol 60 algorithm presented in *Program
Development by Stepwise Refinement*.

http://oberoncore.ru/_media/library/wirth_program_development_by_stepwise_refinement2.pdf

"""


class Board(object):
    """Simplistic representation of a chessboard for solving eight queens.

    The paper represents the board as a one-dimensional array, where the index
    corresponds to the column of the board and the value represents the row in
    that column containing a queen. For convenience, I'm using -1 to mean no
    queen is in the column.

    forward_diagonal (/) and back_diagonal (\) indicate if a queen is present
    on the corresponding diagonals for a given square, following the paper's
    observation that squares on the same forward diagonal have the same
    coordinate sum and those on the same back diagonal have the same
    coordinate difference.

    """

    def __init__(self):
        self.board = [-1] * 8
        self.forward_diagonal = set()
        self.back_diagonal = set()

    def set_queen(self, row, column):
        """Place a Queen on the board at the specified location.

        No error checking is performed; if the Queen is already placed at the
        specified coordinates, this method has no effect.

        """

        self.board[column] = row
        self.forward_diagonal.add(column + row)
        self.back_diagonal.add(column - row)

    def remove_queen(self, column):
        """Remove the Queen in the specified column from the board.

        Returns the row of the removed Queen.

        If no Queen was present in the column, returns -1.

        """

        row = self.board[column]
        self.board[column] = -1
        self.forward_diagonal.discard(column + row)
        self.back_diagonal.discard(column - row)
        return row

    def test_square(self, row, column):
        """Determine if a given square is safe for Queen placement.

        A square is considered safe if there is no Queen elsewhere on the board
        in the same row, column, or diagonals as the given square.

        Since Wirth's algorithm works by placing a single Queen in each column,
        the column is assumed to be empty and no check is performed.

        """

        return row not in self.board and \
            column + row not in self.forward_diagonal and \
            column - row not in self.back_diagonal

    def __unicode__(self):
        def generate():
            yield ' _______________________________ \n'
            for row in range(8):
                yield '|   |   |   |   |   |   |   |   |\n|'
                for column in range(8):
                    yield ' Q |' if self.board[column] == row else '   |'

                yield '\n|___|___|___|___|___|___|___|___|\n'

        return ''.join(generate())

    def __repr__(self):
        return self.__unicode__()


def solve():
    board = Board()
    row = column = 0

    while 0 <= column <= 7:
        for row in range(row, 8):
            if board.test_square(row, column):
                board.set_queen(row, column)
                column += 1
                row = 0
                break
        else:
            # regress: backtrack to the previous column and continue advancing
            # its queen
            column -= 1
            row = board.remove_queen(column) + 1

    return board


if __name__ == '__main__':
    print(solve())