Backtracking generarea permutărilor problema celor N dame produsul cartezian a N mulțimi

Generarea permutarilor. Se citeste un numar natural n.

Sa se genereze toate permutarile multimii {1, 2, 3, ... n}. Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.

incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei; incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita; valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare; intrucat nivelul 3 este completat corect. Tiparim: 1 2 3 Algoritmul continua pana cand stiva devine vida.

Problema celor n dame. Fiind data o tabla de sah n (n se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc). Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4 (4, o solutie ar fi urmatoarea: Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1. A doua dama nu poate fi asezata decat pe coloana a 3-a. Observam ca a treia dama nu poate fi plasata in linia a 3-a. Incercam atunci plasarea celei de-a doua dame in coloana a 4-a. A treia dama nu poate fi plasata decat pe coloana a 2-a. In aceasta situatie dama a patra nu mai poate fi asezata. Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a treia, nici in coloana a patra, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a doua.

Acum este posibil sa plasam a patra dama in coloana a treia si astfel am obtinut o solutie a problemei.

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru prezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama). Exemplu: pentru solutia gasita avem vectorul st ce poate fi asimilat unei stive.

Intrucat doua dame nu se pot gasi pe aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema (ca doua dame sa nu fie plasate in aceeasi diagonala). A proceda astfel, inseamna sa lucra conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. Fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura valid.

Produsul cartezian a n multimi. Se dau multimile de mai jos si se cere produsul cartezian al lor.

A1 = {1, 2, 3, , k1} A2 = {1, 2, 3, , k2} An = {1, 2, 3, , kn} Exemplu: A1 = {1, 2} A2 = {1, 2, 3} A3 = {1, 2, 3} A1 (A2 (A3 = { (1, 1, 1), (1, 1, 2) ...