Here is Abigail-styled golfed regex approach. It works for me with "8" as argument, but crashes with "5" :)

#!perl -l
sub f{/((.).*)(.)(??{$"x($2!=$3&length$1!=abs$2-$3)})/?0:/.{@ARGV}/?pr
+int:map&f,$_.1..$_."@ARGV"}f
[download]

P.S. Removing one char magically solves crashing:

-l sub f{/((.).*)(.)(??{$2!=$3&&length$1!=abs$2-$3&&0})/?0:/.{@ARGV}/?print:map&f,$_.1..$_."@ARGV"}f

Update on Sep 20: more golf