盤や駒を文字列で扱っているのを、数値に置き換えると２倍程度（経験則）速くなると思います。
サンプル・プログラム
!パズル - 将棋駒の入れ替え
!３×３ １行目と３行目を入れ替える
! 銀金銀 歩歩歩
! 角 飛 → 角 飛
! 歩歩歩 銀金銀
!答え ３０手
LET t0=TIME
PUBLIC NUMERIC xSIZE,ySIZE !盤の大きさ
LET xSIZE=3
LET ySIZE=3
PUBLIC NUMERIC cSPACE !空白の数
LET cSPACE=1
DECLARE STRING INIT$ !初期の状態
LET INIT$="銀金銀角 飛歩歩歩"
PUBLIC STRING GOAL$ !完成の状態
LET GOAL$="歩歩歩角 飛銀金銀" !完全一致
!!LET GOAL$="歩歩歩○○○○○○" !部分一致
PUBLIC STRING KO$(6) !駒の種類と移動可能範囲 ※８近傍 動きは将棋と同じ
DATA "×○××歩××××"
DATA "○○○×銀×○×○"
DATA "○○○○金○×○×"
DATA "○×○×角×○×○"
DATA "×○×○飛○×○×"
DATA "○○○○玉○○○○"
FOR i=1 TO 6
READ KO$(i)
NEXT i
PUBLIC NUMERIC LIM !手数の上限 →最少手数
LET LIM=200
PUBLIC STRING ANS$(0 TO 200) !上限までの手順
PUBLIC STRING STK$(0 TO 200) !局面の記録 ※スタック
FOR i=0 TO 200
LET ANS$(i)=""
LET STK$(i)=""
NEXT i
!PUBLIC NUMERIC LVL(0 TO 200) !----- trace -----
!MAT LVL=ZER
IF LEN(INIT$)<>ySIZE*xSIZE THEN
PRINT "盤の大きさ（xSIZE,ySIZE）と駒の数（INIT$）が合いません。"
STOP
END IF
IF LEN(GOAL$)<>ySIZE*xSIZE THEN
PRINT "盤の大きさ（xSIZE,ySIZE）と駒の数（GOAL$）が合いません。"
STOP
END IF
LET STK$(0)=INIT$
CALL backtrack(0) !０手目
IF ANS$(0)="" THEN
PRINT "解なし"
ELSE
PRINT
FOR i=1 TO LIM !解を表示する
PRINT ANS$(i)
NEXT i
END IF
PRINT "計算時間=";TIME-t0;"秒"
END
EXTERNAL SUB backtrack(L) !１手ずつ打っていき、行き詰まれば元に戻ってやり直す
LET bd$=stk$(L) !現在の局面
!---------- ↓↓↓↓↓ ---------- trace
!SET DRAW mode hidden !ちらつき防止の開始
!CLEAR
!FOR i=1 TO L
! PLOT TEXT ,AT 0.4+0.05*MOD(i-1,10),0.95-0.04*INT((i-1)/10): STR$(LVL(i))
!NEXT i
!FOR i=1 TO ySIZE
! LET t=(i-1)*xSIZE
! PLOT TEXT ,AT 0.1,0.50-i*0.05: bd$(t+1:t+xSIZE)
!NEXT i
!SET DRAW mode explicit !ちらつき防止の終了
!---------- ↑↑↑↑↑ ----------
LET C=0 !枝刈り ※「残りの手数」と「駒の位置が一致しない数」との関係より
FOR i=1 TO ySIZE*xSIZE
SELECT CASE GOAL$(i:i)
CASE "×"," ","○" !何でも良い
CASE ELSE !完全一致
IF GOAL$(i:i)<>bd$(i:i) THEN LET C=C+1 !Ｃ個の駒を一致させる必要があるが、
END SELECT
NEXT i
IF L+C>LIM THEN EXIT SUB !残りの手数が足りないので、不可能！！！
IF C=0 THEN !完成なら、手順を記録しておく
PRINT L;"手"
FOR i=0 TO L
LET ANS$(i)=STK$(i)
NEXT i
PRINT STK$(L) !debug
LET LIM=L !上限を狭める
END IF
IF L>=LIM THEN EXIT SUB !上限まで
LET CntOfSP=0
FOR p=1 TO ySIZE*xSIZE !盤を走査して空白に駒を移動させる
IF bd$(p:p)=" " THEN
LET px=MOD(p-1,xSIZE)+1 !水平・垂直の座標へ
LET py=INT((p-1)/xSIZE)+1
!!!FOR d=1 TO 9 !隣接する駒を探す ※ケースバイケース
FOR d=9 TO 1 STEP -1 !隣接する駒を探す ※ケースバイケース
IF d=5 THEN
ELSE
LET mx=px + MOD(d-1,3)-1 !移動元の座標 ※dを水平・垂直の差分dx,dyへ
LET my=py + INT((d-1)/3)-1
IF (mx>=1 AND mx<=xSIZE) AND (my>=1 AND my<=ySIZE) THEN !盤内か確認する
LET mp=(my-1)*xSIZE + mx !連番へ
LET t$=bd$(mp:mp)
IF t$="×" OR t$=" " THEN
ELSE
FOR a=1 TO UBOUND(KO$) !駒の属性を得る
IF t$=KO$(a)(5:5) THEN EXIT FOR
NEXT a
IF KO$(a)(10-d:10-d)="×" THEN !移動可能範囲なら
ELSE
LET w$=bd$
LET w$(p:p)=KO$(a)(5:5) !移動させる
LET w$(mp:mp)=" "
FOR t=L TO 0 STEP -1 !最近の局面から順に新しい手かどうか確認する
IF STK$(t)=w$ THEN EXIT FOR
NEXT t
IF t<0 THEN
!LET LVL(L+1)=CntOfSP*10+d !----- trace -----
LET STK$(L+1)=w$ !記録して、次の局面へ
CALL backtrack(L+1)
END IF
END IF
END IF
END IF
END IF
NEXT d
LET CntOfSP=CntOfSP+1
IF CntOfSP=cSPACE THEN EXIT FOR !空白の数だけ
END IF
NEXT p
END SUB
WindowsMe、PentiumⅢ700MHz、192MBにて、十進BASIC ２進モードで実行。
86 手
歩歩歩角 飛銀金銀
84 手
歩歩歩角 飛銀金銀
84 手
歩歩歩角 飛銀金銀
82 手
歩歩歩角 飛銀金銀
82 手
歩歩歩角 飛銀金銀
79 手
歩歩歩角 飛銀金銀
77 手
歩歩歩角 飛銀金銀
76 手
歩歩歩角 飛銀金銀
76 手
歩歩歩角 飛銀金銀
75 手
歩歩歩角 飛銀金銀
74 手
歩歩歩角 飛銀金銀
74 手
歩歩歩角 飛銀金銀
69 手
歩歩歩角 飛銀金銀
67 手
歩歩歩角 飛銀金銀
63 手
歩歩歩角 飛銀金銀
61 手
歩歩歩角 飛銀金銀
61 手
歩歩歩角 飛銀金銀
59 手
歩歩歩角 飛銀金銀
58 手
歩歩歩角 飛銀金銀
58 手
歩歩歩角 飛銀金銀
57 手
歩歩歩角 飛銀金銀
56 手
歩歩歩角 飛銀金銀
48 手
歩歩歩角 飛銀金銀
48 手
歩歩歩角 飛銀金銀
46 手
歩歩歩角 飛銀金銀
46 手
歩歩歩角 飛銀金銀
44 手
歩歩歩角 飛銀金銀
44 手
歩歩歩角 飛銀金銀
42 手
歩歩歩角 飛銀金銀
42 手
歩歩歩角 飛銀金銀
42 手
歩歩歩角 飛銀金銀
42 手
歩歩歩角 飛銀金銀
40 手
歩歩歩角 飛銀金銀
40 手
歩歩歩角 飛銀金銀
40 手
歩歩歩角 飛銀金銀
40 手
歩歩歩角 飛銀金銀
39 手
歩歩歩角 飛銀金銀
39 手
歩歩歩角 飛銀金銀
39 手
歩歩歩角 飛銀金銀
39 手
歩歩歩角 飛銀金銀
36 手
歩歩歩角 飛銀金銀
32 手
歩歩歩角 飛銀金銀
32 手
歩歩歩角 飛銀金銀
32 手
歩歩歩角 飛銀金銀
32 手
歩歩歩角 飛銀金銀
32 手
歩歩歩角 飛銀金銀
30 手
歩歩歩角 飛銀金銀
30 手
歩歩歩角 飛銀金銀
銀金 角銀飛歩歩歩
銀 金角銀飛歩歩歩
銀銀金角 飛歩歩歩
銀銀金角歩飛歩 歩
銀銀金 歩飛歩角歩
銀 金銀歩飛歩角歩
銀歩金銀 飛歩角歩
銀歩金銀飛 歩角歩
銀歩金銀飛角歩 歩
銀歩金銀 角歩飛歩
歩金銀銀角歩飛歩
銀歩金 銀角歩飛歩
銀歩金歩銀角 飛歩
銀歩金歩銀角飛 歩
銀歩金歩銀 飛角歩
銀歩 歩銀金飛角歩
銀歩銀歩 金飛角歩
歩銀歩銀金飛角歩
歩歩銀 銀金飛角歩
歩歩銀角銀金飛 歩
歩歩銀角銀金 飛歩
歩歩銀角 金銀飛歩
歩歩銀角金 銀飛歩
歩歩銀角金歩銀飛
歩歩銀角金歩銀 飛
歩歩銀角 歩銀金飛
歩歩 角銀歩銀金飛
歩歩歩角銀 銀金飛
歩歩歩角銀飛銀金
歩歩歩角 飛銀金銀
計算時間= 45.0900000000001 秒