# C++ Naive Recursive solution. Naive but clear.

• ``````class Solution {
vector<int> used;
int min_l, max_l;
int solve(int f, int len)
{
if (len >= max_l)
return 1;
used[f] = 1;
int sum = 0;
for (int t = 1; t <= 9; ++t)
if (is_valid(f, t))
sum += solve(t, len + 1);
used[f] = 0;
if (len >= min_l)
sum++;
return sum;
}
bool is_valid(int f, int t)
{
if (f == t)
return false;
if (used[t])
return false;
int row_f = (f-1)/3, row_t = (t-1)/3;
int col_f = (f-1)%3, col_t = (t-1)%3;
if (row_f == row_t)
{
if (abs(col_f - col_t) == 1)
return true;
//if abs(col_f - col_t) == 2
return used[row_f * 3 + 1 + 1];
}
if (abs(row_f - row_t) == 1)
{
if (col_f == col_t)
return true;
if (abs(col_f - col_t) == 1)
return true;
//if abs(col_f - col_t) == 2
return true;//used[row_f * 3 + 1 + 1] && used[row_t * 3 + 1 + 1];
}
if (abs(row_f - row_t) == 2)
{
if (col_f == col_t)
return used[3 + col_f + 1];
if (abs(col_f - col_t) == 1)
return true;//used[3 + col_f + 1] && used[3 + col_t + 1];
//if abs(col_f - col_t) == 2
return used[5];
}
return false;
}
public:
int numberOfPatterns(int m, int n) {
used.resize(10);
min_l = m;
max_l = n;
int sum = 0;
for (int i = 1; i <= 9; ++i)
sum += solve(i, 1);
return sum;
}
};``````

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