Faster way to solve android lock valid patterns

It is possible to speed up your existing code even without compilation. The idea is to count not all configurations, but rather the topologically different ones.

There are 3 topologically distinct possibilities to start a path

1. Corner: 1, 3, 7, 9
2. Edge: 2, 4, 6, 8
3. Center: 5

Thus, it is sufficient to count the number of paths starting from 1 (n[1]), starting from 2 (n[2]) and starting from 5 (n[5]). The total number of configurations is given by the sum weighted with symmetry factors.

I keep your definitions of list and ps and perform timing of each part of the algorithm.

(x=Permutations[Range[9],{4,9}];)//AbsoluteTiming
Out[3]= {0.145363,Null}

(y[1]=Cases[x,{1,___}];
 y[2]=Cases[x,{2,___}];
 y[5]=Cases[x,{5,___}];)//AbsoluteTiming
Out[4]= {0.3311,Null}

Fold[Cases,x,ps]//Length//AbsoluteTiming
Out[5]= {13.6685,389112}

(n[1]=Fold[Cases,y[1],ps]//Length)//AbsoluteTiming
(n[2]=Fold[Cases,y[2],ps]//Length)//AbsoluteTiming
(n[5]=Fold[Cases,y[5],ps]//Length)//AbsoluteTiming

Out[6]= {1.40567,38042}
Out[7]= {1.60751,43176}
Out[8]= {1.71645,64240}

4n[1]+4n[2]+n[5]
Out[9]= 389112 

Discussion

The results of the timing with respect to the original algorithm are as follows:

1. Generation of all configurations 1%.
2. Selection of the corner, edge and center classes 2%.
3. Brute-force selection of the valid configurations 99%.
4. Selection of valid paths starting at the corner 10%, the edge 12%, and the center 12%.

Even with this simplest idea the achieved time saving is 65%. This approach can be systematically extended further depending on the time one wants to invest in the topological analysis.

Challenge

This problem can be easily generalized to any $n\times n$ grid. However, only for $3\times 3$ and $4\times 4$ the solution is known. Can someone compute the $5\times 5$ number ?

In the same manner as yarchik's answer, but leveraging more symmetries.

Also using ps as defined in the question.

t = {2, 6};
u = {3, 6, 9};

eightfoldStarts = Thread /@
    {{1, t}, {1, 5, {2, 3, 6}}, {1, 5, 9, t},
     {2, u}, {2, 5, u}, {2, 5, 8, u},
     {5, 1, t}, {5, 1, 9, t}, {5, 2, u}, {5, 2, 8, u}} // Catenate;

finish[s : {__Integer}] :=
  Join[s, #] & /@ Permutations[Complement[Range@9, s], {4 - Length@s, 9}];

filter[s : {__Integer}] := Fold[Cases, finish@s, ps]

8 Total[Length@*filter /@ eightfoldStarts] // AbsoluteTiming

{1.15843, 389112}

There is a more concise and slightly faster pattern matching solution:

impossible = {{1, 3}, {3, 1}, {4, 6}, {6, 4}, {7, 9}, {9, 7}, {1, 
   7}, {7, 1}, {2, 8}, {8, 2}, {3, 9}, {9, 3}, {1, 9}, {9, 1}, {3, 
   7}, {7, 3}};
possible = Permutations[Range[9], {4, 9}];

Count[possible, {___, PatternSequence @@@ Alternatives @@ impossible, ___}];

This takes around 7.22 seconds on my machine, against 11.24 seconds for your pattern matching solution. (By the way, you should use RepeatedTiming, not AbsoluteTiming, for more accurate timing results!)

Edit 1: Ah, OrdlessPatternSequence is a thing.

Count[possible,
  {___, OrderlessPatternSequence @@@ 
    Alternatives @@ {{1, 3}, {4, 6}, {7, 9}, {1, 7}, {2, 8}, {3, 
       9}, {1, 9}, {3, 7}}, ___}
  ]

Takes 5.24 seconds on my machine.