Knight's Tour

#include <LedControl.h>
LedControl lc = LedControl(12, 11, 10, 1); //11 is to CLOCK, 10 = CS, 12=DIN

#define N 8

int is_valid(int i, int j, int sol[N + 1][N + 1]) {
  if (i >= 1 && i <= N && j >= 1 && j <= N && sol[i][j] == -1)
    return 1;
  return 0;
}

int knight_tour(int sol[N + 1][N + 1], int i, int j, int step_count, int x_move[], int y_move[]) {
  if (step_count == N * N)
    return 1;

  int k;
  for (k = 0; k < N; k++) {
    int next_i = i + x_move[k];
    int next_j = j + y_move[k];

    if (is_valid(i + x_move[k], j + y_move[k], sol)) {
      sol[next_i][next_j] = step_count;
      if (knight_tour(sol, next_i, next_j, step_count + 1, x_move, y_move))
        return 1;
      sol[i + x_move[k]][j + y_move[k]] = -1; // backtracking
    }
  }

  return 0;
}

int start_knight_tour() {
  int sol[N + 1][N + 1];

  int i, j;
  for (i = 1; i <= N; i++) {
    for (j = 1; j <= N; j++) {
      sol[i][j] = -1;
    }
  }

  int x_move[] = {2, 1, -1, -2, -2, -1, 1, 2};
  int y_move[] = {1, 2, 2, 1, -1, -2, -2, -1};

  sol[1][1] = 0; // placing knight at cell(1, 1)

  if (knight_tour(sol, 1, 1, 1, x_move, y_move)) {
    int cnt = 0;
    while (cnt <= N * N) {
      for (i = 1; i <= N; i++) {
        for (j = 1; j <= N; j++) {
          if (sol[i][j] == cnt) {
            delay(1500);
            lc.setLed(0, i - 1, j - 1, true);
            cnt = cnt + 1;
          }
        }
      }
    }
    return 1;
  }
  return 0;
}

void setup() {
  Serial.begin(9600);
  lc.shutdown(0, false);
  lc.setIntensity(0, 2);
  lc.clearDisplay(0);
  lc.setLed(0, 0, 0, true);
  int out = start_knight_tour();
}

void loop() {
  //lc.clearDisplay(0);
  //delay(100);
}