#!/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 :
  """ 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 :
  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] :
  if m == 0 :
    return [[]]
  else :
    lstBrd = [brd + [n]
              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] :
  return queens(8, m)

def queens4(m: File) -> [Board] :
  return queens(4, m)

def backtrackProfile(brdSize: Rank) -> list[int] :
  return [len(queens(brdSize,m)) for m in range(brdSize+1)]

def backtrackProfileSum(brdSize: Rank) -> (int,list[int]) :
  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