设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 小甲鱼课后作业S1E36马踏棋盘问题
返回列表 发新帖
查看: 2291|回复: 5

[已解决]小甲鱼课后作业S1E36马踏棋盘问题

[复制链接]
飞花落尽
发表于 2021-12-10 23:06:20 | 显示全部楼层 |阅读模式
15鱼币
请问各位大佬们，我的回溯算法为什么会死循环？
#include <stdio.h>

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

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

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

int main(void)
{
        int row,col;
        printf("请输入行数：");
        scanf("%d",&row);
        printf("请输入列数：");
        scanf("%d",&col);
        array[row - 1][col - 1] = (row - 1) * 8 + col;
        run(row,col,array);
        
        return 0;
}
最佳答案
月排行榜 / 总排行榜
人造人
2021-12-10 23:06:21
你代码逻辑就是错的吧？
还有写代码不认真
#include <stdio.h>

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

int run(int row, int col, int (*array)[8]) {
    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[i][0] >= 1 && col + step[i][1] >= 1 &&
           // 认真一点
           //row + step[i][0] <= 8 && col + step[i][0] <= 8 &&
           row + step[i][0] <= 8 && col + step[i][1] <= 8 &&
           !array[row + step[i][0] - 1][col + step[i][1] - 1]) {
            array[row + step[i][0] - 1][col + step[i][1] - 1] =
                (row + step[i][0] - 1) * 8 + (col + step[i][1]);

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

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

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

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

    run(row, col, array);

    return 0;
}

最佳答案

人造人

查看完整内容

你代码逻辑就是错的吧？ 还有写代码不认真
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2021-12-10 23:06:21 | 显示全部楼层    本楼为最佳答案   
你代码逻辑就是错的吧？
还有写代码不认真
#include <stdio.h>

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

int run(int row, int col, int (*array)[8]) {
    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[i][0] >= 1 && col + step[i][1] >= 1 &&
           // 认真一点
           //row + step[i][0] <= 8 && col + step[i][0] <= 8 &&
           row + step[i][0] <= 8 && col + step[i][1] <= 8 &&
           !array[row + step[i][0] - 1][col + step[i][1] - 1]) {
            array[row + step[i][0] - 1][col + step[i][1] - 1] =
                (row + step[i][0] - 1) * 8 + (col + step[i][1]);

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

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

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

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

    run(row, col, array);

    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

飞花落尽
 楼主| 发表于 2021-12-11 09:54:43 | 显示全部楼层 
step = [[-1,-2],[1,-2],[-2,-1],[2,-1],[-1,2],[-2,1],[1,2],[2,1]]
array = [[0 for j in range(8)] for i in range(8)]

def end(array):
    for i in range(8):
        for j in range(8):
            if (not array[i][j]):
                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[i][0] >= 1 and col + step[i][1] >= 1 and row + step[i][0] <= 8 and col + step[i][0] <= 8 and not array[row + step[i][0] - 1][col + step[i][1] - 1]):
            array[row + step[i][0] - 1][col + step[i][1] - 1] = (row + step[i][0] - 1) * 8 + (col + step[i][1])
            run(row + step[i][0],col + step[i][1],array)
            print("\b\b\b   ")
            array[row + step[i][0] - 1][col + step[i][1] - 1] = 0
    return False

def main(row,col):
    array[row - 1][col - 1] = 18
    run(row,col,array)
    return True

if __name__ == "__main__":
    main(3,2)
我试了下Python写，他说我列表越界了，有没有大佬帮帮忙
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2021-12-12 11:53:15 | 显示全部楼层
我先贴一下我的代码，等一下看你写的代码
#include <stdio.h>
#include <stdbool.h>
#include <time.h>

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

bool verify(void) {
    for(size_t y = 0; y < 8; ++y) {
        for(size_t x = 0; x < 8; ++x) {
            if(!array[y][x]) 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[y][x]) return false;
    bool flag = false;
    array[y][x] = count;
    for(size_t i = 0; i < 8; ++i) {
        size_t nx = x + step[i][0];
        size_t ny = y + step[i][1];
        if((flag = run(nx, ny, count + 1))) break;
    }
    if(!flag) array[y][x] = 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[y][x]);
        }
        puts("");
    }
    time_t end = time(NULL);
    printf("time: %lu\n", end - begin);
    return 0;
}
$ gcc -O3 -o main main.c
$ ./main
11  4  1 18  9  6 15 64
 2 19 10  5 14 17 24  7
39 12  3 20 23  8 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
 6  3  8 11 14 17 20 23
 9 12  5  2 21 24 15 18
 4  7 10 13 16 19 22 25
31 28 41 36  1 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[X][Y];

// 找到下一个可走的位置
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[x+2][y-1] == 0)
                {
                        *px = x + 2;
                        *py = y - 1;
                        return 1;
                }
                break;
        case 1:
                if (x+2<=X-1 && y+1<=Y-1 && chess[x+2][y+1] == 0)
                {
                        *px = x + 2;
                        *py = y + 1;
                        return 1;
                }
                break;
        case 2:
                if (x+1<=X-1 && y-2>=0 && chess[x+1][y-2] == 0)
                {
                        *px = x + 1;
                        *py = y - 2;
                        return 1;
                }
                break;
        case 3:
                if (x+1<=X-1 && y+2<=Y-1 && chess[x+1][y+2] == 0)
                {
                        *px = x + 1;
                        *py = y + 2;
                        return 1;
                }
                break;
        case 4:
                if (x-2>=0 && y-1>=0 && chess[x-2][y-1] == 0)
                {
                        *px = x - 2;
                        *py = y - 1;
                        return 1;
                }
                break;
        case 5:
                if (x-2>=0 && y+1<=Y-1 && chess[x-2][y+1] == 0)
                {
                        *px = x - 2;
                        *py = y + 1;
                        return 1;
                }
                break;
        case 6:
                if (x-1>=0 && y-2>=0 && chess[x-1][y-2] == 0)
                {
                        *px = x - 1;
                        *py = y - 2;
                        return 1;
                }
                break;
        case 7:
                if (x-1>=0 && y+2<=Y-1 && chess[x-1][y+2] == 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[x][y] = 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[x][y] = 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[i][j] = 0;
                }
        }

        // 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
        // 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
        if (setHorse(2, 0, 1))
        {
                for (i = 0; i < X; i++)
                {
                        for (j = 0; j < Y; j++)
                        {
                                printf("%02d  ", chess[i][j]);
                        }
                        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
43  50  47  38  57  52  61  32
48  37  44  51  46  33  58  53
01  42  49  56  39  60  31  62
36  15  40  45  34  29  54  59
41  02  35  16  55  24  63  30
14  05  12  09  22  19  28  25
03  10  07  20  17  26  23  64
06  13  04  11  08  21  18  27
time: 6
$
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2021-12-12 12:43:11 | 显示全部楼层 
#include <stdio.h>
#include <stdbool.h>
#include <time.h>

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

bool verify(void) {
    for(size_t y = 0; y < 8; ++y) {
        for(size_t x = 0; x < 8; ++x) {
            if(!array[y][x]) 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[y][x]) return false;
    bool flag = false;
    array[y][x] = count;
    for(size_t i = 0; i < 8; ++i) {
        size_t nx = x + step[i][0];
        size_t ny = y + step[i][1];
        if((flag = run(nx, ny, count + 1))) break;
    }
    if(!flag) array[y][x] = 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[y][x]);
        }
        puts("");
    }
    time_t end = time(NULL);
    printf("time: %lu\n", end - begin);
    return 0;
}
$ gcc -O3 -o main main.c
$ ./main
43 48  1 36 41 14  3  6
50 37 42 15  2  5 10 13
47 44 49 40 35 12  7  4
38 51 56 45 16  9 20 11
57 46 39 34 55 22 17  8
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

接下来看你写的代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2021-12-12 17:29:36 | 显示全部楼层
作为练习，上面那个八皇后的问题，我也写了，有兴趣的话可以看一看

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

bool array[8][8];
size_t count;

bool verify(size_t y, size_t x) {
    for(size_t cy = 0; cy < y; ++cy) {
        if(array[cy][x]) return false;
    }
    for(size_t cy = y - 1, cx = x - 1; cy < 8 && cx < 8; --cy, --cx) {
        if(array[cy][cx]) return false;
    }
    for(size_t cy = y - 1, cx = x + 1; cy < 8 && cx < 8; --cy, ++cx) {
        if(array[cy][cx]) 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[y][x]);
            }
            puts("");
        }
        return;
    }
    for(size_t x = 0; x < 8; ++x) {
        if(!verify(y, x)) continue;
        array[y][x] = true;
        run(y + 1);
        array[y][x] = false;
    }
}

int main(void) {
    run(0);
    return 0;
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 17:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表