类似于 Knight-Tour-Problem 的回溯问题

Question

我正在尝试解决与 Knight-Tour-Problem 类似的问题。问题：

A knight is placed on the upper-left square of a chess board. You are given a vector of numbers(the numbers represent the squares of the chess board, as numbered from left to right, from 1 to 64). The knight has to get to those squares in the vector, one after the other, and at the end you should output the path the knight took. Note that the knight might visit a square more than once.

我尝试使用回溯解决这个类似于骑士之旅问题的问题。但是我陷入了“不止一次访问一个广场”的困境。如果我不设置任何条件，骑士只会在 2 个方格之间来回跳跃，永远到不了任何地方。我还尝试以某种方式限制骑士返回它之前到达的方格，但后来我得到了一个更大的循环。在这种特殊情况下，我是否遗漏了什么或回溯一般错误？

下面是我的代码。请注意，作为一个简单的测试，我只使用了右下角的方块作为骑士到达它的目标，即使这样程序也失败了，调试器显示骑士仍在无限循环中行走。

#include <iostream>
#include <cmath>
using namespace std;

const int n = 8;
bool found = 0;
int *path = new int[n*n];
int pathindex=0;
bool visited[n][n];

void print(int (*matrica)[n]); //function to print a matrix
void printpath(int path[n*n]){
    for(int i=0;i<pathindex;i++)
        cout<<path[i]<<" ";
        cout<<endl;
}

void knight(int (*matrica)[n], int x, int y, int path[n*n], int &pathindex){

if(found){
 return;
}
    if (x==7 && y == 7){ //if knight landed on the target, output the result
       found = 1;
       path[pathindex]=matrica[7][7];
       pathindex++;
       printpath(path);
       return;
      } 
     if(x > n-1 || y > n-1 || x < 0 || y < 0){ //if coordinates out of bounds, dismiss
        return;
    }
    path[pathindex]= matrica[x][y];
    pathindex++;
                                        //all possible knight moves     
        if(path[pathindex-1]!=matrica[x-1][y+2])   //conditions to test if the next square was the one we came from
        knight(matrica, x-1, y+2, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x-2][y+1])
        knight(matrica, x-2, y+1, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x+1][y+2])
        knight(matrica, x+1, y+2, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x+2][y+1])
        knight(matrica, x+2, y+1, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x+2][y-1])
        knight(matrica, x+2, y-1, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x+1][y-2])
        knight(matrica, x+1, y-2, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x-1][y-2])
        knight(matrica, x-1, y-2, path, pathindex);
        
        if(path[pathindex-1]!=matrica[x-2][y-1])
        knight(matrica, x-2, y-1, path, pathindex);
    pathindex--;    
}


int main(){

int matrica[n][n];
int k = 1;
  for(int i=0;i<n;i++){  //number the chess board
    for(int j=0;j<n;j++){
        matrica[i][j] = k;
        k++;}
}
    print(matrica); 
    knight(matrica, 0, 0, path, pathindex);
    if(!found)
    cout<<"No Solution!";
    return 0;
}
void print(int (*matrica)[n]){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(matrica[i][j]<10)
            cout<<" "<<matrica[i][j]<<" ";
            else
            cout<<matrica[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl<<endl;
}

我如何实现骑士可以多次使用同一个方格，但它不能在原来的地方循环行走的部分？

请注意，这不是任何家庭作业或学校相关项目，这只是我个人的乐趣。

Answer 1

如果按顺序访问方块，这很容易；找出如何从 a 到 b。基本寻路。然后连接。

如果方格数较少，每次排列都按上述方法进行。为所有对排序 a 到 b 的成本（b 到 a 是相同的）。然后解决旅行商寻找最短路线。

假设第一个，或者如果你不关心最短，这是“从 a 到 b 的寻路”。当这样做时你可以假设它永远不会循环，因为那样的话不做循环也可以。

最简单的解决办法就是涂漆。有一个充满 -1 的 8x8 网格。写 0。然后在所有从 0 开始的 -1 的骑士移动中写 1。然后在所有从 1 开始的 -1 的骑士移动中写下 2。重复。

如果你真的想画得花哨，你可以用位操作来代替绘画。有 8 个 8 位值。在骑士开始的地方画一个 1 位。一系列的转变和面具可以盲目地转变为“骑士可以到达”的面具。存储每组移动的可达掩码，直到到达目标方块。

现在回溯 - 从目标方格移动到先前快照中的任何合法移动。然后重复直到你到达原来的骑士广场。

newrow[i]=row[i-2]<<1 | row[i-2]>>1 | row[i+2]<<1 | row[i+2]>>1 | row[i-1]<<2 | row[i-1]>>2 | row[i+1]<<2 | row[i+1]>>2;

进行边界检查，因此 row[out of bounds] 为 0 且上限为 8 位，并且每 8 行循环一次，并且您将可到达的骑士面具向前或向后 1 步。

类似于 Knight-Tour-Problem 的回溯问题

Backtracking problem similar to Knight-Tour-Problem

c++

backtracking

chess

knights-tour