马踏棋盘

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

typedef struct              //结点类型
 {
    int num1;
    int num2;
    struct node *prior;
    struct node *next;

 }node;

typedef struct            //走法数组类型
{
    int m;
    int n;
}array; 

typedef struct             //栈的类型
{
    int row;
    int col;
}stack;

int main()          
{
    int i,j,k,l;
    int a,b=0;
    node *head,*p,*ptr;
    int flag[9][9]={0};    
    array po[9];
    stack S[65];                           //初始化栈
    int top=0;
    S[0].row=S[0].col=0;
    head=(node *)malloc(sizeof(node));     //初始化链表
    head->num1=head->num2=NULL;
    head->prior=NULL;
    head->next=NULL;
    p=head;
    printf("请输入起点坐标:i,j\n");
    scanf("%d,%d",&i,&j);
    top++;
    S[top].row=i;                           //已遍历方格入栈
    S[top].col=j;
    flag[i][j]=1;                           //标记遍历方格
    ptr=(node *)malloc(sizeof(node));       //建立表头结点
    ptr->num1=i;
    ptr->num2=j;
    ptr->prior=p;
    ptr->next=NULL;
    p=ptr;
    do
    {
if(top==50)
{
    printf("hahah\n");
}

        printf("%d,%d->",S[top].row,S[top].col);
    for(k=1;k<9;k++)                     //8种走法
    {
        if(k==1||k==2) po[k].m=i-1;
        if(k==3||k==4) po[k].m=i+1;
        if(k==5||k==6) po[k].m=i-2;
        if(k==7||k==8) po[k].m=i+2;
        if(k==1||k==3) po[k].n=j-2;
        if(k==2||k==4) po[k].n=j+2;
        if(k==5||k==7) po[k].n=j-1;
        if(k==6||k==8) po[k].n=j+1;
    }
    if((a!=0)&&(b!=0))                  //发生回溯的情况
    {       
            for(k=1;k<9;k++)
            {
                if((po[k].m==a)&&(po[k].n==b)) 
                {a=0;
                 b=0;
                 for(l=1;l<(k+1);l++)
                 {
                    po[l].m=0;
                    po[l].n=0;
                 }
                 break;
                }
            }
        
    }
    for(k=1;k<9;k++)                     //筛选不可行走法
    {
        if((po[k].m<1)||(po[k].m>8)||(po[k].n<1)||(po[k].n>8))
        {po[k].m=0;
        po[k].n=0;}
        if(flag[po[k].m][po[k].n]==1)
        {po[k].m=0;
          po[k].n=0;}
    }

    for(k=1;k<9;k++)
    {
        if(flag[po[k].m][po[k].n]==0&&po[k].m!=0)      
        {
            top++;
            i=po[k].m;
            j=po[k].n;
            S[top].row=i;
            S[top].col=j;
            flag[i][j]=1;
            ptr=(node *)malloc(sizeof(node));
            ptr->num1=i;
            ptr->num2=j;
            ptr->prior=p;
            ptr->next=NULL;
            p=ptr;
            break;
        }
    }   
    if(k==9)          //当无可行路径时，回溯
    {
        a=i;
        b=j;
        flag[i][j]=0;
          p=p->prior;
        free(ptr);
        ptr=p;
         top--;
        if(top==0)
        {
            printf("\n无法遍历棋盘!\n");
            system("pause");
            return 0;
        }
           i=S[top].row;
        j=S[top].col;
    }
    }while(0<top<65);
    
    if(top==64)
    {   ptr->next=NULL;
        p=head;
        for(l=1;l<64;l++)
        {  
            p=p->next;
            printf("(%d,%d)",p->num1,p->num2);
        }
    }
    system("pause");
    return 0;
}

回溯的代码是不是有问题，好像会出现重复的情况，得不出结果
用这种方式能解决问题吗 可以改出来吗

思路没问题的，也就是重复操作太多所以得出结果会慢一些这么一点瑕疵

得不出结果原因是do while条件恒真

while(0<top<65) --> while((0<top)<65) --> while(1<65) --> while(true)

再者top取值有64种(0 - 63)可能，所以正确的写法是 while (0 < top && top < 64)

哦，你的链表用的不对，next 域从未赋值过，所以输出那肯定会有问题

而且已经有stack了，完全可以删除链表部分。打印stack即可

ps:不要放弃数组的0域，那么大个空间弃用怪可惜的

[此贴子已经被作者于2016-12-11 13:57编辑过]

链表加上这句就没问题了吧?    p->next=ptr;
主要是不知道回溯的代码是不是哪里错了 走过不行的之后还会再走
运行了很久还是没有结果

[此贴子已经被作者于2016-12-13 15:24编辑过]

恩，两个地方要加


你的思路比较懒，穷举的频率较多，所以运行很慢，但是要出结果还是没问题的

我这边测试，把while条件改掉后，运行 40s 左右显示结果