Kakuro is a puzzle game that is kind of like a crossword with numbers.
Each row and column has a target value at the end, and you must fill
in (without reuse) the numbers 1 through 9 to add up to that target.
I ended up writing the following code to find all of the legal
solutions given a total and number of boxes to fill in. It also,
optionally, restricts the results to only those that contain any
additional numbers given. I'm still really new to Lisp, and just doing
this to goof around and try to learn the language, so I would
appreciate any pointers, criticisms, or wild re-implementations that
demonstrate something cool about Lisp.
-Adam
---
(defun compare-total (val numlist)
(= val (apply '+ numlist)))
(defun find-values (boxes value)
"Returns all the valid solutions for _value across _boxes locations"
(remove-if-not #'(lambda (x) (compare-total value x)) (gen-values
boxes)))
(defun must-contain (items lists)
"Returns only the members of _lists that have all the values in the
list _items"
(remove-if #'(lambda (lst) (set-difference items lst)) lists))
(defun gen-values (boxes &optional (initlist nil))
"Generates a (unvalidated) list of the possible values that will fit
in the given number of boxes"
(if (not initlist)
(setq initlist (loop for i from 1 to (- 10 boxes) collect (list
i))))
(if (> boxes (length (first initlist)))
(gen-values boxes (mapcan #'next-values initlist))
(return-from gen-values initlist)))
(defun next-values (lst)
"Generate the set of lists representing the next values for the
given list"
(loop for i from 1 to 9
when (> i (first (last lst))) collect
(append lst (list i))))
(defun print-nums (numlist)
(loop for lst in numlist do (format t "~{~a~^ + ~}~%" lst)))
(defun solutions (boxes value &rest numbers)
(print-nums (must-contain numbers (find-values boxes value))))
On Mar 8, 4:04 am, "Adam Jones" <·······@gmail.com> wrote:
> Kakuro is a puzzle game that is kind of like a crossword with numbers.
> Each row and column has a target value at the end, and you must fill
> in (without reuse) the numbers 1 through 9 to add up to that target.
<curmudgeon-rant>
Been doing "Cross Sums" for 40+ years, all of the sudden
they become popular and cool because of a japanese name?
</curmudgeon-rant>
> (defun next-values (lst)
> "Generate the set of lists representing the next values for the
> given list"
> (loop for i from 1 to 9
> when (> i (first (last lst))) collect
> (append lst (list i))))
LAST and APPEND are not very efficient and since
the order of the list doesn't really matter:
(defun next-values(list)
(loop for i
from (if (first list)
(1+ (first list))
1)
to 9
collect (cons i list)))
> (defun print-nums (numlist)
> (loop for lst in numlist do (format t "~{~a~^ + ~}~%" lst)))
Halfway there:
(defun print-nums (numlist)
(format t "~&~{~{~a~^ + ~}~%~}" numlist))
You could also just generate all the possibilities
once and cache them:
(defparameter *combos* (make-hash-table))
(defun gen-key(length sum)
(+ (* 10 sum) length))
(defun fill-hash()
(labels ((combo (start list sum length)
(when (< length 9)
(loop for i from start to 9 do
(let ((new-list (cons i list))
(new-length (1+ length))
(new-sum (+ i sum)))
(push new-list
(gethash (gen-key new-length new-sum)
*combos*))
(combo (1+ i) new-list new-sum new-length))))))
(combo 1 '() 0 0)))
(defun find-values(boxes value)
;; if the hash table is empty fill it
(when (zerop (hash-table-count *combos*)) (fill-hash))
(gethash (gen-key boxes value) *combos*))
---
Geoff