骑士之旅c++递归

Question

我试图使用递归函数在c++中进行骑士巡演，但是这个程序只是退出而不多次执行该函数。主要的概念只是蛮横地强迫一个函数找到一种方法，跳到任何一个开放的地方，然后尝试去下一个地方。如果它阻止了自己，它应该只返回false并尝试下一个选项，依此类推。我只是完全放弃了这个方法，还是我只是遗漏了什么？

#include <iostream>
#include <math.h>
#include <numeric>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <limits>
using namespace std;

struct sah{

   int pos[8][8] = {{0}};           //fill whole board with 0
   int x;
   int y;
   int fre=64;                      //number of free spaces on board

   bool free (int xx,int yy);

};

bool sah::free (int xx,int yy)
{

   pos[xx][yy]=1;
   for(int a=0;a!=8;a++){
      for(int b=0;b!=8;b++){
         cout<<pos[a][b]<<" ";  
      }
      cout<<endl;
   }

   if(pos[xx+2][yy-1]==0&&pos[xx+2][yy-1]!=NULL&&free(xx+2,yy-1)!=false)
      cout<<"hai";
   else if(pos[xx-2][yy-1]==0&&pos[xx-2][yy-1]!=NULL&&free(xx-2,yy-1)!=false)
      cout<<"hai";      
   else if(pos[xx+2][yy+1]==0&&pos[xx+2][yy+1]!=NULL&&free(xx+2,yy+1)!=false)
      cout<<"hai";      
   else if(pos[xx-2][yy+1]==0&&pos[xx-2][yy+1]!=NULL&&free(xx-2,yy+1)!=false)
      cout<<"hai";      
   else if(pos[xx+1][yy-2]==0&&pos[xx+1][yy-2]!=NULL&&free(xx+1,yy-2)!=false)
      cout<<"hai";      
   else if(pos[xx-1][yy-2]==0&&pos[xx-1][yy-2]!=NULL&&free(xx-1,yy-2)!=false)
      cout<<"hai";      
   else if(pos[xx+1][yy+2]==0&&pos[xx+1][yy+2]!=NULL&&free(xx+1,yy+2)!=false)
      cout<<"hai";  
   else if(pos[xx-1][yy+2]==0&&pos[xx-1][yy+2]!=NULL&&free(xx-1,yy+2)!=false)
      cout<<"hai";  
   else{
      pos[xx][yy]=0;
      cout<<"kek"<<xx<<yy;
      return false;
   }

   for(int n=0;n!=8;n++){
      for(int i=0;i!=8;i++){
         if(pos[n][i]==1)
            fre=fre-1;  
      }
   }
   cout<<fre<<" ";


}

int main(int argc, char** argv) {

   sah chess;
   chess.x=0;
   chess.y=0;
   if(chess.free(chess.x,chess.y)!=false)
      cout<<"end";

}

输出：

1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
kek00

对于任何对最终工作代码/解决方案感兴趣的人来说，这里是最终版本。这仍然只是一种蛮力的方法，远非最佳，但可能会有所帮助：

#include <iostream>
using namespace std;

struct chess{

    int pos[8][8] = {{0}};          //fill whole board with 0
    int x;
    int y;
    int all=0;
    int fre=64;                     //number of free spaces on board

    bool free (int xx,int yy);

};

bool chess::free (int xx,int yy)
{
    all++;

pos[xx][yy]=1;
    for(int n=0;n!=8;n++){
        for(int i=0;i!=8;i++){
            if(pos[n][i]==1)
            fre=fre-1;  
        }
    }
    cout<<endl<<endl;
    for(int a=0;a!=8;a++){
        for(int b=0;b!=8;b++){
            cout<<pos[a][b]<<" ";   
        }
        cout<<endl;
    }
    cout<<endl;

    if(pos[xx+2][yy-1]==0&&yy-1>0&&xx+2<9&&free(xx+2,yy-1)!=false)
    cout<<"success";
    else if(pos[xx-2][yy-1]==0&&xx-2>0&&yy-1>0&&free(xx-2,yy-1)!=false)
    cout<<"success";        
    else if(pos[xx+2][yy+1]==0&&yy+1<9&&xx+2<9&&free(xx+2,yy+1)!=false)
    cout<<"success";        
    else if(pos[xx-2][yy+1]==0&&yy+1<9&&xx-2>0&&free(xx-2,yy+1)!=false)
    cout<<"success";        
    else if(pos[xx+1][yy-2]==0&&xx+1<9&&yy-2>0&&free(xx+1,yy-2)!=false)
    cout<<"success";        
    else if(pos[xx-1][yy-2]==0&&xx-1>0&&yy-2>0&&free(xx-1,yy-2)!=false)
    cout<<"success";        
    else if(pos[xx+1][yy+2]==0&&yy+2<9&&xx+1<9&&free(xx+1,yy+2)!=false)
    cout<<"success";    
    else if(pos[xx-1][yy+2]==0&&yy+2<9&&xx-1>0&&free(xx-1,yy+2)!=false)
    cout<<"success";    
    else{
            if(fre==0)
            return true;
            pos[xx][yy]=0;
            cout<<"   "<<xx<<","<<yy;
            return false;
    }
}

int main(int argc, char** argv) {

    chess knight;
    knight.x=0;
    knight.y=0;
    if(knight.free(knight.x,knight.y)==true)
    cout<<endl<<endl<<endl<<knight.all;
    return 0;
}

Answer 1

我注意到代码中有以下错误。

1. sha::free在关闭}之前没有return语句。这是造成未定义行为的原因。 当函数到达这个点时，我不清楚返回值应该是false还是true。
2. 您正在使用pos[xx+2][yy-1] != NULL。似乎您正在尝试与指针进行比较，但pos[xx+2][yy-1]不是指针。它是一个整数。从你的帖子中还不清楚你的意图是什么。
3. 您正在使用无效的索引访问pos，如pos[xx+2][yy-1]和pos[xx-2][yy-1，这也是导致未定义行为的原因。 如果xx为6或更高，则xx+2是无效索引。如果yy为0，则yy-1为无效索引。 我建议对这些指数进行以下修正。 xx+2需要成为(xx+2)%8。 yy-1需要成为(yy-1+8)%8。 xx+1、xx-1、xx-1、yy+1、yy+2和yy-2也需要进行类似的更改。 您可能需要使用一个函数来封装逻辑。 例如。 int plusIndex(x，n) {返回(x+n)%8；} int minusIndex(x，n) {返回(x-n+8)%8；} 然后使用： //不要使用这个// if( posxx+2==0 &&posxx+2!=NULL & free(xx+2，yy--1)！=false) //使用这个。如果( posplusIndex(xx，2) != 0 &&…
4. 在对free的递归调用中传递无效的索引。当你使用 免费(xx+2，yy-1) 其中一个或两者都可能是无效的索引。相反，使用 免费(plusIndex(xx，2)，minusIndex(yy，1))

免责声明

上述更改不会解决您发布的代码中的任何算法错误。

Answer 2

您的问题在于if条件，如

pos[xx+2][yy-1]==0&&pos[xx+2][yy-1]!=NULL

这总是false，因为在您在这里使用的上下文中，NULL和0是等价的。所以你有x == 0 and x != 0，它总是false