GAIさんへのお返事です。
かなり答えがあるようです。検証はO(2^n)ですから、２４あたりが妥当かと、、、
F2$(x)を使ったものは、前回の「数値の数だけ進む」の交差判定を含んだ回答となります。
（F$(x)を使った４箇所のコメントを入れ替える）
!散歩コースの探索
DECLARE EXTERNAL FUNCTION F.F$ !外部関数の宣言
DECLARE EXTERNAL FUNCTION F2$ !外部関数の宣言
LET t0=TIME
PUBLIC NUMERIC ANSWER_COUNT !解答数
LET ANSWER_COUNT=0
PUBLIC NUMERIC N !歩数
LET N=16
PUBLIC NUMERIC M !マップの大きさ
LET M1=0
LET M2=0
FOR i=0 TO N !※2+4+6+ … +(N-2)+Nより大きく
LET t=LEN(F$(i)) !歩数
!!!LET t=LEN(F2$(i)) !歩数 ←←←←←
IF MOD(i,2)=1 THEN
LET M1=M1+t
ELSE
LET M2=M2+t
END IF
NEXT i
LET M=MAX(M1,M2)
PRINT M;M1;M2
DIM map(-M TO M,-M TO M) !散歩したコース（足跡）
MAT map=(ORD("."))*CON !未踏
LET x=0 !現在位置
LET y=0
!※１歩目と２歩目を固定して、回転と鏡面を排除する
CALL walk(F$(0),map,0,x,y, ok) !１歩目は東へ ※0:東、1:北、2:西、3:南
!!!CALL walk(F2$(1),map,0,x,y, ok) !１歩目は東へ ※0:東、1:北、2:西、3:南 ←←←←←
LET d=MOD(0-1,4) !進行方向
CALL walk(F$(1),map,d,x,y, ok) !２歩目は北へ
!!!CALL walk(F2$(2),map,d,x,y, ok) !２歩目は北へ ←←←←←
CALL search(3,map,d,x,y) !３歩目以降
IF ANSWER_COUNT=0 THEN PRINT "解答なし"
PRINT "計算時間=";time-t0
END
EXTERNAL SUB walk(s$,map(,),d,x,y, ok) !コースに足跡を残す
LET ok=0
LET L=LEN(s$)
SELECT CASE d !進行方向に応じて
CASE 0 !E
FOR i=1 TO L
IF map(y,x+i)<>ORD(".") THEN EXIT SUB !未踏以外なら
LET map(y,x+i)=ORD(s$(i:i))
NEXT i
LET x=x+L !移動先
CASE 1 !N
FOR i=1 TO L
IF map(y+i,x)<>ORD(".") THEN EXIT SUB !未踏以外なら
LET map(y+i,x)=ORD(s$(i:i))
NEXT i
LET y=y+L !移動先
CASE 2 !W
LET x=x-L !移動先 ※予め先に
FOR i=1 TO L
IF map(y,x+i-1)<>ORD(".") THEN EXIT SUB !未踏以外なら
LET map(y,x+i-1)=ORD(s$(i:i))
NEXT i
CASE 3 !S
LET y=y-L !移動先 ※予め先に
FOR i=1 TO L
IF map(y+i-1,x)<>ORD(".") THEN EXIT SUB !未踏以外なら
LET map(y+i-1,x)=ORD(s$(i:i))
NEXT i
CASE ELSE
END SELECT
LET ok=1 !成功
END SUB
EXTERNAL SUB search(s,map(,),d,x,y) !バックトラックで検索する
DECLARE EXTERNAL FUNCTION F.F$ !外部関数の宣言
DECLARE EXTERNAL FUNCTION F2$ !外部関数の宣言
LET s$=F$(s-1) !歩数を算出する
!!!LET s$=F2$(s) !歩数を算出する ←←←←←
LET L=LEN(s$)
DIM mmm(-L TO L) !save map
IF MOD(s,2)=0 THEN
FOR i=-L TO L !１列分のみ（メモリ使用の節約）
LET mmm(i)=map(y+i,x)
NEXT i
ELSE
FOR i=-L TO L !１行分のみ
LET mmm(i)=map(y,x+i)
NEXT i
END IF
FOR k=-1 TO 1 STEP 2 !右と左のみ
LET dd=MOD(d+k,4) !１つ前を基準にして、s歩目の方向を決める
LET xx=x
LET yy=y
CALL walk(s$,map,dd,xx,yy, ok) !s歩目の移動
IF ok=1 THEN
IF s=N THEN !指定の歩数に達したら
IF xx=0 AND yy=0 THEN !元の位置に戻ったら
LET ANSWER_COUNT=ANSWER_COUNT+1 !解答数
PRINT ANSWER_COUNT
FOR i=-M TO M !コースを表示する
LET t$=""
FOR j=-M TO M
LET t$=t$ & CHR$(map(i,j))
NEXT j
PRINT t$ !１行分をまとめて出力する（高速）
NEXT i
PRINT
END IF
ELSE
CALL search(s+1,map,dd,xx,yy) !次へ
END IF
END IF
IF MOD(s,2)=0 THEN !restore map
FOR i=-L TO L
LET map(y+i,x)=mmm(i)
NEXT i
ELSE
FOR i=-L TO L
LET map(y,x+i)=mmm(i)
NEXT i
END IF
NEXT k
END SUB
MODULE F !英語読みに変換する
SHARE STRING nm$(0 TO 19) !０～１９
DATA "Zero" !0
DATA "One" !1
DATA "Two" !2
DATA "Three" !3
DATA "Four" !4
DATA "Five" !5
DATA "Six" !6
DATA "Seven" !7
DATA "Eight" !8
DATA "Nine" !9
DATA "Ten" !10
DATA "Eleven" !11
DATA "Twelve" !12
DATA "Thirteen" !13
DATA "Fourteen" !14
DATA "Fifteen" !15
DATA "Sixteen" !16
DATA "Seventeen" !17
DATA "Eighteen" !18
DATA "Nineteen" !19
MAT READ nm$
SHARE STRING nm2$(2 TO 9) !２０以上
DATA "Twenty" !20
DATA "Thirty" !30
DATA "Fourty" !40
DATA "Fifty" !50
DATA "Sixty" !60
DATA "Seventy" !70
DATA "Eigthy" !80
DATA "Ninety" !90
MAT READ nm2$
PUBLIC FUNCTION F$
EXTERNAL FUNCTION F$(x) !数値を英語読みに変換する ※０～９９
IF x<20 THEN !0～19なら
LET v$=v$ & nm$(x)
ELSE
LET v$=v$ & nm2$(INT(x/10)) !十の位
LET w=MOD(x,10) !一の位
IF w<>0 THEN LET v$=v$ & "-" & nm$(w)
END IF
LET F$=v$
END FUNCTION
END MODULE
EXTERNAL FUNCTION F2$(x) !数値の長さ
LET F2$=REPEAT$(mid$("123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",x,1),x)
END FUNCTION
!回答、情報、アルゴリズム、パズル