骑士之旅递归

Question

我想写骑士巡逻递归算法：

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; 
} 

有人能告诉我，我犯了一个错误？我已经逐步检查了哪些池算法正在添加到列表中。什么是加入4,3池之后的大惊喜算法，然后6,4池应该用6,4作为自己的实际位置来调用它自己，但我不知道为什么它以4,3作为实际位置调用自己。

Answer 1

OP大部分都有。除了一些次要的代码之外，它在*number增加/减少了2个地方是错误的。

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 

---

工作实施例。 “CD”意味着我的更改

// 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; 
}