Probleme ce necesita back-tracking

Am explicat pe larg aceasta metoda de programare intr-un capitol separat. In acest capitol vom oferi doar citeva exemple de probleme rezolvate. Majoritatea dintre ele sint de maxima dificultate si nu li se cunoaste o altfel de rezolvare decit prin aceasta metoda. Din fericire, aceasta metoda de proiectare a solutiei are un caracter foarte general si 'functioneaza' in fiecare caz. Din nefericire, in practica, atunci cind dimensiunea datelor de intrare este consistenta (avind valori cel putin de ordinul sutelor)  programul rezultat devine, prin durata astronomica de executie, total inutilizabil.

Atragem atentia ca doar simpla lecturare a acestor exemple de probleme de back-tracking rezolvate nu permite nicidecum insusirea acestei metode de proiectare a solutiilor. Este necesara mai intii implicarea si participare personala, a celui ce-si propune sa invete aceasta metoda, incercind direct solutionarea lor si abia apoi comparind solutia rezultata cu cea propusa de noi.

Problema clasica de programare care necesita back-tracking (revenirea pe urma lasata) este problema iesirii din labirint.

- iata o solutie simpla care initializeaza labirintul in mod static, ca o matrice de caractere

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define XMAX 6

#define YMAX 6

char a[XMAX+1][YMAX+1]=;

int x0=1,y0=2;

void print(void)

getchar();clrscr();

void escape(int x,int y)

a[x][y]='*';print();

if(a[x][y+1]==' ')

if(a[x+1][y]==' ')

if(a[x][y-1]==' ')

if(a[x-1][y]==' ')

return;

void main(void)

Sa se genereze toate sirurile de lungime n formate numai din caracterele a, b si c a.i. sa nu existe doua subsiruri identice alaturate.

- de exemplu, daca n=3 putem avea siruri de forma abc, cab, bcb, etc. dar nu si siruri de forma aab; pentru n=4 nu putem genera siruri de forma abab, baac, etc.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define byte unsigned char

char car[4]=' abc';

unsigned int n,contor;

int Valid(char *s,char c,byte k)

if (ok)

}

return Val;

void ConcatSir(char *s,byte k)

} else

void main(void)

Sa se afiseze toate descompunerile unei sume s intr-un numar minim de monezi ale unui sistem monetar de n valori.

- de exemplu, in cazul unui sistem monetar de forma 10, 5, 3, 1 putem descompune suma 18 in diverse moduri dar solutia minimala necesita doar 3 monezi: 18=1 x 10+1 x 5+1 x 3 ; descompunerea minimala poate sa nu fie unica ; sistemul monetar trebuie sa fie astfel ales incit sa permita descompunerea oricarei sume incepind de la o valoare minimala in sus (orice sistem monetar contine de obicei moneda unitara 1)

#include <stdio.h>

int m[10],a[10],a_final[10],s,n,nrmin=32000,kmin;

void descompune(int s,int k,int contor)

else return;

if(k>n) return;

if(k==n)

else for(i=s/m[k];i>=0;i--)

void main(void)

Sa se afiseze toate descompunerile unui numar s ca suma de n elemente.

- de exemplu, pentru s=13 si n=3 avem urmatoarele 14 descompuneri 13= 1+1+11= 1+2+10= 1+3+9= . = 1+6+6= 2+2+9= 2+3+8= 2+4+7= 2+5+6= 3+3+7= 3+4+6= 3+5+5=  4+4+5

- desi este cu totul alta problema decit cea dinainte, putem observa asemanarea dintre cele doua solutii (ambele sint date in varianta recursiva)

#include <stdio.h>

int a[10],s,n,contor=0;

void descompune(int s,int k)

else for(i=1;i<s;i++)

void main(void)