Knights tour recursive

Question

I'm trying to write knights tour recursive algorithm:

int mov[8][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};

typedef struct element {
    int x;
    int y;
    struct element *prev, *next;
} node; 

//adding pool to list
void dEnd(node **root, int x,int y)
{
    node *pos;
    pos = *root;
    while(pos->next!= NULL)
    pos = pos->next;
    pos->next = (node *)malloc(sizeof(node));
    pos->next->x=x;
    pos->next->y=y;
    pos->next->prev=pos;
    pos->next->next=NULL;
}

void uEnd(node **root,int x,int y)
{
    node *pos;
    pos = *root;
    while(pos->x!= x && pos->y !=y)
    {
        pos = pos->next;
    }
    pos->prev->next=NULL;
    free(pos);
}

void printAll(node **root)
{
    node *pos = *root;
    while(pos->next)
    {
        printf("%d %d\n", pos->x,pos->y);
        pos = pos->next;
    }
}

int contains(int x,int y)
{
    return(((x >= 0 ) && (x <= 7)) && ((y >= 0) && (y <= 7)));
}
//find move
int searchForMove(int x, int y, int **tab, node **list, int *number)
{

    int i ;
    for(i = 0; i < 8; i++)
    {
        int nx, ny;
        nx = x + mov[i][0];
        ny = y + mov[i][1];
        if(contains(nx, ny) && !tab[nx][ny])
        {
            dEnd(list, nx, ny);
            tab[nx][ny] = 1;
            *number++;
            if(!searchForMove(nx,ny,tab,list,number))
            {
                uEnd(list,nx,ny);
                tab[nx][ny]=0;
                *number--;
            }
        }
    }
    if(i == 7 && *number <64)
        return 0;
    if(*number == 64)
        return 1;
}

Could someone show me where I made a mistake? I've checked step by step what pools algorithm is adding to list. What is big suprise algorithm after adding 4,3 pool and then 6,4 pool should call it self with 6,4 as actual position but I don't know why it's calling itself with 4,3 as actual position.

Answer 1

OP mostly had it. Aside from some minor code, it was the *number increment/decrement that was wrong in 2 places.

int searchForMove(int x, int y, int **tab, node **list, int *number) {
  ...
  // *number++;  // This increase the pointer to the next pointer.
  (*number)++; // This dereferences number and increases it.
  ...
    // *number--;
    (*number)--; // CD

---

Working Example. "CD" implies my changes

// CD
#include <assert.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int mov[8][2] = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 },
        { -1, 2 }, { 1, -2 }, { -1, -2 } };

typedef struct element {
  int x;
  int y;
  struct element *prev, *next;
} node;

//adding pool to list
void dEnd(node **root, int x, int y) {
  node *pos;
  pos = *root;
  assert(pos); // CD
  while (pos->next != NULL)
    pos = pos->next;
  pos->next = (node *) malloc(sizeof(node));
  pos->next->x = x;
  pos->next->y = y;
  pos->next->prev = pos;
  pos->next->next = NULL;
}

void uEnd(node **root, int x, int y) {
  node *pos;
  pos = *root;
  while (pos->x != x && pos->y != y) {
    pos = pos->next;
  }
  pos->prev->next = NULL;
  free(pos);
}

void printAll(node **root) {
  node *pos = *root;
  unsigned i = 0; // CD
  uint64_t mask = 0; // CD
  while (pos->next) {
    // printf("%d %d\n", pos->x, pos->y);
    printf("%2u %d %d\n", i++, pos->x, pos->y); // CD prepend visit index.
    mask |= 1llu << (pos->x + 8*pos->y); // CD accumulate visited squares
    pos = pos->next;
  }
  printf("Mask %016" PRIX64 "\n", mask); // CD Show all locations visited
}

int contains(int x, int y) {
  return (((x >= 0) && (x <= 7)) && ((y >= 0) && (y <= 7)));
}

//find move
int searchForMove(int x, int y, int **tab, node **list, int *number) {
  int i;
  for (i = 0; i < 8; i++) {
    int nx, ny;
    nx = x + mov[i][0];
    ny = y + mov[i][1];
    if (contains(nx, ny) && !tab[nx][ny]) {
      dEnd(list, nx, ny);
      tab[nx][ny] = 1;

      // *number++;
      (*number)++; // CD

      if (!searchForMove(nx, ny, tab, list, number)) {
        uEnd(list, nx, ny);
        tab[nx][ny] = 0;

        // *number--;
        (*number)--; // CD

      }
    }
  }
  if (i == 7 && *number < 64)
    return 0;
  if (*number == 64)
    return 1;
  return 2;  // CD added
}

// All added by CD
int main(int argc, char *argv[]) {
  int tab0[8] = {0,0,0,0,0,0,0,0};
  int tab1[8] = {0,0,0,0,0,0,0,0};
  int tab2[8] = {0,0,0,0,0,0,0,0};
  int tab3[8] = {0,0,0,0,0,0,0,0};
  int tab4[8] = {0,0,0,0,0,0,0,0};
  int tab5[8] = {0,0,0,0,0,0,0,0};
  int tab6[8] = {0,0,0,0,0,0,0,0};
  int tab7[8] = {0,0,0,0,0,0,0,0};
  int *tab[8] = {tab0, tab1, tab2, tab3, tab4, tab5, tab6, tab7 };
  node HeadNode = { 0, 0, NULL, NULL };
  node *pHeadNode = &HeadNode;
  int number = 0;
  int result;
  result = searchForMove(0, 0, tab, &pHeadNode, &number);
  printAll(&pHeadNode);
  return result;
}