Sudoku table generator failure, lisp

Question

Hello. I have a problem with some part of my lisp code. It is a sudoku table generator. It works fine until this part:

(loop for e in entries do     
    (if (and (not (member e sub))
             (not (member e col)))
        (progn (setq choices (nconc choices (list e)))
               (print choices)))
    (if (= (length choices) 1)
        (setq pick (car choices))
        (if (not (= (length choices) 0)) 
            (setq pick (nth (random (+ 0 (length choices))) choices))))

Basically, I am on a row x and a column y, and I need to insert an element. I watch the submatrix for this element and for column, and I choose the number that isn't appearing in any of the above and put it there. That's the "pick" variable. The problem is that sometimes the "choices" variable gets NIL value although in entries loop it has the right value. When it gets NIL, the pick value stays the same as it was in last loop (I am looping in columns and rows, above this snippet), making my final table have invalidated output (double values in a row, for example). How can I track where the choices variable changes? I work with it only in this snippet and I don't understand why it changes suddenly to nil.

For instance, I usually have:

• in entries loop: choices (5)
• Out of entries loop: choices (5)
• in entries loop: choices (6 7)
• Out of entries loop: choices (6 7) and after that this one:
• in entries loop: choices nil.

Thank you.

Answer 1

This is not a proper answer, but I did fix the indentation to make the code a bit more legible to myself and other answerers:

(loop for e in entries do
  (if (and (not (member e sub))  (not (member e col)))
      (progn  (setq choices (nconc choices (list e)))
              (print choices) ))
  (if (= (length choices) 1) (setq pick (car choices))
      (if (not (=(length choices) 0))
          (setq pick (nth (random (+ 0 (length choices))) choices))))

Questions:

1. Is entries a list of lists? Does each list represent a row?
2. What are the values 'sub' and 'col' set to?

Answer 2

A potential source of trouble is NCONC.

• nconc is destructively modifying the first list. If that is unwanted, use APPEND instead.

A second source of problem with NCONC is the use of literal lists.

Example:

(defun foo (bar)  (let ((l '(1 2 3))) ...))

Here '(1 2 3) is a literal list. The effects of destructively modifying such a list is undefined in Common Lisp. Thus it should be avoided. What to do instead?

1. cons the list: (list 1 2 3)
2. copy the literal list: (copy-list l)
3. use non destructive operations (APPEND instead of NCONC, ...)

Answer 3

First, some reformatting:

(loop for e in entries do     
  (if (and (not (member e sub))
           (not (member e col)))
      (progn (setq choices (nconc choices (list e))) 
             (print choices)))
(if (= (length choices) 1)
    (setq pick (car choices))
(if (not (= (length choices) 0))
    (setq pick (nth (random (+ 0 (length choices))) choices))))

Then, if you don't need the alternative clause of if, but want a progn, you can use when:

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (setq choices (nconc choices (list e))) 
    (print choices))
(if (= (length choices) 1)
    (setq pick (car choices))
(if (not (= (length choices) 0))
    (setq pick (nth (random (+ 0 (length choices))) choices))))

The last two if clauses are mutually exclusive, so either cond or case would be appropriate (I'll use cond for now):

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (setq choices (nconc choices (list e))) 
    (print choices))
(cond ((= (length choices) 1)
       (setq pick (car choices)))
      ((not (= (length choices) 0))
       (setq pick (nth (random (+ 0 (length choices))) choices))))

There is a zerop predicate:

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (setq choices (nconc choices (list e))) 
    (print choices))
(cond ((= (length choices) 1)
       (setq pick (car choices)))
      ((not (zerop (length choices)))
       (setq pick (nth (random (+ 0 (length choices))) choices))))

I don't see what adding 0 to some value should accomplish:

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (setq choices (nconc choices (list e))) 
    (print choices))
(cond ((= (length choices) 1)
       (setq pick (car choices)))
      ((not (zerop (length choices)))
       (setq pick (nth (random (length choices)) choices))))

Unless you are sure that pick is set to a sensible default to begin with, you should perhaps have a default case (this may be one of your problems):

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (setq choices (nconc choices (list e))) 
    (print choices))
(cond ((= (length choices) 1)
       (setq pick (car choices)))
      ((not (zerop (length choices)))
       (setq pick (nth (random (length choices)) choices)))
      (t
       (setq pick nil))

Instead of using setq and nconc, you can use push (this puts the new element at the start of the list, but since you pick randomly anyway, this shouldn't be a concern):

(loop for e in entries do     
  (when (and (not (member e sub))
             (not (member e col)))
    (push e choices)
    (print choices))
(cond ((= (length choices) 1)
       (setq pick (car choices)))
      ((not (zerop (length choices)))
       (setq pick (nth (random (length choices)) choices)))
      (t
       (setq pick nil))

I suspect that at the start of this snippet, choices is supposed to be (), that you don't need choices after this snippet, and that printing choices is just for debugging, so you could do this in a different way by using remove-if and changing the condition:

(let ((choices (remove-if (lambda (e)
                            (or (member e sub)
                                (member e col)))
                          entries)))
  (print choices)
  (cond ((= (length choices) 1)
         (setq pick (car choices)))
        ((not (zerop (length choices)))
         (setq pick (nth (random (length choices)) choices)))
        (t
         (setq pick nil)))

If choices is printed as () now, it means that there are no choices left here, so you will have to do some backtracking then (or whatever your algorithm does when a dead end is reached).

Finally, since (length choices) can only be non-negative integers, you can use case instead of cond if you test the cases in different order:

(let ((choices (remove-if (lambda (e)
                            (or (member e sub)
                                (member e col)))
                          entries)))
  (print choices)
  (case (length choices)
    (0 (setq pick nil))
    (1 (setq pick (car choices)))
    (otherwise (setq pick (nth (random (length choices)) choices)))))

Update by request.

As Rainer points out, this is basically the body of a pick function, so we can get rid of all the free variables. Also, instead of car, you can use the (for lists) more descriptive name first:

(defun pick (entries sub col)
  (let ((choices (remove-if (lambda (e)
                              (or (member e sub)
                                  (member e col)))
                            entries)))
    (print choices)
    (case (length choices)
      (0 nil)
      (1 (first choices))
      (otherwise (nth (random (length choices)) choices)))))

This function would be defined elsewhere, and in the snippet's place, it would be called like this:

(pick entries sub col)

In order not to compute (length choices) twice, we can put that into the let (which needs to become let* for serial evaluation):

(defun pick (entries sub col)
  (let* ((choices (remove-if (lambda (e)
                               (or (member e sub)
                                   (member e col)))
                             entries))
         (choices-length (length choices)))
    (print choices)
    (case choices-length
      (0 nil)
      (1 (first choices))
      (otherwise (nth (random choices-length) choices)))))

A final step (really optional, but perhaps you discover that you have more sequences reducing your choices, e.g. row) would be a little generalization:

(defun pick (entries &rest exclusion-sequences)
  (let* ((choices (remove-if (lambda (e)
                               (some #'identity
                                     (mapcar (lambda (seq)
                                               (member e seq))
                                             exclusion-sequences)))
                             entries))
         (choices-length (length choices)))
    (print choices)
    (case choices-length
      (0 nil)
      (1 (first choices))
      (otherwise (nth (random choices-length) choices)))))

The call to this function is of the same shape, but you can now use any number of exclusion sequences:

(pick entries col sub row ver ima fou)

Answer 4

My Lisp is quite rusty, but I don't see any backtracking there... and I think you cannot just start putting numbers randomly and expect that they will make a proper sudoku game.

It seems that the list is nil because there are no possible options and thus is not created. You should handle that.