c - 骑士之旅无限循环-6ren

c - 骑士之旅无限循环

转载作者：行者123 更新时间：2023-11-30 19:59:45

我想测试一下我是否理解回溯，所以我尝试了骑士问题。但我的代码似乎不起作用。它似乎做了一个无限循环，所以也许我对路径的跟踪执行得不好。所以我想知道我在理解这个问题时错过了什么。

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

最佳答案

对我来说，你的程序可以工作，但需要很长时间才能找到解决方案。

简单说两句:

最好像这样初始化数组:

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

并不总是说没有解决方案

<小时/>

有一个启发式方法可以解决问题Warnsdorf's rule in Wikipedia :马被移动，以便它始终前进到马向前移动最少的方格。在计算每个候选方格的向前移动次数时，我们不会计算重新访问任何已访问过的方格的移动次数。当然，可以有两个或多个向前移动次数相等的选择

在回答的最后，我使用该启发式给出了一个建议

<小时/>

稍作更改即可查看搜索进度:

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 back 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小时后计算未完成)

<小时/>

使用 Warnsdorf 启发法对程序进行修改:

#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 :)

关于c - 骑士之旅无限循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54591797/

文章推荐： c# - 在 For 循环中格式化字符串生成器

文章推荐： javascript - AngularJS ng-repeat map (对象)不实时更新 DOM

文章推荐： c# - 无法在第二台计算机上解密数据

node.js - 未处理的拒绝错误 - 骑士
我尝试运行稍微修改过的 horsemanjs 的示例代码: var Horseman = require('node-horseman'); var horseman = new Horseman()
three.js - 如何使用threejs创建轴测斜/骑士/橱柜？
我在 Isometric camera with THREE.js 中找到了有关如何创建(轴测)等距相机的示例，但如何创建轴测斜线？最佳答案您可以渲染带有倾斜的场景 cabinet perspec
javascript - 有 promise 的 Node 骑士
我正在尝试在 horseman 的 evalute 函数中使用 promises。一个简单的例子: var Horseman = require('node-horseman'); var horse
c# - JetBrain 骑士 : viewing List<> during debugging
我试图在调试期间查看 List<> 的内容。不幸的是我看不到它们，因为我在变量窗口中收到以下消息: corvalue.GetExactTypeSafe(out type). The object is
c# - 团结/骑士: order of multiplication operations is inefficient?
Rider IDE 通知我以下内容效率低下 transform.Translate(moveDirection * speed * Time.smoothDeltaTime); 并想将
entity-framework - 骑士。 EF Code First 迁移
是否有一种简单的方法可以在 Visual Studio 之外使用旧的 EF 来搭建脚手架迁移？如果可能的话，我想通过 Rider IDE 来完成。最佳答案对于 EF Core，您可以使用 http
.net - Jetbrains 骑士 : Show "external code" in debugger call stack
在 Rider 中，当在断点处暂停时，有没有办法在调试器堆栈帧中实际显示“外部代码”？在 Visual Studio 中，这可以轻松完成，但在 Rider 中似乎不可能。而且，是的，我启用了“exa
environment-variables - JetBrains 骑士 : Can't change environment variable in a project profile
我试图通过更改其环境变量来修改 Linux 上 JetBrains Rider 中 .NET 项目的设置配置文件。但是，当我点击文件夹图标时，我无法点击添加、删除或修改任何环境变量。我注意到在 Ri
android - 骑士 Xamarin 错误 MSB1008 : Only one project can be specified
只是试用 Rider 并遇到了这个问题，如果我只是构建 Xamarin Android 项目 - 它构建得非常好，但是如果我尝试运行它，它会在部署步骤失败并出现以下错误: ▼ Project Not
asp.net-core - Jetbrains 骑士 : [MSB4057] The target "build" does not exist in the project
当我在 Jetbrains Rider EAP 21 中创建解决方案时，我在解决方案资源管理器窗口中收到“(缺少包)”错误。然后，我尝试构建项目并获得 [MSB4057] 错误。尽管如此，我可以通

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

c - 骑士之旅无限循环