public int numberOfPatterns(int m, int n) {
// Skip represents the number to skip between two numbers
int[][] skip = new int[10][10];
skip[1][3] = skip[3][1] = 2;
skip[7][9] = skip[9][7] = 8;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3] = skip[2][8] = skip[8][2]
= skip[4][6] = skip[6][4] = 5;
boolean[] visited = new boolean[10];
for (int i = m; i <= n; i++) {
res += searchPatterns(visited, skip, 1, i - 1) * 4; // 1, 3, 7, 9 are symmetric
res += searchPatterns(visited, skip, 2, i - 1) * 4; // 2, 4, 6, 8 are symmetric
res += searchPatterns(visited, skip, 5, i - 1);
public int searchPatterns(boolean[] visited, int[][] skip, int curNum, int steps) {
for (int nextNum = 1; nextNum <= 9; nextNum++) {
// if nextNum is not visited and (curNum is adjacent to nextNum or their skip number is visited)
if (!visited[nextNum] && (skip[curNum][nextNum] == 0 || visited[skip[curNum][nextNum]])) {
res += searchPatterns(visited, skip, nextNum, steps - 1);