# 20 lines, easy understand backtracking with explanations

• At the first glance, the description seems long and complicated. Actually, it can be simplified as:

• Connect two opposite corners, center should be already visited, such as 1-->9

• Connect two not-next-to-each-other cells vertically or horizontally, the in-between cell should be already visited. such as 4--->6

• Any cell not visited can be connected to.

`````` | 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
``````

The 9 cells can be divided into 3 groups: A(corner), B(middle), C(Center). We only need to calc once for each group.

``````| A | B | A |
| B | C | B |
| A | B | A |
``````

The code is a straightforward backtracking approach in C#,

``````public class Solution
{
public int NumberOfPatterns(int m, int n)
{
int[,] screen = new int[3,3];

int corner = 0, center = 0, middle = 0;
NumberOfPatternsUtil(screen, m, n, 0, 0, 1, ref corner);
NumberOfPatternsUtil(screen, m, n, 1, 1, 1, ref center);
NumberOfPatternsUtil(screen, m, n, 0, 1, 1, ref middle);

return (corner + middle) * 4 + center;
}

private void NumberOfPatternsUtil(int[,] screen, int m, int n, int x, int y, int keySequence, ref int result)
{
if(keySequence > n) return;
if(keySequence >= m && keySequence <= n) result ++;

screen[x,y] = keySequence;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(screen[i,j] == 0)
{
if(Math.Abs(x - i) == 2 && Math.Abs(y - j) == 2 && screen[1,1] == 0)continue;
if(x == i && Math.Abs(y - j) == 2 && screen[x, 1] == 0) continue;
if(y == j && Math.Abs(x - i) == 2 && screen[1, y] == 0) continue;

NumberOfPatternsUtil(screen, m, n, i, j, keySequence + 1, ref result);
}
}
}
screen[x,y] = 0; //backtracking
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.