In this problem we work with and analyze the Queens Problem which is described by Springer and Friedman in Section 6.5 of the text. We wish to produce a more general solution to the Queens problem for a checker board of size n. For example, given n = 4, we consider the checker board of size 4 shown in Figure 1.

A solution of (2 4 1 3) is shown in Figure 1. (3 1 4 2) is also a solution for n = 4.

Write a function, queens, having form:

(define queens

(lambda (n)

...))

which will compute a list of all solutions for a checker board of size n. For example,

(queens 4) ==> ((2 4 1 3) (3 1 4 2))

The function solution?, defined by Springer and Friedman, uses length to test whether or not a given list is a solution. This is rather expensive since each time length is called, length must recursively or iteratively cdr down list. Try to devise a more efficient solution which does not use length to test for a solution.