module Queens where
  
  type Rank  = Int    -- Rows of the chess board
  type File  = Int    -- Columns of the chess board
  type Board = [Rank] -- Example [1,5,8,6,3,7,2,4]

  inCheck :: (File,Rank) -> (File,Rank) -> Bool
  inCheck (i,j) (m,n)
    = (j == n) 
      || (i + j == m + n) || (i - j == m - n)

  -- No need to check equality of columns (Files)
  -- since representation rules this out

      
  isSafe :: Board -> Rank -> Bool
  isSafe brd n
    = and [not (inCheck (i,j) (m,n)) |
           (i,j) <- zip [1..length brd] brd
          ]
      where
        m = length brd + 1          
          
  queens :: Rank -> File -> [Board]
  queens brdSize 0 = [[]]
  queens brdSize m
    = [brd ++ [n] |
       brd <- queens brdSize (m-1),
       n <- [1..brdSize],
       isSafe brd n
      ]
      
  queens8 = queens 8
  queens4 = queens 4
      
  backtrackProfile :: Rank -> [Int]
  backtrackProfile brdSize
    = [length (queens brdSize m) |
       m <- [0..brdSize]]

  backtrackProfileSum :: Rank -> (Int,[Int])
  backtrackProfileSum brdSize
    = (profileSum,profileLst)
      where
        profileLst = backtrackProfile brdSize
        profileSum = sum profileLst


  qFiles = ["qa","qb","qc","qd","qe","qf","qg","qh"]
  
  q8Test
   = [[1,5,8,6,3,7,2,4],[1,6,8,3,7,4,2,5],[1,7,4,6,8,2,5,3],[1,7,5,8,2,4,6,3]
     ,[2,4,6,8,3,1,7,5],[2,5,7,1,3,8,6,4],[2,5,7,4,1,8,6,3],[2,6,1,7,4,8,3,5]
     ,[2,6,8,3,1,4,7,5],[2,7,3,6,8,5,1,4],[2,7,5,8,1,4,6,3],[2,8,6,1,3,5,7,4]
     ,[3,1,7,5,8,2,4,6],[3,5,2,8,1,7,4,6],[3,5,2,8,6,4,7,1],[3,5,7,1,4,2,8,6]
     ,[3,5,8,4,1,7,2,6],[3,6,2,5,8,1,7,4],[3,6,2,7,1,4,8,5],[3,6,2,7,5,1,8,4]
     ,[3,6,4,1,8,5,7,2],[3,6,4,2,8,5,7,1],[3,6,8,1,4,7,5,2],[3,6,8,1,5,7,2,4]
     ,[3,6,8,2,4,1,7,5],[3,7,2,8,5,1,4,6],[3,7,2,8,6,4,1,5],[3,8,4,7,1,6,2,5]
     ,[4,1,5,8,2,7,3,6],[4,1,5,8,6,3,7,2],[4,2,5,8,6,1,3,7],[4,2,7,3,6,8,1,5]
     ,[4,2,7,3,6,8,5,1],[4,2,7,5,1,8,6,3],[4,2,8,5,7,1,3,6],[4,2,8,6,1,3,5,7]
     ,[4,6,1,5,2,8,3,7],[4,6,8,2,7,1,3,5],[4,6,8,3,1,7,5,2],[4,7,1,8,5,2,6,3]
     ,[4,7,3,8,2,5,1,6],[4,7,5,2,6,1,3,8],[4,7,5,3,1,6,8,2],[4,8,1,3,6,2,7,5]
     ,[4,8,1,5,7,2,6,3],[4,8,5,3,1,7,2,6]
     ,[5,1,4,6,8,2,7,3],[5,1,8,4,2,7,3,6],[5,1,8,6,3,7,2,4],[5,2,4,6,8,3,1,7]
     ,[5,2,4,7,3,8,6,1],[5,2,6,1,7,4,8,3],[5,2,8,1,4,7,3,6],[5,3,1,6,8,2,4,7]
     ,[5,3,1,7,2,8,6,4],[5,3,8,4,7,1,6,2],[5,7,1,3,8,6,4,2],[5,7,1,4,2,8,6,3]
     ,[5,7,2,4,8,1,3,6],[5,7,2,6,3,1,4,8],[5,7,2,6,3,1,8,4],[5,7,4,1,3,8,6,2]
     ,[5,8,4,1,3,6,2,7],[5,8,4,1,7,2,6,3]
     ,[6,1,5,2,8,3,7,4],[6,2,7,1,3,5,8,4],[6,2,7,1,4,8,5,3],[6,3,1,7,5,8,2,4]
     ,[6,3,1,8,4,2,7,5],[6,3,1,8,5,2,4,7],[6,3,5,7,1,4,2,8],[6,3,5,8,1,4,2,7]
     ,[6,3,7,2,4,8,1,5],[6,3,7,2,8,5,1,4],[6,3,7,4,1,8,2,5],[6,4,1,5,8,2,7,3]
     ,[6,4,2,8,5,7,1,3],[6,4,7,1,3,5,2,8],[6,4,7,1,8,2,5,3],[6,8,2,4,1,7,5,3]
     ,[7,1,3,8,6,4,2,5],[7,2,4,1,8,5,3,6],[7,2,6,3,1,4,8,5],[7,3,1,6,8,5,2,4]
     ,[7,3,8,2,5,1,6,4],[7,4,2,5,8,1,3,6],[7,4,2,8,6,1,3,5],[7,5,3,1,6,8,2,4]
     ,[8,2,4,1,7,5,3,6],[8,2,5,3,1,7,4,6],[8,3,1,6,2,5,7,4],[8,4,1,3,6,2,7,5]]

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

-- Versions
-- v0.01 Created 20 April 2026