Write a program in Common Lisp using a pure functional style (no global variables, no side-effects) to find the best placement of two chess queens on a n by n sized chess board so that the coverage of the 2 queens are either minimized or maximized (up to the user).

Your program should return a list of three items, the number of squares covered by the queens and the locations of the two queens. Each queen location is as a list of two integers. For example a minimum coverage for n=3 might be (8 (3 3) (3 1)).

The bottom left square is (1 1) and the bottom right square for n=3 is (3 1). Due to symmetry, it really doesn't matter whether (1 1) is bottom left, bottom right, top left, or top right.

Start by defining a function to build a list of integers from 1 to n. Next write a function to create a list of combinations of pairs of integers. You can either use n as the input or the list of integers as input (I recommend the list). This would look like ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3)) for n = 3.

You can use this function on itself to get a list of all possible squares for two queens. Since both queens cannot occupy the same square, you need code to to remove duplicated squares. I recommend you use the built-in functions remove-if or delete-if. These require a test predicate (function) that will check if the first item in a list is the same as the second item in the list to remove/delete that item. For example, ((1 1) (1 1)) should be removed/deleted because both queens would be on the same (1 1) square. The remove-if or delete-if functions take in a test predicate and a list of squares (a square is a list of two integers) to get a list of all possible pairs of squares for the queen positions (without both queens on top of each other).

Next work on a function that takes in the positions of the two queens as two squares and takes in n and returns the number of squares covered by the 2 queens. It is helpful to have an intersect function that takes in two squares and returns true if the two squares are on the same column, same row, or same diagonal (there are two diagonals for any square). The easiest way is to check every possible square and see if it intersects with either of the queen squares.

Finally compare the coverage of all possible queen posiions to find the max or min coverage position. You might find it helpful to use reduce and pass it a function that returns the smaller (or larger for most coverage) of a list consisting of the coverage of the 2 queens followed by the squares occupied by the 2 queens.