Nested for-loop in LispWorks (4x4 queens)

Question

I have just started using LispWorks and I am working on the 4x4 Queen problem. What I am trying to do is with the help of 4 for-loops state all the possible Queen-combinations, and then checking whether they are possible solutions or not. A possible state (1 3 4 2) for example means that in row 1 queen is in column 1, in row 2 queen is in column 3 and so on.

I think I am doing something wrong though because the compiler don't like my loops. The error I'm getting is something like: Loop keyword expected in...

Here is the code:

(loop for i in '(1 2 3 4) 
  nconc (loop for j in '(1 2 3 4) 
              nconc (loop for k in '(1 2 3 4) 
                          nconc (loop for l in '(1 2 3 4) 


                                     (defvar first 0)
                                     (defvar second 0)
                                     (defvar third 0)
                                     (defvar fourth 0)
                                     (setq first (abs (- 1 i)))
                                     (setq second (abs (- 2 j)))
                                     (setq third (abs (- 3 k)))
                                     (setq fourth (abs (- 4 l)))
                                     (if (and (not (eq first second)) (not (eq first third)) (not (eq first fourth)) (not (eq second third)) 
                                                (not (eq second fourth)) (not (eq first second)) (not (eq third fourth)))
                                           (if (and (or (eq i j) (eq i k) (eq i l) (eq j k) (eq j l)) (or (eq k l)))
                                               (print i j k l)))))))

Please help me out with the nested loops and feel free to comment on my code and possibly suggest better ways of solving this problem. Please keep it fairly basic, I am a complete beginner to LispWorks and I have only done some ADA 95 and Java before.

Thank you in advance

Answer 1

The reason you get the error message is that your code is lacking the keyword do after '(1 2 3 4) in the inner loop. As you are not collecting results from the loops, just printing the final result, you should use do instead of nconc in the outer loops as well.

Fixing this, another error shows up: print only print one object, so in order to print all four numbers you can use e.g. (print (list i j k l))

The program then prints

(1 1 1 1) 
(1 3 1 1) 
(2 2 1 1) 
(4 2 2 2) 
(4 4 3 3) 
(4 4 4 4)

so something is wrong with the logic as well.

However, there are also lots of improvements that can be done to the code:

1. Do not use defvar to introduce new variables inside the loop. defvar creates dynamic ("global") variables. Instead, use let, or introduce them as loop variables, like you have done with i , j etc.
2. Instead of first creating the variables, and then updating them once using setq, give them the correct value when they are created (using let or a loop keyvword).
3. As you are comparing pairs of numbers: Instead of using eq (which is for symbols) or eql (which is the correct one for comparing two numbers of the same type), use = or /= which can compare many numbers to check if they are all equal/different.

Together with a small fix of the logic, this results in the following code (which for illustration introduces some variables using loop keywords, and some using let):

(loop for i in '(1 2 3 4) 
      for first = (abs (- 1 i)) 
      do (loop for j in '(1 2 3 4)
               for second = (abs (- 2 j))
               do (loop for k in '(1 2 3 4)
                        do (loop for l in '(1 2 3 4)
                                 do (let ((third (abs (- 3 k)))
                                           (fourth (abs (- 4 l))))
                                       (if (and (/= first second third fourth)
                                                (/= i j k l))
                                          (print (list i j k l))))))))

Which result in

(2 4 3 1) 
(3 2 4 1) 
(4 1 3 2) 
(4 2 1 3) 

meaning that there are still logic errors present.

Hopefully the simplified code makes it easy to spot the error, which probably has something to do with not comparing (+ i 1), (+ j 2) etc.

Finally: If you want to extend the code to handle more queens, creating a recursive solution will be better than a solution using even more nested loops.