a somewhat functional approach to Queens using Python

queens.py

#!/bin/python3

from typing import *
from pymonad import curry


class Square(NamedTuple):
    """
    represents a chessboard square indexed by row and col(short column), using 0-based indexing
    """

    row: int
    col: int


Layout = List[Square]

QueensVisibilityPredicate = Callable[[Square, Square], bool]

sameRow: QueensVisibilityPredicate = lambda x, y: x.row == y.row
sameCol: QueensVisibilityPredicate = lambda x, y: x.col == y.col
sameDiagonal: QueensVisibilityPredicate = lambda x, y: x.col - x.row == y.col - y.row or x.col + x.row == y.col + y.row
visibleAny: QueensVisibilityPredicate = lambda x, y: any(
    map(lambda f: f(x, y), [sameRow, sameCol, sameDiagonal])
)
pickSquare: Callable[
    [Iterable[Square], Layout], Square
] = lambda squares, layout: first_true(squares, None, is_playable(layout))

visible_Diag = """
>>> sq1 = Square(0,5)
>>> sq2 = Square(2,5)
>>> sq4 = Square(3,6)
>>> sq5 = Square(3,4)
>>> print(sameDiagonal(sq1, sq2))
False
>>> print(sameDiagonal(sq4, sq2))
True
>>> print(sameDiagonal(sq5, sq2))
True
>>> print(sameDiagonal(sq5, sq4))
False
"""

visible_Row = """
>>> sq1 = Square(0,5)
>>> sq2 = Square(2,5)
>>> sq3 = Square(2,4)
>>> print(sameRow(sq1, sq2))
False
>>> print(sameRow(sq3, sq2))
True
"""

visible_Col = """
>>> sq1 = Square(0,5)
>>> sq2 = Square(2,5)
>>> sq3 = Square(2,4)
>>> print(sameCol(sq1, sq3))
False
>>> print(sameCol(sq1, sq2))
True
"""

visible_Any = """
>>> sq1 = Square(0,5)
>>> sq2 = Square(2,5)
>>> sq3 = Square(2,4)
>>> sq4 = Square(3,6)
>>> sq5 = Square(3,4)
>>> print(visibleAny(sq1, sq2))
True
>>> print(visibleAny(sq1, sq3))
False
>>> print(visibleAny(sq3, sq2))
True
>>> print(visibleAny(sq4, sq2))
True
>>> print(visibleAny(sq5, sq2))
True
>>> print(visibleAny(sq5, sq4))
True
"""


def show(layout: Layout) -> Any:
    """prints squares of a layout in simplest and primitive format e.g. <(0,0) (1,2)...(7,3)>"""
    formatted_squares = ("({r},{c})".format(r=row, c=col) for (row, col) in layout)
    print(" ".join(formatted_squares))


def first_true(iterable, default=False, predicate=None):
    """Returns the first true value in the iterable.

    If no true value is found, returns *default*

    If *predicate* is not None, returns the first item
    for which predicate(item) is true.

    """
    # first_true([a,b,c], x) --> a or b or c or x
    # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x
    return next(filter(predicate, iterable), default)


@curry
def is_playable(layout: Layout, square: Square) -> bool:
    """Returns true if the candidate square for a new queen is not visible
    with respect to any selected squares(queens) within current layout
    """
    return not (
        first_true(layout, False, lambda existing_sq: visibleAny(square, existing_sq))
    )


def queens(n: int) -> Iterable[Layout]:
    """Returns as many solutions as it can find for a given chessboard size n"""

    def search(layout: Layout, squares: Iterable[Square]) -> Optional[Layout]:
        """identifies an eligible square from provided squares and search forward with it if available
           otherwise backtracks from current layout
        """
        square: Optional[Square] = pickSquare(squares, layout)
        if square:
            return forward(layout + [square])
        else:
            return backtrack(layout)

    def forward(layout: Layout) -> Optional[Layout]:
        """identifies a possible layout from a given partial or full (assumed) consistent layout if there is one,
        None otherwise
        """
        if len(layout) == n:
            return layout
        else:
            squares_on_next_row: Iterable[Square] = (
                Square(len(layout), col) for col in range(n)
            )
            return search(layout, squares_on_next_row)

    def backtrack(layout: Layout) -> Optional[Layout]:
        """removes last square from layout and attempts to make progress
        in identifying a solution(Layout) first by exhausting all columns of the last failed row
        and moving forward when possible or backtrack further when that is not possible.
        When we backtrack fully, i.e nothing left in layout, we return a failed layout (None).
        """
        if layout:
            removed: Square = layout.pop()
            next_squares_on_same_row: Iterable[Square] = (
                removed._replace(col=c) for c in range(removed.col + 1, n)
            )
            return search(layout, next_squares_on_same_row)
        else:
            return None

    previous: Optional[Layout] = []
    while previous is not None:
        # either we have an immediate solution or we explore forward for a next one.
        # In this usage, we explore forward only on first iteration and on next ones
        # we identify immediately as valid. Backtrack can also find the solutions,
        # though it calls forward recursively.
        sol = forward(previous)
        if sol:
            yield sol
            # backtrack effectively continues searching from current position regardless of whether it's broken
            previous = backtrack(sol)
        else:
            break


__test__ = {
    "visible_Row": visible_Row,
    "visible_Col": visible_Col,
    "visible_Diag": visible_Diag,
    "visible_Any": visible_Any,
}


def display_solutions(n: int) -> Any:
    """displays all solutions for a chessboard of dimension n"""
    # Iterable can only be consumed once, this forces something unpleasant to test for empty
    # with additional variable has_none (or a tee)
    queens_solutions_iter = iter(queens(n))
    has_none = True
    while True:
        try:
            solution = next(queens_solutions_iter)
            show(solution)
            has_none = False
        except StopIteration:
            break

    if has_none:
        print("could not find a queens solution for size {d}".format(d=n))


def test():
    import doctest

    doctest.testmod(verbose=1)


if __name__ == "__main__":
    # test()
    display_solutions(5)

added a type declaration for display_solutions