What is the error in solving the traveling salesman problem using backtracking?

Question

C++ / C#

The traveling salesman problem.

There are n cities with given distances; the traveling salesman needs to leave some city, visit the other n-1 cities exactly once and return to the starting city. In this case, the traveling salesman route must have a minimum length (cost).

Input data:
10
-1 32 19 33 22 41 18 15 16 31
32 -1 51 58 27 42 35 18 17 34
19 51 -1 23 35 49 26 34 35 41
33 58 23 -1 33 37 23 46 46 32
22 35 33 -1 19 10 23 23 9
41 42 49 37 19 -1 24 42 42 10
18 35 26 23 10 24 -1 25 25 14
15 18 34 46 23 42 25 -1 1 32
16 17 35 46 25 42 -1 32
31 34 41 32 9 10 14 32 32 -1

Output:
If you go from the zero city, then 158.

My idea:
There is a minimum amount, if some solution is already greater than this minimum amount, then we exit this cycle, since we need a minimum solution. Since we need to go through all the cities, we create a separate Boolean vector in which we will mark the already passed settlements. Additionally, for debugging, I began to display which stations the salesman will go to.

My program's response to the input given is:
168
2 3 6 5 9 4 1 8 7 0

#include <iostream>
#include <vector>
#include <fstream>

void minimumWay(std::vector<std::vector<int>>&board, std::vector<bool>& checker, 
                std::vector<int>& now, std::vector<int>& best, 
                long long int sum, long long int& sumMin, int number, int count) 
{
    if (sum < sumMin)
    {
        if (count == board[0].size() + 1)
        {           
            best = now;
            sumMin = sum;
        }
        else if (count == board[0].size())
        {
            sum += board[number][0];
            minimumWay(board, checker, now, best, sum, sumMin, number, count + 1);
        }
        else
        {
            for (int i = 0; i < board[0].size(); i++)
            {
                if (board[number][i] > 0 && checker[i] == false)
                {
                    now[count - 1] = i;
                    checker[i] = true;

                    minimumWay(board, checker, now, best,
                        sum + board[number][i], sumMin, i, count + 1);

                    now[count - 1] = -1;
                    checker[i] = false;
                }
            }
        }
    }   
}

int main()
{
    std::ifstream fin("C:\\Users\\User\\Documents\\Files\\INPUT3.txt");
    
    int in = 0, count = 0;
    fin >> count;

    std::vector<std::vector<int>>board(count, std::vector<int>(count));

    int x = 0, y = 0;
    while (fin >> in)
    {
        board[x][y] = in;
        y++;
        if (y == count)
        {
            x++;
            y = 0;
        }
    }

    fin.close();

    std::vector<bool> checker(count);
   

    std::vector<int> now(count);
    std::vector<int> best(count);
    long long int sumMin = 900000000000000;

    int start = 0;
    std::cout << "Input a number of city where the salesman goes ";
    std::cin >> start;
    checker[start] = true;

    minimumWay(board, checker, now, best, 0, sumMin, start, 1);
    best[best.size() - 1] = start;
    std::cout << sumMin << '\n';
    for (int i = 0; i < best.size(); i++)
    {
        std::cout << best[i] << " ";
    }
    std::cout << '\n';
}

Answer 1

I don't see any error in the code.
Try rewriting with std::next_permutation to iterate over all permutations. Just to compare and test the test - suddenly there is a typo.
It will work slower than recursive enumeration due to the lack of cutoffs, and the same solution with a cyclic shift will be obtained n times, but for 10 cities it should quickly work out. But on the other hand, the code will be quite simple: one loop, as in the example from the documentation, iterates over all permutations from 0 to n-1. Inside, you take these numbers in a loop as city indices and sum up the distances between them + the distance between the last one and the initial one. And remember if the sum is less than the known minimum. If it turns out 168 there too, there is a typo in the test.