# Principled Programming / Tim Teitelbaum / Chapter 16.
def eight_queens() -> None:
        """Solve the Eight Queens problem."""
    # R[c] is r if Queen in ⟨r,c⟩.*/
        R: list[int] = [ 0, 1, 2, 3, 4, 5, 6, 7 ]
    # Consider each permutation of R until one is found that represents a
    #   solution. (At least one such permutation is known to exist.)
        while has_same_diagonal(R): next_permutation(R)
    # Output solution R.
        printBoard(R)

def has_same_diagonal( r: list[int] ) -> bool:
        """Return True iff R has two Queens on same diagonal."""
    # PosDiag[k] (resp., NegDiag[k]) True iff a Queen in R[0..c] occurs on the
    #   positive (resp., negative) diagonal with index k.
        PosDiag: list[bool] = [False] * 15
        NegDiag: list[bool] = [False] * 15
    #
        c: int = 0
        while c < 8 and not(PosDiag[r[c] + c]) and not(NegDiag[c - r[c] + 7]):
            PosDiag[r[c] + c] = True; NegDiag[c - r[c] + 7] = True
            c += 1
        return c != 8

def next_permutation(a: list[int]) -> None:
        """
        Update R[0..7] to be the next permutation of 1,2,3,4,5,6,7,8
        in a cycle of all 8! such permutations.
        """
    #
        n = len(a)
    # Set j so that A[j+1..n-1] is the longest descending suffix of A.
        j = n - 2
        while (j >= 0) and a[j] >= a[j + 1]: j -= 1
    #
        if j >= 0:
            # Set k so A[k] is smallest value in A[j+1..n-1] larger than A[j].
                k = len(a) - 1
                while a[k] < a[j]: k -= 1
            # Swap A[j] and A[k].
                temp = a[j];  a[j] = a[k];  a[k] = temp

    # Reverse A[j+1..n-1].
        reverse(a, j + 1, n - 1)

def reverse(A: list[int], L: int, R: int) -> None:
    """
    Given int array A[0..n-1], reverse the order of the subsequence A[L..R]
    in situ without affecting the rest of A.
    """

    while L < R:
        # Swap A[L] and A[R].
            temp = A[L];  A[L] = A[R];  A[R] = temp
        #
            L += 1;  R -= 1

def printBoard(R: list[int]) -> None:
    """Print board represented by R, the column index of each row's queen."""
    for r in range(8):
        row = ['_','_','_','_','_','_','_','_']
        row[R[r]] = 'Q'
        print(''.join(row))  # print string consisting of concatenated chars.

eight_queens()