马踏棋盘算法(骑士周游问题)
2020 年 04 月 10 日 448 322 字 暂无评论

题目要求:

国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。
要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。

请输入图片描述

代码实现:

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

#define X 8
#define Y 8

int chess[X][Y];
// 找到基于(x,y)位置的下一个可走的位置
int nextxy(int* x, int* y, int count)
{
    switch (count)
    {
    case 0:
        if (*x + 2 <= X - 1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)
        {
            *x = *x + 2;
            *y = *y - 1;
            return 1;
        }
        break;
            case 1:
    if (*x + 2 <= X - 1 && *y + 1 <= Y - 1 && chess[*x + 2][*y + 1] == 0)
    {
        *x = *x + 2;
        *y = *y + 1;
        return 1;
    }
    break;

case 2:
    if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
    {
        *x = *x + 1;
        *y = *y - 2;
        return 1;
    }
    break;

case 3:
    if (*x + 1 <= X - 1 && *y + 2 <= Y - 1 && chess[*x + 1][*y + 2] == 0)
    {
        *x = *x + 1;
        *y = *y + 2;
        return 1;
    }
    break;

case 4:
    if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
    {
        *x = *x - 2;
        *y = *y - 1;
        return 1;
    }
    break;

case 5:
    if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0)
    {
        *x = *x - 2;
        *y = *y + 1;
        return 1;
    }
    break;

case 6:
    if (*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)
    {
        *x = *x - 1;
        *y = *y - 2;
        return 1;
    }
    break;

case 7:
    if (*x - 1 >= 0 && *y + 2 <= Y - 1 && chess[*x - 1][*y + 2] == 0)
    {
        *x = *x - 1;
        *y = *y + 2;
        return 1;
    }
    break;

default:
    break;
}
return 0;
    }

void print()
{
    int i, j;
    for (i = 0; i < X; i++)
{
    for (j = 0; j < Y; j++)
    {
        printf("%2d\t", chess[i][j]);
    }
    printf("\n");
}
printf("\n");
    }

// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量,每走一步,tag+1
int TravelChessBoard(int x, int y, int tag)
{
    int x1 = x, y1 = y, flag = 0, count = 0;
    chess[x][y] = tag;

// 如果tag==X*Y,则完成整个棋盘的遍历
if (tag == X * Y)
{
    print();
    return 1;
}

flag = nextxy(&x1, &y1, count);
while (0 == flag && count < 7)
{
    count++;
    flag = nextxy(&x1, &y1, count);
}

while (flag)
{
    if (TravelChessBoard(x1, y1, tag + 1))
    {
        return 1;
    }

    x1 = x;
    y1 = y;
    count++;

    flag = nextxy(&x1, &y1, count);
    while (0 == flag && count < 7)
    {
        count++;
        flag = nextxy(&x1, &y1, count);
    }
}

if (0 == flag)
{
    chess[x][y] = 0;
}
return 0;
    }

int main()
{
    int i, j;
    clock_t start, finish;
    start = clock();

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

if (!TravelChessBoard(2, 0, 1))
{
    printf("抱歉,马踏棋盘失败鸟~\n");
}

finish = clock();
printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish - start) / CLOCKS_PER_SEC);

return 0;
    }

这里用了回溯法和用到了哈密尔顿路径的概念。
回溯法:

  • 就是一条路走到黑,碰壁了再回来一条路走到黑......一般和递归可以很好的搭配使用,还有深度优先搜索(DFS)。

哈密尔顿路径:

  • 图G中的哈密尔顿路径指的是经过图G中每个顶点,且只经过一次的一条轨迹。如果这条轨迹是一条闭合的路径(从起点出发不重复地遍历所有点后仍能回到起始点),那么这条路径称为哈密尔顿回路

注:以上内容为我从小甲鱼那学习得来的。大家可以去fishc.com.cn学习。


版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/15/



评论已关闭