#!/usr/bin/env python3

# 8 Queens Problem
# Version: See end

# Board Representation: list of ranks (rows)

type Rank  = int    # Rows
type File  = int    # Columns
type Board = [Rank] # Example

def inCheck(posn1: (File,Rank), posn2: (File,Rank)) -> bool :        #e\label{python:inCheck}\only<article>{\index[pythonCode]{inCheck@\STvar{inCheck}|STmainEntry}}
  """ Return True if Queen in position posn1 == (i,j)
  can be threatened by Queen in posn2 == (m.n)
  Precondition: not (i == m) 
  since we are placing queens File (column) by File
  """
  (i,j) = (posn1[0],posn1[1])
  (m,n) = (posn2[0],posn2[1])
  return ((j == n)
          or (i + j == m + n)
          or (i - j == m - n))

def isSafe(brd: Board, n: Rank) -> bool :                            #e\label{python:isSafe}\only<article>{\index[pythonCode]{isSafe@\STvar{isSafe}|STmainEntry}}
  nxtFl = len(brd) + 1
  lstOfCks = [not (inCheck((i,j), (nxtFl,n)))
             for (i,j) in list(zip(range(1,len(brd)+1), brd))
             ]
  return all(lstOfCks)

def queens(brdSize: Rank,m: File) -> [Board] :                       #e\label{python:queens}\only<article>{\index[pythonCode]{queens@\STvar{queens}|STmainEntry}}
  if m == 0 :
    return [[]]                                                      #e\label{python:queensA}
  else :
    lstBrd = [brd + [n]                                              #e\label{python:queensB}
              for brd in queens(brdSize, m-1)
              for n in range(1,brdSize + 1)
              if isSafe(brd,n)]  
    return lstBrd


def queens8(m: File) -> [Board] :                                    #e\label{python:queens8}\only<article>{\index[pythonCode]{queens8@\STvar{queens8}|STmainEntry}}
  return queens(8, m)

def queens4(m: File) -> [Board] :                                    #e\label{python:queens4}\only<article>{\index[pythonCode]{queens4@\STvar{queens4}|STmainEntry}}
  return queens(4, m)

def backtrackProfile(brdSize: Rank) -> list[int] :                   #e\label{python:backtrackProfile}\only<article>{\index[pythonCode]{backtrackProfile@\STvar{backtrackProfile}|STmainEntry}}
  return [len(queens(brdSize,m)) for m in range(brdSize+1)]

def backtrackProfileSum(brdSize: Rank) -> (int,list[int]) :          #e\label{python:backtrackProfileSum}\only<article>{\index[pythonCode]{backtrackProfileSum@\STvar{backtrackProfileSum}|STmainEntry}}
  profileLst = backtrackProfile(brdSize)
  profileSum = sum (profileLst)
  return (profileSum,profileLst)

# Source
# \only<article>{\citet[161]{bird:88}}%
# \only<beamer>{Bird and Wadler (1988, page 161)}
# \emph{Introduction to Functional Programming}


# Versions
# v0.02 25 April 2026 defined queens8 and queens4
# v0.01 Created 20 April 2026