【原创】关于 "马踏棋盘" 的回溯算法问题

blogdaren 2020-12-17 2评论 144人次

问题背景:

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

问题说明:

作者自行实现的代码好像有BUG,分享出来,望不吝赐教。

实现源码:

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

#define ROW     8
#define COL     8
#define TOTAL   ROW * COL
#define TOTAL_NUMBER_WITH_FOOT_POSITION  8

typedef struct cache
{
    int (*pline)[COL];
    int col;
    int val;
}Cache;

void initChess(int (*p)[COL]);
void showChess(int (*p)[COL]);
void showAddress();
void showFoot();
void findNextPosition(Cache *pcache);
int isPositionUsed(int n);
int isAddressValid(int *p);
Cache *getOnePossiblePositon(int index, Cache *pcache);
int global_foot[TOTAL];
int *global_address[TOTAL];


int main()
{
    int data[ROW][COL] = {0};
    Cache cache, *pc;

    pc = &cache;
    pc->col = 4;
    pc->pline = data;

    initChess(data);
    showChess(data);
    /*showAddress();*/

    //设定一初始位置
    global_foot[0] = *(*pc->pline + pc->col);

    findNextPosition(pc);
    showFoot();

    return 0;
}

void findNextPosition(Cache *pcache)
{
    int i = 0; 
    static int counter = 0;
    Cache *pcache2;

    if(counter > TOTAL) return;

    for(i = 1; i <= TOTAL_NUMBER_WITH_FOOT_POSITION; i++)
    {
        pcache2 = getOnePossiblePositon(i, pcache);

        if(pcache2 == NULL) continue;

        int ok = 1;
        if(isPositionUsed(pcache2->val)) ok = 0;

        //找到了一个可用位置
        if(ok == 1) 
        {
            global_foot[++counter] = pcache2->val;
            /*printf("%02d-%d\n", counter, pcache2->val);*/
            findNextPosition(pcache2);
        }
    }
}

void initChess(int (*p)[COL])
{
    int i, k = 0;

    for(i = 0; i < TOTAL; i++)
    {
        *(*p + i) = ++k;
    }
}

Cache *getOnePossiblePositon(int index, Cache *pcache)
{
    Cache cache2, *pcache2;
    int t1, t2;

    pcache2 = &cache2;
    
    if(index == 1)
    {
        pcache2->pline = pcache->pline - 2;
        pcache2->col = pcache->col - 1;
    }
    else if(index == 2)
    {
        pcache2->pline = pcache->pline - 2;
        pcache2->col = pcache->col + 1;
    }
    else if(index == 3)
    {
        pcache2->pline = pcache->pline - 1;
        pcache2->col = pcache->col + 2;
    }
    else if(index == 4)
    {
        pcache2->pline = pcache->pline + 1;
        pcache2->col = pcache->col + 2;
    }
    else if(index == 5)
    {
        pcache2->pline = pcache->pline + 2;
        pcache2->col = pcache->col + 1;
    }
    else if(index == 6)
    {
        pcache2->pline = pcache->pline + 2;
        pcache2->col = pcache->col - 1;
    }
    else if(index == 7)
    {
        pcache2->pline = pcache->pline + 1;
        pcache2->col = pcache->col - 2;
    }
    else if(index == 8)
    {
        pcache2->pline = pcache->pline - 1;
        pcache2->col = pcache->col - 2;
    }

    if(pcache2->col < 0 || pcache2->col > COL - 1) return NULL;

    t1 = isAddressValid(*pcache2->pline);
    if(0 == t1) return NULL;

    t2 = isAddressValid(*pcache2->pline + pcache2->col);
    if(0 == t2) return NULL;

    pcache2->val = *(*pcache2->pline + pcache2->col);

    return pcache2;
}

void showChess(int (*p)[COL])
{
    int i;

    putchar('\n');

    for(i = 0; i < TOTAL; i++)
    {
        printf("%3d ", *(*p + i), *p + i);

        if((i + 1) % COL == 0) putchar('\n');
        global_address[i] = *p + i;
    }

    putchar('\n');
}

void showAddress()
{
    int i;

    for(i = 0; i < TOTAL; i++)
    {
        printf("%p ", global_address[i]);

        if((i + 1) % COL == 0) putchar('\n');
    }

    putchar('\n');
}

int isPositionUsed(int n)
{
    int i;

    for(i = 0; i < TOTAL; i++)
    {
        if(n == global_foot[i])
        {
            return 1;
        }
    }

    return 0;
}

int isAddressValid(int *p)
{
    int i;

    for(i = 0; i < TOTAL; i++)
    {
        if(p == global_address[i])
        {
            return 1;
        }
    }

    return 0;
}

void showFoot()
{
    int i = 0;

    printf("宝马依次走过的足迹为:\n\n");

    for(i = 0; i < TOTAL; i++)
    {
        printf("%d ", global_foot[i]);
    }

    putchar('\n');
    putchar('\n');
}


版权声明:除非注明,本文由( blogdaren )原创,转载请保留文章出处。

本文链接:【原创】关于 "马踏棋盘" 的回溯算法问题

用户评论:

2020-12-25 19:35
写点注释它不香吗?
blogdaren
2020-12-28 21:18
@肥臣:^v^ XAR ^v^

发表评论:

您的昵称:
电子邮件:
个人主页:

Free Web Hosting