Knight's Tour Бесконечный цикл - PullRequest
Новая
       42

Knight's Tour Бесконечный цикл

0 голосов
/ 08 февраля 2019

Я хотел проверить, хорошо ли я понимаю возвращение, поэтому я попробовал проблему рыцаря.Но мой код, похоже, не работает.Похоже, что это делает бесконечный цикл, так что, возможно, мое отслеживание пути не выполняется должным образом.Поэтому я хотел знать, чего мне не хватает в моем понимании проблемы. 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


#define N 8

int board[8][8]=  {

     -1,-1,-1,-1,-1,-1,-1,-1, //1
     -1,-1,-1,-1,-1,-1,-1,-1, //2
     -1,-1,-1,-1,-1,-1,-1,-1, //3
     -1,-1,-1,-1,-1,-1,-1,-1, //4
     -1,-1,-1,-1,-1,-1,-1,-1, //5
     -1,-1,-1,-1,-1,-1,-1,-1, //6
     -1,-1,-1,-1,-1,-1,-1,-1, //7
     -1,-1,-1,-1,-1,-1,-1,-1, //8


};

bool isSafe(int x, int y)
{
    return ( x >= 0 && x < N && y >= 0 &&
             y < N && board[x][y] == -1);
}

int SolveKnight_From_One_Point (int x,int y , int number_Moov) {

    if (number_Moov == N*N)
        return 1;

    if (isSafe(x,y)){
        board[x][y] = number_Moov;
        if (SolveKnight_From_One_Point(x-2,y+1,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x-2,y-1,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x-1,y+2,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x-1,y-2,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x+2,y-1,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x+2,y+1,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x+1,y+2,number_Moov+1)==1) {
            return 1;
        }
        if (SolveKnight_From_One_Point(x+1,y-2,number_Moov+1)==1) {
            return 1;
        }

        board[x][y] = -1;
    }

    return 0;
}



int main (){

    if (SolveKnight_From_One_Point(0,0,0)==1){
        printf(" Solution found :)\n");

    }
    printf("No solution :(\n");

    return 0;
}

1 Ответ

0 голосов
/ 08 февраля 2019

Для меня ваша программа работает, но нужно очень много времени, чтобы найти решение.

Всего два замечания:

Лучше инициализировать ваш массив так: 

int board[8][8]=  {
  { -1,-1,-1,-1,-1,-1,-1,-1}, //1
  { -1,-1,-1,-1,-1,-1,-1,-1}, //2
  { -1,-1,-1,-1,-1,-1,-1,-1}, //3
  { -1,-1,-1,-1,-1,-1,-1,-1}, //4
  { -1,-1,-1,-1,-1,-1,-1,-1}, //5
  { -1,-1,-1,-1,-1,-1,-1,-1}, //6
  { -1,-1,-1,-1,-1,-1,-1,-1}, //7
  { -1,-1,-1,-1,-1,-1,-1,-1}  //8
};

И заменить 

if (SolveKnight_From_One_Point(0,0,0)==1){
    printf(" Solution found :)\n");
}
printf("No solution :(\n");

на 

if (SolveKnight_From_One_Point(0,0,0)==1){
    printf(" Solution found :)\n");
}
else {
    printf("No solution :(\n");
}

, чтобы не всегда сказано Нет решения

Существует эвристическийчтобы решить проблему Правило Варнсдорфа в Википедии : Рыцарь перемещается так, что он всегда идет к клетке, от которой у рыцаря будет наименьшее количество ходов вперед.При подсчете количества ходов вперед для каждого квадрата-кандидата мы не учитываем ходы, которые повторно посещают любой квадрат, который уже посетили.Конечно, возможно иметь два или более вариантов, для которых число поступательных ходов равно

В конце моего ответа я даю предложение, используя эту эвристику

Небольшое изменение, чтобы увидеть прогресс в поиске: 

int SolveKnight_From_One_Point (int x,int y , int number_Moov) {
  static int max = 0;

  if (number_Moov > max) {
    int a,b;

    printf("%d moves\n", number_Moov);
    max = number_Moov;
    for (a = 0; a != N; ++a) {
      for (b = 0; b != N; ++b) {
        printf("%02d ", board[a][b]);
      }
      putchar('\n');
    }
    putchar('\n');
  }

  if (number_Moov == N*N)
      return 1;
  ...

Если я изменил N на 5, решение будет найдено немедленно: 

1 moves
00 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

2 moves
00 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 01 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

3 moves
00 -1 02 -1 -1 
-1 -1 -1 -1 -1 
-1 01 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

4 moves
00 -1 02 -1 -1 
-1 -1 -1 -1 -1 
-1 01 -1 03 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

5 moves
00 -1 02 -1 04 
-1 -1 -1 -1 -1 
-1 01 -1 03 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

6 moves
00 -1 02 -1 04 
-1 -1 05 -1 -1 
-1 01 -1 03 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

7 moves
00 -1 02 -1 04 
-1 -1 05 -1 -1 
-1 01 -1 03 -1 
-1 06 -1 -1 -1 
-1 -1 -1 -1 -1 

8 moves
00 -1 02 -1 04 
07 -1 05 -1 -1 
-1 01 -1 03 -1 
-1 06 -1 -1 -1 
-1 -1 -1 -1 -1 

9 moves
00 -1 02 -1 04 
07 -1 05 -1 -1 
-1 01 08 03 -1 
-1 06 -1 -1 -1 
-1 -1 -1 -1 -1 

10 moves
00 -1 02 09 04 
07 -1 05 -1 -1 
-1 01 08 03 -1 
-1 06 -1 -1 -1 
-1 -1 -1 -1 -1 

11 moves
00 -1 02 09 04 
07 -1 05 -1 -1 
-1 01 08 03 10 
-1 06 -1 -1 -1 
-1 -1 -1 -1 -1 

12 moves
00 -1 02 09 04 
07 -1 05 -1 -1 
-1 01 08 03 10 
-1 06 -1 -1 -1 
-1 -1 -1 11 -1 

13 moves
00 -1 02 09 04 
07 -1 05 12 -1 
-1 01 08 03 10 
-1 06 11 -1 -1 
-1 -1 -1 -1 -1 

14 moves
00 13 02 09 04 
07 -1 05 12 -1 
-1 01 08 03 10 
-1 06 11 -1 -1 
-1 -1 -1 -1 -1 

15 moves
00 13 02 09 04 
07 -1 05 12 -1 
14 01 08 03 10 
-1 06 11 -1 -1 
-1 -1 -1 -1 -1 

16 moves
00 13 02 09 04 
07 -1 05 12 -1 
14 01 08 03 10 
-1 06 11 -1 -1 
-1 15 -1 -1 -1 

17 moves
00 13 02 09 04 
07 -1 05 12 -1 
14 01 08 03 10 
-1 06 11 16 -1 
-1 15 -1 -1 -1 

18 moves
00 13 02 09 04 
07 -1 05 12 17 
14 01 08 03 10 
-1 06 11 16 -1 
-1 15 -1 -1 -1 

19 moves
00 17 02 09 04 
07 12 05 16 -1 
18 01 08 03 10 
13 06 11 -1 15 
-1 -1 14 -1 -1 

20 moves
00 17 02 09 04 
07 12 05 16 -1 
18 01 08 03 10 
13 06 11 -1 15 
-1 19 14 -1 -1 

21 moves
00 17 02 09 04 
07 12 05 16 -1 
18 01 08 03 10 
13 06 11 20 15 
-1 19 14 -1 -1 

22 moves
00 17 02 09 04 
07 12 05 16 21 
18 01 08 03 10 
13 06 11 20 15 
-1 19 14 -1 -1 

23 moves
00 13 02 19 04 
07 18 05 14 09 
12 01 08 03 20 
17 06 21 10 15 
-1 11 16 -1 22 

24 moves
00 11 02 19 06 
15 20 05 10 03 
12 01 14 07 18 
21 16 09 04 23 
-1 13 22 17 08 

25 moves
00 17 02 11 20 
07 12 19 16 03 
18 01 06 21 10 
13 08 23 04 15 
24 05 14 09 22 

 Solution found :)

С Nназад 8 первые 60 ходов выполняются немедленно, затем они становятся все длиннее 

1 movs
00 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

2 movs
00 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

3 movs
00 -1 02 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

4 movs
00 -1 02 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 03 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

5 movs
00 -1 02 -1 04 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 03 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

6 movs
00 -1 02 -1 04 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 03 -1 05 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

7 movs
00 -1 02 -1 04 -1 06 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 03 -1 05 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

8 movs
00 -1 02 -1 04 -1 06 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 01 -1 03 -1 05 -1 07 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

9 movs
00 -1 02 -1 04 -1 06 -1 
-1 -1 -1 -1 -1 08 -1 -1 
-1 01 -1 03 -1 05 -1 07 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

10 movs
00 -1 02 -1 04 -1 06 09 
-1 -1 -1 -1 -1 08 -1 -1 
-1 01 -1 03 -1 05 -1 07 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 -1 

...    

60 movs
00 15 02 13 04 11 06 09 
-1 24 17 22 -1 08 29 -1 
16 01 14 03 12 05 10 07 
25 18 23 38 21 28 33 30 
46 55 20 27 32 37 40 35 
19 26 45 56 39 34 31 50 
54 47 58 43 52 49 36 41 
59 44 53 48 57 42 51 -1 

61 movs
00 15 02 13 04 11 06 09 
-1 24 17 22 31 08 33 60 
16 01 14 03 12 05 10 07 
25 18 23 30 21 32 59 34 
52 29 20 27 58 45 38 41 
19 26 51 44 55 40 35 46 
50 53 28 57 48 37 42 39 
-1 -1 49 54 43 56 47 36 

62 movs
00 15 02 13 04 11 06 09 
-1 24 17 22 33 08 31 -1 
16 01 14 03 12 05 10 07 
25 18 23 34 21 32 49 30 
44 59 20 27 48 29 36 53 
19 26 45 56 35 52 39 50 
58 43 60 47 28 41 54 37 
61 46 57 42 55 38 51 40 

63 movs
00 15 02 13 04 11 06 09 
-1 24 17 22 35 08 33 62 
16 01 14 03 12 05 10 07 
25 18 23 36 21 34 61 32 
56 37 20 29 60 31 52 43 
19 26 57 40 53 44 49 46 
38 55 28 59 30 47 42 51 
27 58 39 54 41 50 45 48

(вычисления не завершены через 6 часов)

Модификация вашей программыиспользуя эвристику Варнсдорфа: 

#include <stdio.h>

#define N 8

int Board[8][8]=  {
  { -1,-1,-1,-1,-1,-1,-1,-1}, //1
  { -1,-1,-1,-1,-1,-1,-1,-1}, //2
  { -1,-1,-1,-1,-1,-1,-1,-1}, //3
  { -1,-1,-1,-1,-1,-1,-1,-1}, //4
  { -1,-1,-1,-1,-1,-1,-1,-1}, //5
  { -1,-1,-1,-1,-1,-1,-1,-1}, //6
  { -1,-1,-1,-1,-1,-1,-1,-1}, //7
  { -1,-1,-1,-1,-1,-1,-1,-1}  //8
};

typedef struct DxDy {
  int dx;
  int dy;
} DxDy;

#define NDEPLS 8

const DxDy Depls[NDEPLS] = { {-2,1}, {-2,-1}, {-1,2}, {-1,-2}, {2,-1}, {2,1}, {1,2} , {1,-2} };


int isSafe(int x, int y)
{
  return ((x >= 0) && (x < N) &&
          (y >= 0) && (y < N) && 
          (Board[x][y] == -1));
}

int nchoices(int x, int y)
{
  int r = 0;
  int i;

  for (i = 0; i != NDEPLS; ++i) {
    if (isSafe(x + Depls[i].dx, y + Depls[i].dy))
      r += 1;
  }

  return r;
}

void pr()
{
  int a, b, c;

  for (a = 0; a != N; ++a) {
    for (c = 0; c != 2; c++) {
      for (b = 0; b != N; ++b)
        printf(((a ^ b) & 1) ? "********" : "        ");
      putchar('\n');
    }
    for (b = 0; b != N; ++b)
      printf(((a ^ b) & 1) ? "***%2d***" : "   %2d   ", Board[a][b]);
    putchar('\n');
    for (c = 0; c != 2; c++) {
      for (b = 0; b != N; ++b)
        printf(((a ^ b) & 1) ? "********" : "        ");
      putchar('\n');
    }
  }
  putchar('\n');
}

int SolveKnight_From_One_Point(int x, int y , int number_Moov)
{
  Board[x][y] = number_Moov;
  number_Moov += 1;

  int i, fx[NDEPLS], fy[NDEPLS], mins[NDEPLS];
  int imin = 0;
  int min = NDEPLS+1;

  for (i = 0; i != NDEPLS; ++i) {
    int nx = x + Depls[i].dx;
    int ny = y + Depls[i].dy;

    if (isSafe(nx, ny)) {
      Board[nx][ny] = number_Moov;

      if (number_Moov == (N*N - 1)) {
        puts("Done");
        pr();
        return 1;
      }

      int n = nchoices(nx, ny);

      if ((n != 0) && (n < min)) {
        mins[imin] = min = n;
        fx[imin] = nx;
        fy[imin] = ny;
        imin += 1;
      }

      Board[nx][ny] = -1;
    }
  }

  while (imin-- != 0) {
    if ((mins[imin] == min) && 
        SolveKnight_From_One_Point(fx[imin], fy[imin], number_Moov))
      return 1;
  }

  Board[x][y] = -1;

  return 0;
}



int main ()
{
  if (SolveKnight_From_One_Point(0, 0, 0))
    printf("Solution found :)\n");
  else
    printf("No solution :(\n");

  return 0;
}

На этот раз решение найдено немедленно: 

pi@raspberrypi:~ $ ./a.out
Done
        ********        ********        ********        ********
        ********        ********        ********        ********
    0   ***21***    2   ***17***   24   ***29***   12   ***15***
        ********        ********        ********        ********
        ********        ********        ********        ********
********        ********        ********        ********        
********        ********        ********        ********        
*** 3***   18   ***23***   28   ***13***   16   ***33***   30   
********        ********        ********        ********        
********        ********        ********        ********        
        ********        ********        ********        ********
        ********        ********        ********        ********
   22   *** 1***   20   ***25***   48   ***31***   14   ***11***
        ********        ********        ********        ********
        ********        ********        ********        ********
********        ********        ********        ********        
********        ********        ********        ********        
***19***    4   ***55***   38   ***27***   34   ***49***   32   
********        ********        ********        ********        
********        ********        ********        ********        
        ********        ********        ********        ********
        ********        ********        ********        ********
   56   ***39***   26   ***47***   60   ***53***   10   ***35***
        ********        ********        ********        ********
        ********        ********        ********        ********
********        ********        ********        ********        
********        ********        ********        ********        
*** 5***   42   ***59***   54   ***37***   46   ***63***   50   
********        ********        ********        ********        
********        ********        ********        ********        
        ********        ********        ********        ********
        ********        ********        ********        ********
   40   ***57***   44   *** 7***   52   ***61***   36   *** 9***
        ********        ********        ********        ********
        ********        ********        ********        ********
********        ********        ********        ********        
********        ********        ********        ********        
***43***    6   ***41***   58   ***45***    8   ***51***   62   
********        ********        ********        ********        
********        ********        ********        ********        

Solution found :)
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...