title: Unexpected results for 'finding the digits' problem using recursion in Common Lisp
body: <p>The &quot;<em>finding the digits</em> problem&quot; is this:</p>
  <pre><code>Find unique decimal digits A, B, C such that
  
       CCC
    +  BBB
    +  AAA
    = CAAB 
  </code></pre>
  <p>To solve it using recursion in Common Lisp, I've written this code:</p>
  <pre class="lang-lisp prettyprint-override"><code>(defun find! ()
    (found? 0        ;; initially point to the number 1
            '(1 2 3) ;; initial list 
            '()      ;; initially no numbers found
            3        ;; numbers list width is 3 
            ) )
  
  (defun found? (index lst occupied width)
    (if (&lt; index (1- width))
        (do ( (j 1 (1+ j) ) )
            ( (&gt; j 9) lst)
          (unless (some (lambda (x) (= x j)) occupied)
            (setf (nth index lst) j)
            (push j occupied)
            (if (found? (1+ index) lst occupied width) ;; recursion happens here
                lst
                (setf occupied (remove j occupied)))))
        (do ( (j 1 (1+ j) ) )
            ( (&gt; j 9) lst)
          (unless (some (lambda (x) (= x j)) occupied)
            (setf (nth index lst) j)
            (let ((lefthnd (* 111 (reduce #'+ lst)))
                  (rghthnd (reduce #'+ 
                              (mapcar 
                                (lambda (x y) (* x y))
                                '(1000 100 10 1)
                                (list (third lst) (first lst) 
                                      (first lst) (second lst))))))
              (if (= lefthnd rghthnd)
                  lst
                  'nil))))))
  </code></pre>
  <p>The delivered result (<code>lst</code>) is <code>(9 9 9)</code></p>
  <p>The expected result (<code>lst</code>) is <code>(9 8 1)</code> meaning <code>A=9</code>, <code>B=8</code>, <code>C=1</code> so that the equation <code>CCC + BBB + AAA = CAAB</code> holds i.e.</p>
  <pre><code>      111     ;  CCC
     +  888     ;  BBB
     +  999     ;  AAA
     = 1998     ; CAAB
  </code></pre>
  <p>Which parts of the code should I change so that it gives the expected result? Can someone fix the code? Note that using recursion is a must. Only one line of recursion is enough i.e. like the line where the <code>;; recursion happens here</code> comment is.</p>
  <p>What is the minimal edit to fix this code?</p>