骑士之旅

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大部分都有。除了一些次要的代码之外，在两个地方错误的是*数字增量/减量。

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