The idea is to not continue searching under these conditions:

the next key is on the same row and two columns away, but the key in the middle has been visited;

the next key is on the same column but two rows away, but the key in the middle has been visited;

the next key is across the diagonal, but center key (1,1) has been visited;
public class Solution
{
public int NumberOfPatterns(int m, int n)
{
int res = 0;
bool[,] visited = new bool[3, 3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
res += Search(i, j, m, n, visited);
}
}return res; } private int Search(int i, int j, int m, int n, bool[,] visited) { if (visited[i, j]) { return 0; } if (n == 0) { return 1; } int res = 0; if (m <= 0) { res = 1; } visited[i, j] = true; for (int x = 0; x < 3; x++) { for (int y = 0; y < 3; y++) { if (!((x == i && Math.Abs(y  j) == 2 && !visited[i, 1])  (y == j && Math.Abs(x  i) == 2 && !visited[1, j])  (Math.Abs(x  i) == 2 && Math.Abs(y  j) == 2 && !visited[1, 1]))) { res += Search(x, y, m, n, visited); } } } visited[i, j] = false; return res; }
}