1

私は騎士ツアーの再帰アルゴリズムを書こうとしています:

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 でそれ自体を呼び出す理由がわかりません。

4

1 に答える 1

0

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;
}
于 2013-09-19T06:16:20.393 に答える