fork download
  1. ; square-sum puzzle
  2.  
  3. (define (range . args)
  4. (case (length args)
  5. ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
  6. ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
  7. ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
  8. (let loop ((x(car args)) (xs '()))
  9. (if (le? (cadr args) x)
  10. (reverse xs)
  11. (loop (+ x (caddr args)) (cons x xs))))))
  12. (else (error 'range "unrecognized arguments"))))
  13.  
  14. (define (isqrt n)
  15. (if (not (and (positive? n) (integer? n)))
  16. (error 'isqrt "must be positive integer")
  17. (let loop ((x n))
  18. (let ((y (quotient (+ x (quotient n x)) 2)))
  19. (if (< y x) (loop y) x)))))
  20.  
  21. (define (square? n)
  22. (let ((s (isqrt n)))
  23. (= (* s s) n)))
  24.  
  25. (define (adjacent n k)
  26. (filter (lambda (i)
  27. (and (not (= i k))
  28. (square? (+ i k))))
  29. (range 1 (+ n 1))))
  30.  
  31. (define (make-graph n)
  32. (map (lambda (k) (cons k (adjacent n k)))
  33. (range 1 (+ n 1))))
  34.  
  35. (define (square-sum n)
  36. (let ((graph (make-graph n)))
  37. (call-with-current-continuation
  38. (lambda (return)
  39. (do ((node n (- node 1))) ((zero? node) (list))
  40. (let dfs ((node node) (neighbors (assoc node graph)) (path (list node)))
  41. (when (= (length path) n) (return path))
  42. (do ((neighbors neighbors (cdr neighbors)))
  43. ((null? neighbors))
  44. (when (not (member (car neighbors) path))
  45. (dfs (car neighbors) (assoc (car neighbors) graph) (cons (car neighbors) path))))))))))
  46.  
  47. (display (square-sum 15)) (newline)
Success #stdin #stdout 0.07s 8384KB
stdin
Standard input is empty
stdout
(8 1 15 10 6 3 13 12 4 5 11 14 2 7 9)