使用回溯的奈特算法

Question

我已经使用回溯编写了这个 Knight 问题算法并得到了以下输出，但是无论我在哪里查找人们对它的编码都不同，我不知道这种方法是正确还是错误以及需要进行哪些优化？任何人都可以在这里指导我，因为我对回溯算法还很陌生。

#include<bits/stdc++.h>
using namespace std;


bool isValid(int arr[][5], int i, int j)
{
    return (i>=0 && j>=0 && i<5 && j<5 && arr[i][j]==0);
}

void knightProblem(int arr[][5], int i, int j)
{
    static int count = 0;

    if(!isValid(arr,i,j))
        return;

    count++;

    arr[i][j]=count;

    knightProblem(arr,i+2,j+1);
    knightProblem(arr,i+2,j-1);
    knightProblem(arr,i-2,j+1);
    knightProblem(arr,i-2,j-1);
    knightProblem(arr,i+1,j+2);
    knightProblem(arr,i+1,j-2);
    knightProblem(arr,i-1,j+2);
    knightProblem(arr,i-1,j-2);
}

int main()
{
        int maze[5][5]  =  {
       {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}
    };

    knightProblem(maze,0,0);

    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<maze[i][j]<<" ";
        }

        cout<<"\n";
    }
}

输出

1 23 18 12 24

19 13 15 7 17

22 2 9 4 11

14 20 6 16 8

25 21 3 10 5

Answer 1

您的代码不正确。你永远不会 return 到尝试另一个分支，因为你总是递增计数器。您只是遍历 DFS 顺序中的所有单元格，并不能保证它会产生有效的解决方案（其中有效的 solition 意味着路径，而不是 DFS 顺序）。

如何修正算法的想法：

正确的解决方案需要仅使用一条路径遍历所有单元格。每当你发现无法继续，你仍然没有访问所有单元格时，你需要退后一步释放当前位置。
函数 knightProblem 必须 return 一个值，指示您是否在该方向找到了解决方案。如果 none 当前状态的路径允许您找到解决方案，则需要释放单元格并 return 返回。
避免static int counter。出于多种原因，这是一种不好的做法。最好在 main 中分配一个变量并通过引用传递它。
最终状态（表示您已找到解决方案）是当您的计数器等于棋盘大小时。

使用回溯的奈特算法

Knight's Algorithm using Backtracking

c++

algorithm

backtracking

输出