c++ 我的Knight's Tour问题代码没有任何输出

v8wbuo2f  于 2023-03-05  发布在  其他
关注(0)|答案(3)|浏览(86)

问题:
给定一个N * N棋盘,骑士位于空棋盘的第一块。按照国际象棋的规则,骑士必须访问每个方格一次。打印每个方格被访问的顺序。

    • 我使用了回溯,但没有得到任何输出**
#include <bits/stdc++.h>
using namespace std;

bool valid(int a, int b)
{
    //check validity
    if (a < 0 || a > 7 || b < 0 || b > 7)
        return false;

    return true;
}

bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j)
{
    //ans found
    if (chess[i][j] == 63)
        return true;
        
    else
    {
        bool flag = false;

        for (int k = 0; k < moves.size(); k++)
        {
            int a = i + moves[k].first, b = j + moves[k].second;
            //if valid.. and not already visited
            if (valid(a, b) && chess[a][b] == -1)
            {
                chess[a][b] = chess[i][j] + 1;

                //recurse for next moves
                flag = backtrack(chess, moves, a, b);

                //if solution not found..backtrack
                if (!flag)
                    chess[a][b] = -1;
                
                //break..return ans
                else
                    break;
            }
        }
        return flag;
    }
}

int main()
{
    vector<vector<int>> chess(8, vector<int>(8, -1));

    vector<pair<int, int>> moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
    
    chess[0][0] = 0;

    backtrack(chess, moves, 0, 0);

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            cout << chess[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
tcomlyy6

tcomlyy61#

将移动的顺序更改为(较不纠结的)

vector<pair<int, int>> moves = { {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

它会起作用的,很快
有多种可能的解决方案。也有其他策略来选择搜索顺序,这可能会改善事情。
这里是一个替代版本,让您发挥与董事会的大小:

#include <iostream>
#include <iomanip>
#include <utility>
using namespace std;

const int N = 8;
int A[N][N]{};
pair<int,int> jump[] = { {1,2}, {2,1} ,{2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

//==========================================================

void display()
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) cout << setw( 3 ) << A[i][j];
      cout << '\n';
   }
}

//==========================================================

bool check( int mv, int i, int j )
{
   if ( i < 0 || i >= N || j < 0 || j >= N || A[i][j] ) return false;
   A[i][j] = mv;
   return true;
}

//==========================================================

bool solve( int mv, int i0, int j0 )                       // main backtracking routine
{
   if ( mv == N * N )                                      // *** COMPLETION
   {
      display();
      return true;
   }

   for ( int jp = 0; jp < 8; jp++ )
   {
      int i = i0 + jump[jp].first ;
      int j = j0 + jump[jp].second;
      if ( check( mv, i, j ) && solve( mv + 1, i, j ) ) return true;      // *** MAIN RECURSIVE CALL ***
   }
   A[i0][j0] = 0;
   return false;
}

//==========================================================

int main()
{
   int i = 0, j = 0, mv = 0;
   A[i][j] = mv;
   solve( mv + 1, i, j );
}
jtjikinw

jtjikinw2#

我没有发现任何无限循环,但是你的代码从来没有到达打印行,因为你使用的是一个蛮力搜索算法,而且你使用的电路板尺寸太大,不可能在合理的时间内用蛮力计算出来。
维基百科上说,在一个8x8棋盘上有“26,534,728,821,064个封闭的图尔斯”,基本上这意味着你可以为该棋盘找到的解的数量。
用蛮力搜索马的路线在最小的棋盘上是不切实际的,例如,在一个8 × 8的棋盘上有大约4×1051个可能的移动序列,这远远超出了现代计算机的能力(或计算机网络)来对如此大的集合执行操作。然而,这个数字的大小并不表明问题的难度,这个问题可以“通过人类的洞察力和聪明才智......不费吹灰之力”解决。-维基百科(骑士之旅-暴力算法)
这意味着在这么大的空间里找到其中一个解的可能性非常低。
您需要使用另一个运行时更快的算法,例如分治算法或该页上列出的其他算法。

wbrvyc0a

wbrvyc0a3#

你的代码中没有bug。简单地说,算法必须稍微改进才能更快。
一个技巧是首先选择那些没有太多未来邻居的细胞。
在下面的代码中,

  • 我列了一张可能的职位清单。
  • 对于每个位置,我计算未来可能的位置数
  • 我根据这些数字排序可能的第一个位置

经过这样的修改,我几乎是瞬间就得到了结果,即使N = 20。

    • 结果**
0 59 14 31 48 27 12 29
15 32 53 60 13 30 49 26
58  1 56 45 54 47 28 11
33 16 61 52 63 44 25 50
 2 57 42 55 46 51 10 39
17 34 19 62 43 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6
#include <vector>
#include <utility>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <numeric>
#include <algorithm>

#define N 8                 // 8
#define two_n_m1 (N*N-1)    // 63 = N*N - 1

using namespace std;

bool valid(int a, int b) {
    //check validity
    return (a >= 0 && a < N && b >= 0 && b < N);
}

int count_neighbors (vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j) {
    int count = 0;
    for (auto& mov: moves) {
        int a = i + mov.first, b = j + mov.second;
        if (valid(a, b) && (chess[a][b] == -1)) {
            count ++;
        }
    }
    return count;
}

bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j) {
    //ans found
    if (chess[i][j] == two_n_m1) return true;
    vector<pair<int, int>> neighbors;
    
    for (auto& mov: moves) {
        int a = i + mov.first, b = j + mov.second;
        if (valid(a, b) && (chess[a][b] == -1)) {
            neighbors.push_back ({a, b});
        }
    }
    int n = neighbors.size();
    if (n == 0) return false;
    if (n == 1) {
        int a = neighbors[0].first, b = neighbors[0].second;
        chess[a][b] = chess[i][j] + 1;
        return backtrack(chess, moves, a, b);
    }
    vector<int> future;
    for (auto& candidate: neighbors)  {
        int count = count_neighbors (chess, moves, candidate.first, candidate.second);
        future.push_back (count);                                                                
    }
    vector<int> index(n);
    std::iota (index.begin(), index.end(), 0);
    auto comp = [&] (int i, int j) {return future[i] < future[j];};
    std::sort (index.begin(), index.end(), comp);

    for (int k = 0; k < n; k++) {
        int kp = index[k];
        int a = neighbors[kp].first, b = neighbors[kp].second;
            chess[a][b] = chess[i][j] + 1;
            auto flag = backtrack(chess, moves, a, b);
            if (flag) return true;
            chess[a][b] = -1;
    }
    return false;
}

int main()
{
    vector<vector<int>> chess(N, vector<int>(N, -1));

    vector<pair<int, int>> moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};

    chess[0][0] = 0;

    auto check = backtrack(chess, moves, 0, 0);
    
    if (!check) {
        cout << "No solution found\n";
        std::exit (1);
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << right << setw(2) << chess[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

相关问题