Took me some time, but now I got it. I'm wondering though why the following is no valid solution:
Gerr, Ubhfr, Enoovg, Znyyrg
Blfgre, Fxv, Zrqny, Sver
Qvr, Bjy, Qbt, Obbx, Fgne
Frrzf gb shysvyy rirel ehyr, rkprcg gur bar gung gur 3eq ebj unf gb or n jbeq. Fb vafgrnq V fbyirq vg ol fgnegvat sebz jung V gubhtug vf gur zbfg yvxryl jbeq sbe 3eq ebj naq onpxsvyyvat gur erfg.