# Java solution, 60+ ms

• ``````public int numberOfPatterns(int m, int n) {
boolean[][] visited = new boolean[3][3];
int ret = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
ret += backtracking(m, n, visited, i, j, 0);
}
}
return ret;
}

private int backtracking(int m, int n, boolean[][] visited, int y, int x, int cur) {
visited[y][x] = true;
cur++;
int count = 0;
if (cur >= m && cur <= n) {
count++;
}
if (cur == n) {
visited[y][x] = false;
return count;
}

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == y && j == x) { continue; }
if (visited[i][j]) { continue; }
int dx = j - x;
int dy = i - y;
/* neighbors */
if ((Math.abs(dx) <= 1 && Math.abs(dy) <= 1)
/* not in the same line */
|| (x != j && y != i // same row or col
&& y - x != i - j // l2r, high
&& x - y != j - i // l2r, low
&& x + y != j + i) // r2l
/* same line but not neighbors */
|| visited[y + dy/2][x + dx/2]) {
count += backtracking(m, n, visited, i, j, cur);
}
}
}
visited[y][x] = false;
return count;
}``````

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