Ok, I take back what I said. Some problems are impossible to solve in Scheme. I tried to solve QKP in Scheme (a pretty straightforward problem) and couldn't get it to run under the time limit of 1s. I implemented the same algorithm in C and it ran in 0.02s (so far, mine is the fastest accepted solution). So a solution implemented in Scheme, with Guile, can be expected to be more than 50 times slower than the C implementation.
My Scheme code (TLEd) is below. I don't know what else to change to make it faster. Yes, I'm aware that 'do' is considered in poor taste in some circles, but, with Guile, I found that it's slightly faster than a loop with named let.
(define visited (make-string (* 1004 1004)))
(let do-test-case ((rows (read)) (cols (read)) (board-number 1))
(if (and (> rows 0) (> cols 0))
(let* ((read-piece-list (lambda (n)
(let loop ((n n) (l '()))
(if (= n 0) l (loop (- n 1) (cons (cons (+ 1 (read)) (+ 1 (read))) l))))))
(fix-coords (lambda (x) (+ (* (car x) (+ cols 4)) (cdr x))))
(queens (map fix-coords (read-piece-list (read))))
(knights (map fix-coords (read-piece-list (read))))
(pawns (map fix-coords (read-piece-list (read))))
(knight-directions (map fix-coords '((1 . 2) (-1 . 2) (1 . -2) (-1 . -2) (2 . 1) (-2 . 1) (2 . -1) (-2 . -1))))
(queen-directions (map fix-coords '((1 . 0) (-1 . 0) (0 . 1) (0 . -1) (1 . 1) (1 . -1) (-1 . 1) (-1 . -1))))
(attack-count 0))
;
; initialize visited
;
; #\O: occupied; #\x: attacked; #\space: safe
;
(substring-fill! visited 0 (* 2 (+ cols 4)) #\O)
(let loop ((r 0) (index (* 2 (+ cols 4))))
(if (< r rows)
(begin
(string-set! visited index #\O)
(string-set! visited (+ index 1) #\O)
(string-set! visited (+ index 2 cols) #\O)
(string-set! visited (+ index 3 cols) #\O)
(substring-fill! visited (+ index 2) (+ index 2 cols) #\space)
(loop (+ r 1) (+ index cols 4)))))
(substring-fill! visited (* (+ 2 rows) (+ cols 4)) (* (+ 4 rows) (+ 4 cols)) #\O)
;
; do the dog
;
(letrec ((visit-square (lambda (i)
(string-set! visited i #\O)
(set! attack-count (+ attack-count 1))))
(walk-queen (lambda (i d)
(do ((i i (+ i d)))
((char=? (string-ref visited i) #\O))
(if (char=? (string-ref visited i) #\space)
(begin
(string-set! visited i #\x)
(set! attack-count (+ attack-count 1)))))))
(visit-queen (lambda (i)
(do ((l queen-directions (cdr l)))
((null? l))
(walk-queen (+ i (car l)) (car l)))))
(visit-knight (lambda (i)
(do ((l knight-directions (cdr l)))
((null? l))
(let* ((d (car l))
(i (+ i d)))
(if (char=? (string-ref visited i) #\space)
(begin
(string-set! visited i #\x)
(set! attack-count (+ attack-count 1)))))))))
(for-each visit-square queens)
(for-each visit-square knights)
(for-each visit-square pawns)
(for-each visit-queen queens)
(for-each visit-knight knights))
(display "Board ") (display board-number)
(display " has ") (display (- (* rows cols) attack-count))
(display " safe squares.\n")
(do-test-case (read) (read) (+ 1 board-number)))))