C++ backtracking doesn't seem to work

[cplusplusnightmare]

Hello guys! I'm a newbie in programming and i really need your help. I've been trying to learn backtracking for about 3-4 days now and i must say that i find it rather difficult. Most of the programs i found on internet do not seem to work so i asked a friend of mine to send me the "standard" program which is taught in schools( i live in Romania) and he sent me the one i included bellow. The problem is that it doesn't seem to do anything at all - it was supposed to show all the permutations of the inputed number.

#include <iostream>

using namespace std;

int i, n, k, st[20];

void tipar()
{
    for(i=1;i<=n;i++)

        cout<<st[i]<<" ";

    cout<<endl;
}

void init()
{
    st[k]=0;
}

int succesor()
{
    if(st[k]<n) {k++; return 1;}

    else return 0;
}

int valid()
{
    for(i=1;i<=k-1;i++)

        if(st[i]=st[k]) return 0;

    return 1;
}
int solutie()
{
    if(k==n) return 1;

    else return 0;
}
void backtr()
{
    int ev,as;

    k=1;

    init();

    while(k>0)
    {
        do{if(as==1) ev=valid();}

        while(as&&!ev);

            {if(as==1)

            {
                if(solutie()==1) tipar();

        else {k++; init();}

        }

        else k--;}
    }

}
int main()
{
 cout<<"n= ";

 cin>>n;

 backtr();

}

[tpb]

You need to edit your post and repaste your code in code tags so that the indentation is not lost: http://www.cplusplus.com/forum/articles/16853/

[cplusplusnightmare]

I did. Thank you very much for your advice

[tpb]

That's some badly written code.

Two obvious problems.

if (st[i] = st[k]) return 0;

That's probably supposed to be == instead of =.

And as is used uninitialized in backtr.

That code is such garbage I wouldn't bother studying it if i were you.
Try this: https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

[Handy Andy]

Hello cplusplusnightmare,

Welcome to the forum.

PLEASE ALWAYS USE CODE TAGS (the <> formatting button) when posting code.
It makes it easier to read your code and also easier to respond to your post.
http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/
Hint: You can edit your post, highlight your code and press the <> formatting button.
You can use the preview button at the bottom to see how it looks.

It may help if you look at your code this way:

#include <iostream>

using namespace std;

int i{}, n{}, k{}, st[20]{};  // <--- Do not count on these variables to be initialized. Also best not to use global variables.

void tipar()
{
	for (i = 1; i <= n; i++)
		cout << st[i] << " ";

	cout << endl;
}

void init()
{
	st[k] = 0;
}

int succesor()
{
	if (st[k]<n)
	{
		k++;
		return 1;
	}

	else return 0;
}

int valid()
{
	for (i = 1; i <= k - 1; i++)
		if (st[i] = st[k])
			return 0;

	return 1;
}

int solutie()
{
	if (k == n)
		return 1;

	else return 0;
}

void backtr()
{
	int ev{}, as{};  // <--- ALWAYS initialize your variables.

	k = 1;

	init();

	while (k>0)
	{
		do
		{
			if (as == 1) ev = valid();
		}

		while (as && !ev);

		{
			if (as == 1)
			{
				if (solutie() == 1)
					tipar();
				else
				{
					k++; init();
				}
			}

			else k--;
		}
	}

}

int main()
{
	cout << "n= ";

	cin >> n;

	backtr();

	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
	std::cout << "\n\n Press Enter to continue";
	std::cin.get();
	
	return 0;
}

As you can see when the {}s line up in the same column it makes the code easier to read and easier to see lines 65 and 77 limit the scope of what is inside the {}s and line 68 can only be reached if line 66 is true.

Like you I am not sure what the program does yet. I did get it to compile and run. Now all I have to do is figure out what it does and it it is working right. I will work on that shortly after lunch.

I do not know where you learned your style of coding at and although it will work what I showed you is easier to work with and read.

Hope that helps for now,

Andy

[cplusplusnightmare]

yes, i'm sorry. i fixed it and added "return 0" at the end of main, but it still does nothing at all and so does every backtracking program i found .

[cplusplusnightmare]

Thank you, Andy!
This programming style is taught is schools. My programming teacher is pretty bad and i took the decision to learn on my own - i would be really grateful if you could send me some websites where i can learn from.

[E0p9LyTq]

C++ tutorial websites:

Here at cplusplus:
http://www.cplusplus.com/doc/tutorial/

Learn C++
http://www.learncpp.com/

[Handy Andy]

Hello cplusplusnightmare,

Sorry I got behind here. I do agree with tpb that the code is badly written and does not even work. Most of the "backtr" function is passed over because while conditions and if conditions usually come out false and the code in the block is never executed. Some of the variables are never given a value after they are defined.

If you are lucky enough to have the global variables initialized then they are set to zero. When "backtr" runs you are more likely to reach "k--;" which really does not help.

tpb's link is a better place to start.

Hope that helps,

Andy