论坛 › 数据结构与算法 › 小甲鱼课后作业S1E36马踏棋盘问题

飞花落尽 发表于 2021-12-10 23:06:20

小甲鱼课后作业S1E36马踏棋盘问题

请问各位大佬们，我的回溯算法为什么会死循环？
#include <stdio.h>

const int step = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-1,2},{-2,1},{1,2},{2,1}};
int array = {0};
int end(int (*array));

int run(int row,int col,int (*array))
{
        int i;
        printf("%2d ",(row - 1) * 8 + col);
        if (end(array))
        {
                printf("success");
                return 1;
        }
        for (i = 0;i < 8;i++)
        {
                if (row + step >= 1 && col + step >= 1 && row + step <= 8 && col + step <= 8 && !array - 1] - 1])
                {
                        array - 1] - 1] = (row + step - 1) * 8 + (col + step);
                        run(row + step,col + step,array);
                        printf("\b\b\b   ");
                        array - 1] - 1] = 0;
                }
        }
        return 0;
}

int end(int (*array))
{
        for (int i = 0;i < 8;i++)
        {
                for (int j = 0;j < 8;j++)
                {
                        if (!array)
                        {
                                return 0;
                        }
                }
        }
        return 1;
}

int main(void)
{
        int row,col;
        printf("请输入行数：");
        scanf("%d",&row);
        printf("请输入列数：");
        scanf("%d",&col);
        array = (row - 1) * 8 + col;
        run(row,col,array);
       
        return 0;
}

人造人 发表于 2021-12-10 23:06:21

你代码逻辑就是错的吧？
还有写代码不认真
#include <stdio.h>

const int step = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-1, 2}, {-2, 1}, {1, 2}, {2, 1}};
int array = {0};
int end(int (*array));

int run(int row, int col, int (*array)) {
    int i;
    //printf("%2d ", (row - 1) * 8 + col);
    if(end(array)) {
      //printf("success");
      printf("success\n");
      return 1;
    }
    for(i = 0; i < 8; i++) {
      if(row + step >= 1 && col + step >= 1 &&
         // 认真一点
         //row + step <= 8 && col + step <= 8 &&
         row + step <= 8 && col + step <= 8 &&
         !array - 1] - 1]) {
            array - 1] - 1] =
                (row + step - 1) * 8 + (col + step);

            // 上面都减1，这里怎么不减1了？
            //run(row + step, col + step, array);
            run(row + step - 1, col + step - 1, array);
            //printf("\b\b\b   ");
            array - 1] - 1] = 0;
      }
    }
    return 0;
}

int end(int (*array)) {
    for(int i = 0; i < 8; i++) {
      for(int j = 0; j < 8; j++) {
            if(!array) {
                return 0;
            }
      }
    }
    return 1;
}

int main(void) {
    int row, col;
    printf("请输入行数：");
    scanf("%d", &row);
    printf("请输入列数：");
    scanf("%d", &col);

    // 这是在做什么？
    array = (row - 1) * 8 + col;

    run(row, col, array);

    return 0;
}

飞花落尽 发表于 2021-12-11 09:54:43

step = [[-1,-2],,[-2,-1],,[-1,2],[-2,1],,]
array = [ for i in range(8)]

def end(array):
    for i in range(8):
      for j in range(8):
            if (not array):
                return False
    return True


def run(row,col,array):
    print((row - 1) * 8 + col)
    if (end(array)):
      print("success")
      return True
    print(row)
    print(col)
    for i in range(8):
      if (row + step >= 1 and col + step >= 1 and row + step <= 8 and col + step <= 8 and not array - 1] - 1]):
            array - 1] - 1] = (row + step - 1) * 8 + (col + step)
            run(row + step,col + step,array)
            print("\b\b\b   ")
            array - 1] - 1] = 0
    return False

def main(row,col):
    array = 18
    run(row,col,array)
    return True

if __name__ == "__main__":
    main(3,2)

我试了下Python写，他说我列表越界了，有没有大佬帮帮忙{:5_105:}

人造人 发表于 2021-12-12 11:53:15

我先贴一下我的代码，等一下看你写的代码

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

const int step = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}, {-2, 1},{2, 1},{-1, 2},{1, 2}};
size_t array;

bool verify(void) {
    for(size_t y = 0; y < 8; ++y) {
      for(size_t x = 0; x < 8; ++x) {
            if(!array) return false;
      }
    }
    return true;
}

bool exist(size_t x, size_t y) {
    if(x >= 8) return false;
    if(y >= 8) return false;
    return true;
}

bool run(size_t x, size_t y, size_t count) {
    if(verify()) return true;
    if(!exist(x, y)) return false;
    if(array) return false;
    bool flag = false;
    array = count;
    for(size_t i = 0; i < 8; ++i) {
      size_t nx = x + step;
      size_t ny = y + step;
      if((flag = run(nx, ny, count + 1))) break;
    }
    if(!flag) array = 0;
    return flag;
}

int main(void) {
    time_t begin = time(NULL);
    run(2, 0, 1);
    for(size_t y = 0; y < 8; ++y) {
      for(size_t x = 0; x < 8; ++x) {
            printf("%2lu ", array);
      }
      puts("");
    }
    time_t end = time(NULL);
    printf("time: %lu\n", end - begin);
    return 0;
}


$ gcc -O3 -o main main.c
$ ./main
1141 1896 15 64
2 19 105 14 17 247
39 123 20 238 63 16
30 21 38 13 28 25 46 61
37 40 29 22 47 62 51 26
34 31 36 55 52 27 60 45
41 56 33 48 43 58 53 50
32 35 42 57 54 49 44 59
time: 496
$

O3 优化都 496 秒，^_^


对于我的这个代码，第一次选的是题目中的位置
    run(4, 3, 1);


$ gcc -O3 -o main main.c
$ ./main
638 11 14 17 20 23
9 1252 21 24 15 18
47 10 13 16 19 22 25
31 28 41 361 26 49 38
42 35 30 27 40 37 60 47
29 32 55 44 61 48 39 50
54 43 34 57 52 63 46 59
33 56 53 62 45 58 51 64
time: 22
$

O3 优化，22 秒

这个使用时间的多少，和起点的选择有关
还和step数组中的元素排列顺序有关

想要得到一个用时最短的组合（起点和step数组中的元素排列顺序）
需要对每一个起点去尝试step数组的全排列，这需要相当长的时间
我就不找这个组合了

我试了一下答案，6秒
#include <stdio.h>
#include <time.h>

#define X 8
#define Y 8

int chess;

// 找到下一个可走的位置
int next(int *px, int *py, int count)
{
      int x = *px;
      int y = *py;

      switch(count)
      {
      case 0:
                if (x+2<=X-1 && y-1>=0 && chess == 0)
                {
                        *px = x + 2;
                        *py = y - 1;
                        return 1;
                }
                break;
      case 1:
                if (x+2<=X-1 && y+1<=Y-1 && chess == 0)
                {
                        *px = x + 2;
                        *py = y + 1;
                        return 1;
                }
                break;
      case 2:
                if (x+1<=X-1 && y-2>=0 && chess == 0)
                {
                        *px = x + 1;
                        *py = y - 2;
                        return 1;
                }
                break;
      case 3:
                if (x+1<=X-1 && y+2<=Y-1 && chess == 0)
                {
                        *px = x + 1;
                        *py = y + 2;
                        return 1;
                }
                break;
      case 4:
                if (x-2>=0 && y-1>=0 && chess == 0)
                {
                        *px = x - 2;
                        *py = y - 1;
                        return 1;
                }
                break;
      case 5:
                if (x-2>=0 && y+1<=Y-1 && chess == 0)
                {
                        *px = x - 2;
                        *py = y + 1;
                        return 1;
                }
                break;
      case 6:
                if (x-1>=0 && y-2>=0 && chess == 0)
                {
                        *px = x - 1;
                        *py = y - 2;
                        return 1;
                }
                break;
      case 7:
                if (x-1>=0 && y+2<=Y-1 && chess == 0)
                {
                        *px = x - 1;
                        *py = y + 2;
                        return 1;
                }
                break;
      }

      return 0;
}

int setHorse(int x, int y, int tag)
{
      int x1 = x, y1 = y, flag = 0, count = 0;

      // tag记录轨迹
      chess = tag;
      // 如果tag等于64退出程序
      if (tag == X*Y)
      {
                return 1;
      }

      // 如果可以走，那么flag为1
      flag = next(&x1, &y1, count);
      // 否则尝试其他路径
      while (flag == 0 && count < 7)
      {
                count += 1;
                flag = next(&x1, &y1, count);
      }

      // 递归进入下一个坐标
      while (flag)
      {
                // 返回1表示成功找到落脚点
                if (setHorse(x1, y1, tag+1))
                {
                        return 1;
                }
                // 否则从上一步重新尝试
                x1 = x;
                y1 = y;
                count += 1;
                flag = next(&x1, &y1, count);
                while (flag == 0 && count < 7)
                {
                        count += 1;
                        flag = next(&x1, &y1, count);
                }
      }

      if (flag == 0)
      {
                chess = 0;
      }

      return 0;
}

int main(void)
{
    time_t begin = time(NULL);
      int i, j;

      for (i = 0; i < X; i++)
      {
                for (j = 0; j < Y; j++)
                {
                        chess = 0;
                }
      }

      // 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
      // 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
      if (setHorse(2, 0, 1))
      {
                for (i = 0; i < X; i++)
                {
                        for (j = 0; j < Y; j++)
                        {
                              printf("%02d", chess);
                        }
                        putchar('\n');
                }
      }
      else
      {
                printf("可惜无解！\n");
      }
    time_t end = time(NULL);
    printf("time: %lu\n", end - begin);

      return 0;
}


$ gcc -O3 -o tmp tmp.c
$ ./tmp
4350473857526132
4837445146335853
0142495639603162
3615404534295459
4102351655246330
1405120922192825
0310072017262364
0613041108211827
time: 6
$

人造人 发表于 2021-12-12 12:43:11

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

const int step = {{2, -1}, {2, 1}, {1, -2}, {1, 2}, {-2, -1},{-2, 1},{-1, -2},{-1, 2}};
size_t array;

bool verify(void) {
    for(size_t y = 0; y < 8; ++y) {
      for(size_t x = 0; x < 8; ++x) {
            if(!array) return false;
      }
    }
    return true;
}

bool exist(size_t x, size_t y) {
    if(x >= 8) return false;
    if(y >= 8) return false;
    return true;
}

bool run(size_t x, size_t y, size_t count) {
    if(verify()) return true;
    if(!exist(x, y)) return false;
    if(array) return false;
    bool flag = false;
    array = count;
    for(size_t i = 0; i < 8; ++i) {
      size_t nx = x + step;
      size_t ny = y + step;
      if((flag = run(nx, ny, count + 1))) break;
    }
    if(!flag) array = 0;
    return flag;
}

int main(void) {
    time_t begin = time(NULL);
    run(2, 0, 1);
    for(size_t y = 0; y < 8; ++y) {
      for(size_t x = 0; x < 8; ++x) {
            printf("%2lu ", array);
      }
      puts("");
    }
    time_t end = time(NULL);
    printf("time: %lu\n", end - begin);
    return 0;
}


$ gcc -O3 -o main main.c
$ ./main
43 481 36 41 1436
50 37 42 1525 10 13
47 44 49 40 35 1274
38 51 56 45 169 20 11
57 46 39 34 55 22 178
52 33 60 29 24 19 26 21
61 58 31 54 63 28 23 18
32 53 62 59 30 25 64 27
time: 9

接下来看你写的代码

人造人 发表于 2021-12-12 17:29:36

作为练习，上面那个八皇后的问题，我也写了，有兴趣的话可以看一看

参考：https://www.jianshu.com/p/deb028537af2
基本思路是：
1.第一行先占一个皇后
2.第二行再占一个且不能与第一个皇后攻击
3.第三行再占一个
。。。。。

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

bool array;
size_t count;

bool verify(size_t y, size_t x) {
    for(size_t cy = 0; cy < y; ++cy) {
      if(array) return false;
    }
    for(size_t cy = y - 1, cx = x - 1; cy < 8 && cx < 8; --cy, --cx) {
      if(array) return false;
    }
    for(size_t cy = y - 1, cx = x + 1; cy < 8 && cx < 8; --cy, ++cx) {
      if(array) return false;
    }
    return true;
}

void run(size_t y) {
    if(y >= 8) {
      printf("count: %lu\n", ++count);
      for(size_t y = 0; y < 8; ++y) {
            for(size_t x = 0; x < 8; ++x) {
                printf("%u ", array);
            }
            puts("");
      }
      return;
    }
    for(size_t x = 0; x < 8; ++x) {
      if(!verify(y, x)) continue;
      array = true;
      run(y + 1);
      array = false;
    }
}

int main(void) {
    run(0);
    return 0;
}

查看完整版本: 小甲鱼课后作业S1E36马踏棋盘问题