Ok, here comes the complete solution.
You will have noticed that every path passes through the central "C".
We can split the problem in two halves: from border to center and from center to border.
If we are able to count the paths in one of the two halves, we can calculate the total number of paths N.
Let us call C1 the number of paths from any "W" on the border to the central "C",
and C2 the number of paths from the central "C" to any "W" on the border.
If you consider that if you reverse the direction of the paths making up C1 you get all the paths making up C2,
you obtain that
C1 = C2 = C
Now, for every path that reaches the center, there will be C paths to continue it back to the border.
This means that the total number of paths is the number of paths reaching the center multiplied by the number of paths leaving it.
In a less verbose fashion, calling N the total number of paths:
N = C2
Ok, now we only have to calculate C.
We have the choice between calculating C1 or C2.
It turns out that C2 is easier to calculate.
Again, we split the problem, this time in 4 quarters: every path from center to border belongs to one of four quadrants.
Once the path has left the cross with horizontal and vertical arms that meet at the "C", it cannot touch it again.
This cross segregates the paths into four quadrants, and, because of symmetry, the number Q of paths in each quadrant is the same:
Q1 = Q2 = Q3 = Q4 = Q
If Q includes, for every quadrant, both the fully horizontal and the fully vertical path (the paths on the boundary cross),
we are counting each path on the boundary between quadrants twice.
If we sum up the paths of the four quadrants, we will have to subtract these boundary paths that have been counted double:
C = 4 Q − 4 = 4 (Q − 1)
Our last task is to calculate Q.
Let us focus on the upper right quadrant.
From the "C", we have the choice between going up or going right.
We have this same choice from the "A" and from every following letter, until we reach a "W", where our journey ends.
This means that at every step the number of paths doubles (and, of course, they all remain distinct).
We have 6 steps in our case, but let us be generic, as scientists like to be, and let us say that there are S steps:
Q = 2 × 2 × ... 2 (S times) = 2S
Putting it all together we have (staying generic):
N = C2 = (4 (Q − 1))2 = 16 (Q − 1)2 = 16 (2S − 1)2
So in our case, where S = 6, we have:
N = 16 (26 − 1)2 = 16 × 632 = 63504
But you will have noticed that you can build the same scheme on any palindrome (word or phrase that reads both left to right and right to left).
For a palindrome of length L there are (L − 1) / 2 steps from center to border, so that the generic formula is:
N = 16 (2(L − 1) / 2 − 1)2