Self-avoiding Walk

I came across this interesting problem when I was implementing the game: squirrel and acorn and was wondering how many different paths are there for the squirrel to move from the top left to the bottom right without revisiting the same square twice.

Here is a summary of the result:

Square	Number of paths
1 x 1	1
2 x 2	2
3 x 3	12
4 x 4	184
5 x 5	8512
6 x 6	1262816

---

What is a self-avoiding walk?

A self-avoiding walk is a path from one point to another which never intersects itself.

Self-avoiding rook walks are walks on an m×n grid which start from (0,0), end at (m,n), and are composed of only horizontal and vertical steps.

The values for m=n=1, 2, ... are 2, 12, 184, 8512, 1262816, ...

I wrote some scripts to compute the value: