c++ - 我的骑士之旅算法可能在无限循环中运行

Question

这是我写的代码。

#include "genlib.h"
#include <iostream>
#include <math.h>
#include "vector.h"

struct square
{
    int x;
    int y;

};


bool knighttour(square start,int &counter,int cb[][8]);
Vector <square> generatemoves (square start);
void Marksquare(int &cb,int ctr);
void Unmarksquare(int &cb);
bool IsLegal(square a,int cb[][8]);




int main() 
{
    int chessboard[8][8];

    for (int i=0;i<8;i++)
        for (int j=0;j<8;j++)
            chessboard[i][j]=-1;

    int counter=1;

    for (int i=0;i<8;i++){
        for (int j=0;j<8;j++){
            square temp;
            temp.x=i;
            temp.y=j;
            if (knighttour(temp,counter,chessboard))
            {
                for (int k=0;k<8;k++){
                    cout<<chessboard[k][0]<<chessboard[k][1]<<chessboard[k][2]<<chessboard[k][3]<<chessboard[k][4]<<chessboard[k][5];
                    cout<<chessboard[k][6]<<chessboard[k][7]<<endl;}


            }

        }
    }


    return 0;
}


bool knighttour(square pt,int &counter,int cb[][8])
{

    Marksquare(cb[pt.x][pt.y],counter);
    if (counter==64)
        return true;

    counter++;

    Vector <square> temp = generatemoves(pt);

    for (int i=0;i<temp.size();i++)
    {
        if (IsLegal(temp[i],cb))
            knighttour(temp[i],counter,cb);
    }

    Unmarksquare(cb[pt.x][pt.y]);
    counter--;
    return false;

}



Vector <square> generatemoves (square start)
{
    Vector <square> temp;
    Vector <square> temp2;

        square mv1;
        mv1.x=start.x+2;
        mv1.y=start.y+1;
        temp.add(mv1);

        square mv2;
        mv2.x=mv1.x;
        mv2.y=start.y-1;
        temp.add(mv2);


        square mv3;
        mv3.y=start.y+2;
        mv3.x=start.x+1;
        temp.add(mv3);

        square mv4;
        mv4.y=start.y+2;
        mv4.x=start.x-1;
        temp.add(mv4);

        square mv5;
        mv5.x=start.x-2;
        mv5.y=start.y+1;
        temp.add(mv5);

        square mv6;
        mv6.x=start.x-2;
        mv6.y=start.y-1;
        temp.add(mv6);

        square mv7;
        mv7.y=start.y-2;
        mv7.x=start.x-1;
        temp.add(mv7);

        square mv8;
        mv8.y=start.y-2;
        mv8.x=start.x+1;
        temp.add(mv8);


        for (int i=0;i<temp.size();i++)
            if (temp[i].x>=0 && temp[i].x<=7 && temp[i].y>=0 && temp[i].y<=7)
                temp2.add(temp[i]);




        return temp2;
}



void Marksquare(int &a,int ctr)
{
    a=ctr;

}



void Unmarksquare(int &a)
{
    a=-1;
}


bool IsLegal(square a,int cb[][8])
{
    if (cb[a.x][a.y]==-1)
        return true;
    else 
        return false;
}

一点解释。我正在使用 int [8][8] 来表示棋盘，最初我在棋盘的每个方格中输入数字 -1。

当小马移动时，它用计数器 (int counter) 标记他访问过的方格，然后从那里(以及小马可以采取的所有合法移动)进行递归调用以找到一条路径(目标是访问每个正方形一次)。

一旦计数器达到 64，函数 bool knighttour(square start,int &counter,int cb[][8]) 必须返回 true，然后主程序应该显示 [8][8] 棋盘上标记的“骑士之旅”。

我相信我提供的上述代码在无限循环中运行。我让它运行 3 分钟。

Answer 1

Theory says :

...It is important to note that an exhaustive brute force approach (one which iterates through all possible move sequences) can never be applied to the Knight's Tour problem (except for very small board sizes). For a regular 8x8 chess board, there are approximately 4×1051 possible move sequences,[9] and it would take an unfathomable amount of time to iterate through such a large number of moves.

因此，为确保您的程序正常运行，请尝试使用较小的电路板尺寸(例如 4x4)。

为确保您的程序在合理的时间内适用于 8x8，您必须更改算法。除了列出的还有很多here .

--编辑--

另外，为了确保您的程序正在执行某些操作，在您仍在开发程序时添加一些跟踪始终是个好主意。

例如

bool knighttour(square pt,int &counter,int cb[][8]) {

printf("\r%d    ", counter);  // <<<---
Marksquare(cb[pt.x][pt.y],counter);
if (counter==64)
    return true;

counter++;

Vector <square> temp = generatemoves(pt);

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
        knighttour(temp[i],counter,cb);
}

Unmarksquare(cb[pt.x][pt.y]);
counter--;
return false;

}