OEIS A300665

a300665.cc

// Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
// OEIS A300665
// Ricardo Bittencourt, March 11 2018

#include <iostream>
#include <vector>

using namespace std;

struct Grid {
  Grid(int size) : n(size), grid(size, vector<bool>(size, false)) {
  }
  long long count() {
    return search(0, 0, n);
  }
  long long search(int j, int i, int left) {
    if (left == 1) {
      return 1;
    }
    grid[j][i] = true;
    long long total = 0;
    for (int k = 0; k < 8; k++) {
      int ii = i + di[k];
      int jj = j + dj[k];
      if (ii < 0 || jj < 0 || grid[jj][ii]) {
        continue;
      }
      total += search(jj, ii, left - 1);
    }
    grid[j][i] = false;
    return total;
  }
  int n;
  vector<vector<bool>> grid;
  constexpr static int di[8] = {-1,  0,  1, -1, 1, -1, 0, 1};
  constexpr static int dj[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
};

int main() {
  int n;
  cin >> n;
  Grid grid(n);
  cout << grid.count();
  return 0;
}

For the knight theoreticallty we only need to change the di,dj arrays, right?

// Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
// OEIS A300665
// Ricardo Bittencourt, March 11 2018

#include <iostream>
#include <vector>

using namespace std;

const static int di[8] = {-2, -1,  2, 1, 2, 1,  -1 -2};
const static int dj[8] = {-1, -2,  1, 2, -1, -2, 2, 1};
struct Grid {
  Grid(int size) : n(size), grid(size, vector<bool>(size, false)) {
  }
  long long count() {
    return search(0, 0, n);
  }
  long long search(int j, int i, int left) {
    if (left == 1) {
      return 1;
    }
    grid[j][i] = true;
    long long total = 0;
    for (int k = 0; k < 8; k++) {
      int ii = i + di[k];
      int jj = j + dj[k];
      if (ii < 0 || jj < 0 || grid[jj][ii]) {
        continue;
      }
      total += search(jj, ii, left - 1);
    }
    grid[j][i] = false;
    return total;
  }
  int n;
  vector<vector<bool>> grid;
};

int main() {
  int n;
  cin >> n;
  Grid grid(n);
  cout << grid.count() << endl;
  return 0;
}