马踏棋盘求----全部解

标题：运用栈和回溯法求马踏棋盘的全部解

回溯法的写法参考《数据结构–严蔚敏》的迷宫求解
感谢我的队友-汪汪汪
他与求一个解不同之处在于，当我们求到一个解之后，这个程序却会告诉计算机：“啊！这不是我们想要的解，我们继续吧。”于是，傻傻的计算机就信了我们的话，跳过这个这个解，继续求下一个。当他走完所有可能之后，他才会退出循环，然后告诉我们，我已经求出全部解了。
下面是我求出的解，目前我已经求出三千多个解了，但是1 2 3 点还是没有移动，显然解是有很多的。而且我们发现每个解最后一个位置都是相同的，36都是在同一个点，难道当我们确定前面某几步之后，最后一个点就一定可以确定下来吗？从观察的结果来看，似乎是这样的。里边似乎有着更加深奥的数学知识。
我对此很好奇，但我并不想再去对这个问题进行探究。希望看到这个文章的读者们，能解答我的疑惑，并将你的看法发表在评论区内。欢迎大家积极评论。God bless you

#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define STACK_INIT_SIZE 200
#define INCREASE 10
#define AddRow 10
#define AddCol 10
int Chess[AddRow][AddCol];
typedef struct
{
 int x;
 int y;
}PosType;
typedef struct
{
 int ord;
 PosType seat;
 int di;
}SElemType;
typedef struct
{
 SElemType* base;
 SElemType* top;
 int stacksize;
}SqStack;
int curstep = 1;
bool InitStack(SqStack& S);
bool Push(SqStack& S, SElemType e);
bool Pop(SqStack& S, SElemType& e);
bool GetTop(SqStack S, SElemType& e);
bool StackEmpty(SqStack S);
bool Pass(PosType curpos)
{
 int x = curpos.x, y = curpos.y;
 if (Chess[x][y] == 0)
  return true;
 else
  return false;
}
void ChessPrint()
{
 //输出棋盘结构
 int i, j;
 for (i = 0; i < AddRow; i++)
 {
  for (j = 0; j < AddCol; j++)
   printf("%3d", Chess[i][j]);
  printf("\n");
 }
}
void MarkPrint(PosType curpos)
{
 int x = curpos.x;
 int y = curpos.y;
 Chess[x][y] = 0;
}
void FootPrint(PosType pos)
{
 int x = pos.x;
 int y = pos.y;
 Chess[x][y] = curstep;
}

void InitChess()
{
  int i, j;
  for (i = 0; i < AddRow; i++)
  {
   for (j = 0; j < AddCol; j++)
   {
    if ((i < 2 || i>7) || (j < 2 || j>7))
     Chess[i][j] = -1;
    else
     Chess[i][j] = 0;
   }
  }
}

bool ChessBoard(PosType Start)
{
PosType curpos;
SqStack S;
InitStack(S);
SElemType e;
int counter = 0;
curpos.x = Start.x;
curpos.y = Start.y;
do
{
if (Pass(curpos))        //如果可以通过
{
FootPrint(curpos);
e.di = 1;
e.seat = curpos;
Push(S, e);
NextPos(curpos, 1);
curstep++;
if (curstep == 37)
{
counter++;
cout << "第" << counter << "个解" << endl;
ChessPrint();
Pop(S, e);e.di++;Push(S, e);
curpos = e.seat;
NextPos(curpos, e.di);
}
}else
{
if (!StackEmpty(S))
{
Pop(S, e);        
while (e.di == 8 && !StackEmpty(S)
{
curstep--;   
MarkPrint(e.seat);     
Pop(S, e);
curpos = e.seat;
}
if (e.di < 8){
e.di++;
Push(S, e);
curpos = e.seat;
NextPos(curpos, e.di);
}
}
}
} while (!StackEmpty(S));
cout << "求解结束" << endl;
return true;
}

int main()
{
    PosType Start;
    InitChess();
    Start.x = 2;
    Start.y = 2;
    ChessBoard(Start);
    return 0;
}

bool InitStack(SqStack& S)
{
    S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!S.base)
    {
        cout << "申请空间失败" << endl;
        return false;
    }
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return true;
}
bool Push(SqStack& S, SElemType e)
{
if (S.top - S.base >= S.stacksize)
{
S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stacksize * 2));
S.top = S.base + S.stacksize;
S.stacksize = S.stacksize * 2;
}
    *S.top = e;
    S.top++;
    return true;
}
bool Pop(SqStack& S, SElemType& e)
{
    if (S.top == S.base)
        return false;
    e = *--S.top;
    return true;
}
bool StackEmpty(SqStack S)
{
    if (S.base == S.top)
        return true;
    else
        return false;
}

，