C++ Backtracking

[Nytro]

Poate va ajuta pe cei care dati maine bacul la informatica. E in "debug mode", poate asa intelegeti mai bine ce se intampla. Lui n sa ii dati valorile 2 si 3, nu mai mult ca nu are rost.

Nu stiu daca comentarile sunt bune, nu prea am inteles nici eu backtrackingul asta. Bine, nici nu m-a interesat, doar azi m-am uitat putin peste el.

Pastebin: http://pastebin.com/GjygyUSY

Codul:

#include <iostream>

int sol[10], k, n;

// Afiseaza lista

void tipar()
{
	for(int i = 1; i <= n; i++) std::cout<<sol[i]<<" ";
	std::cout<<"\n";
}

// Verifica daca s-a ajuns la ultimul element

int solutie(int k)
{
	if(k == n+1) 
	{ 
		std::cout<<"* BUN *: ["<<k<<"] :";
		return 1;
	}
	else 
	{
		std::cout<<"Solutie: ["<<k<<"] :";
		tipar();
		return 0;
	}
}

// Initializeaza elementul

void init(int k)
{
	std::cout<<"Init: ["<<k<<"] :";
	tipar();
	sol[k] = 0;
}

// Verifica daca am ajuns la ultimul element, incrementeaza valoarea daca nu

int succesor(int k)
{
	std::cout<<"Succesor: ["<<k<<"] :";
	tipar();
	if(sol[k] < n)
	{
		sol[k]++;
		return 1;
	}
	else return 0;
}

// Verifica daca elementul se mai afla in lista

int valid(int k)
{
	std::cout<<"Valid: ["<<k<<"] :";
	tipar();
	for(int i = 1; i < k; i++)
	{
		if(sol[i] == sol[k]) return 0;
	}
	return 1;
}

// Apeleaza functiile de mai sus

void back(int k)
{
	std::cout<<"Back ["<<k<<"] :";
	tipar();
	if(solutie(k)) tipar();
	else
	{
		init(k);
		while(succesor(k)) if(valid(k)) back(k+1);
	}
}

/*

 * Backtracking nerecursiv, nu stiu daca e bun

void back()
{
	k=1;init(k);
	while(k>0)
	{
		while(succesor(k))
		{
			if(valid(k))
			if(solutie(k))
			tipar();
			else
			{
				k++;
				init(k);
			}
		}
		k--;
	}
}

*/

int main(int argc, char** argv)
{
	std::cout<<"n=";
	std::cin>>n;
	back(1);
	return 0;
}

Doar afiseaza functia apelata si valoarea lui k in paranteza, poate va ajuta.

Edited July 1, 2010 by Nytro

[Ethereal]

o intrebare despre rostul existentei umane:

La bac scriem int main() sau void main()?

LE:

Sau scriem

#ifdef _MINGW_
int main()
#else
void main()
#endif

Edited July 1, 2010 by Ethereal

[Nytro]

Eu cred ca voi pune void, desi in practica folosesc int. Si va trebui sa pui "cout" probabil, desi ma tenteaza mai mult printf-ul... Si pentru siruri strcpy, strcat, nu std::string. Iar pentru citire si scriere din fisiere fstream nu fopen, fread, fclose. Bine, cred ca poti folosi si astea, normal ar fi sa folosesti ce vrei tu.

[Ethereal]

La scoala ne punea sa folosim borland c++, dar la olimpiade (incepand de anul asta) se foloseste standardul nou cu mingw/gnu c++.

[Nytro]

Eu nu foloseam nici la scoala Borlandul, foloseam CodeBlocks.

PS: Nu am testat asta pe Windows, pe Linux merge bine. Puneti si voi #include<iostream.h> si decat cout in loc de std::cout. A, si daca doriti, void main() fara return.

[Guest User Name]

Nytro sa ne anunti si pe noi ce nota ai loat...ok?

[TomescuMihail]

Eu in lucrare la scoala am folosit int main() cu return 0; si mi-a depunctat toata problema

[orion.hacker]

eu am maine examen la programare...si unul din profi s-a hotarat sa modifice subiectele posbile:|

azi m-am trezit ca dau numai din backtracking:))

poate cineva sa-mi dea un simplu exemplu(in C de preferat sau c++)..cu explicatii la fiecare linie?...gen cel de sus...

[vexyro]

eu am maine examen la programare...si unul din profi s-a hotarat sa modifice subiectele posbile:|

azi m-am trezit ca dau numai din backtracking:))

poate cineva sa-mi dea un simplu exemplu(in C de preferat sau c++)..cu explicatii la fiecare linie?...gen cel de sus...

#include <stdio.h>

static int t[10]={-1}; /* vector care retine pozitia reginelor. t[i]=j inseamna regina la (i,j) */
void queens(int i); /* functia de backtracking */
int empty(int i); /* verifica daca reginele se ataca */
void print_solution(); /* afiseaza solutia gasita la pasul curent */

int main()
{
    queens(1); /* porneste BK incepand cu linia 1 */
    print_solution();

    return 0;
}

void queens(int i)
{
    for (t[i]=1; t[i] <= 8; t[i]++) /* itereaza prin toate coloanele */
    {
		printf("i=%d\n",i);
        if (empty(i)) /* verifica daca la pasul curent (t[i]), regina de pe linia i se ataca cu alta de pe tabla */
        {
            if (i == 8) /* daca nu se ataca cu nici una si s-au pus toate cele 8 regine */
            {
                print_solution(); /* solutie */

                exit(0); /* If this exit is commented, it will show ALL possible combinations */
            }
            else
                queens(i + 1); /* se trece la urmatoarea linie din matrice si se incepe iar cu coloana 1 */
        }
    }
}

int empty(int i)
{
    int j;
    j=1;

	while ((t[i] != t[j]) && /* daca reginele nu se afla pe aceeasi coloana */
		   (abs(t[i] - t[j]) != (i-j)) && /* daca reginele nu se afla pe aceeasi diagonala */
		   (j < 8) /* daca nu s-a ajuns la ultima linie */
		  )  
		j++; /* treci la urmatoarea linie */

    return ((i == j) ? 1 : 0); /* daca pana la ea insasi (regina) nu se ataca cu nicio alta regina (decat cu ea) atunci locul este "valid" */

	/* returnul este echivalent cu:
	 * 
	 * if (i == j)
	 * 		return 1;
	 * else
	 * 		return 0;
	 * 
	 */
}

void print_solution() /* e clara */
{
    int i;
    for (i=1; i <= 8; i++)
		printf("t[%d] = [%d]\n", i, t[i]);
}

Sursa: Interview Questions: What is the 8 queens problem? Write a C program to solve it.

P.S. ?tiu, e urât code-styling-ul dar mi-a fost sil? de formatare. Trage-l ?i tu într-un IDE ?i testeaz?-l

Baft? la examen

Edited June 27, 2012 by vexyro

[passfig]

Salut, uite aici un video facut de un coleg de liceu acum 2 ani, in clasa a XI-a profa de info ne pune sa prezentam claselor mai mici backtracking-ul, pe mine m-a impresionat ala la vremea lui :

Exemplul pe care ti-l dau eu este recursiv si foarte simplu de inteles odata ce sti cum merge back-ul. Algoritmul genereaza permutari pentru numere cuprinse intre 1 si n.

#include<iostream>
#include<string>
using namespace std;
int n, sol[100];

void tipar()
{int i;
	for(i=1;i<=n;i++)
		cout<<sol[i]<<" ";
	cout<<endl;
}

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

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

void back(int k)
{
	if(k==n+1) tipar(); //cand stiva e plina o afisezi
	else
	{
		sol[k]=0;
		while(succesor(k)) //cat timp mai este loc in stiva (nu s-au folosit toate numere) ruleza
		if(valid(k)) back(k+1); //daca ce s-a pus pana acum in stiva este ok mai punem un element
	}
}
int main()
{
	cout<<"n= "; cin>>n;
	back(1);
}

Bafta!

[bcman]

Am vazut ca topicul e vechi. Mersi Nytro, am nevoie pentru olimpiada de pe a 10-a. Oh, se foloseste int main() cu return 0 (conform learncpp.com). Cand scrii void main(), defapt compilatorul interpreteaza ca int main() si pune la sfarsit return 0.

[section11]

La olimpiada important e sa mearga, ca nu il scrii pe hartie ca la bac.