骑士游c++递归

Question

我正在尝试使用递归函数在 C++ 中进行骑士之旅，但该程序只是退出而没有多次执行该函数。主要概念只是通过一个函数强制方法，该函数通过跳转到任何开放位置并尝试转到下一个位置来找到方法。如果它在其中阻塞自己，它应该 return 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

任何对最终工作感兴趣的人 code/solution 这里是最终版本。它仍然只是一种蛮力方法，远非最佳，但它可能会有所帮助：

#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

您的问题是 if 条件，例如

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

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

Answer 2

我注意到您的代码中存在以下错误。

sha::free 在结束 } 之前没有 return 语句。这是未定义行为的原因。

我不清楚当函数达到那个点时 return 值应该是 false 还是 true。
您正在使用 pos[xx+2][yy-1] != NULL。似乎您正在尝试与指针进行比较，但 pos[xx+2][yy-1] 不是指针。它是一个整数。从你的 post 中不清楚你的意图是什么。
您正在使用无效索引访问 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) { return (x+n)%8; }
int minusIndex(x, n) { return (x-n+8)%8; }
```
然后使用：
```
// Don't use this
// if( pos[xx+2][yy-1]==0 &&pos[xx+2][yy-1]!=NULL && free(xx+2,yy-1)!=false )

// Use this.
if ( pos[plusIndex(xx, 2)][minusIndex(yy, 1)] != 0 &&
     ...
```
您在 free 的递归调用中传递了无效索引。当你使用
```
free(xx+2,yy-1)
```
其中一个或两个都可能是无效索引。相反，使用
```
free(plusIndex(xx, 2), minusIndex(yy, 1))
```

免责声明

以上更改没有解决您 posted 代码中的任何算法错误。

骑士游c++递归

Knights tour c++ recursive

c++

knights-tour