(define (sudoku puzzle)
  (define (safe? filled digit cell)
    (cond ((null? filled) #t)
          ((and (= (vector-ref (car filled) 0) (vector-ref cell 0))
                (char=? (vector-ref (car filled) 3) digit)) #f)
          ((and (= (vector-ref (car filled) 1) (vector-ref cell 1))
                (char=? (vector-ref (car filled) 3) digit)) #f)
          ((and (= (vector-ref (car filled) 2) (vector-ref cell 2))
                (char=? (vector-ref (car filled) 3) digit)) #f)
          (else (safe? (cdr filled) digit cell))))
  (define (next digit) (integer->char (+ (char->integer digit) 1)))
  (define (new old digit) (vector (vector-ref old 0) (vector-ref old 1) (vector-ref old 2) digit))
  (let scan ((s 0) (empty '()) (filled '()))
    (if (< s 81)
        (let* ((row (quotient s 9))
               (col (modulo s 9))
               (box (+ (* (quotient row 3) 3) (quotient col 3)))
               (digit (string-ref puzzle s))
               (cell (vector row col box digit)))
          (if (char=? digit #\0)
              (scan (+ s 1) (cons cell empty) filled)
              (scan (+ s 1) empty (cons cell filled))))
        (let solve ((empty empty) (filled filled))
          (if (pair? empty)
              (let try ((cell (car empty)) (digit (next (vector-ref (car empty) 3))))
                (cond ((char<? #\9 digit) ; backtrack
                        (solve (cons (car filled) (cons (new cell #\0) (cdr empty))) (cdr filled)))
                      ((safe? filled digit cell) ; advance
                        (solve (cdr empty) (cons (new cell digit) filled)))
                      (else (try cell (next digit))))) ; try next digit
              (let ((str (make-string 81 #\0)))
                (do ((filled filled (cdr filled))) ((null? filled) str)
                  (let* ((cell (car filled)) (s (+ (* (vector-ref cell 0) 9) (vector-ref cell 1))))
                    (string-set! str s (vector-ref cell 3))))))))))

(display (sudoku "700100000020000015000006390200018000040090070000750003078500000560000040000001002"))

789135624623947815451286397237418569845693271916752483178524936562379148394861752