Backtracking pe matrice

Backtracking pe matrice

1. Enuntul problemei si modificari in algoritm

1.1. Prezentare si extinderi

Principial avem aceleasi conditii ca la capitolul precedent cu mentiunea ca in loc sa avem un vector
X vom avea o matrice A[i][j] cu elemente din multimea My = .

Modificarile care apar in algoritm sunt legate de mentinerea in paralel a unei matrice A[N][N] cu
elemente identice cu ale vectorului X[N*N]. Pentru asta, e necesar sa gasim o bijectie intre
multimile X si . De exemplu, o bijectie poate fi data de
parcurgerea pe linii a matricii, in acest caz formulele de transformare de la indice de sir (k) la indici
de matrice (i, j) fiind:

i(k) := 1 + (k - 1) div n

j(k) := 1 + (k - 1) mod n

iar de la indici de matrice la indici de sir:

k(i, j) := (i - 1) * n + j

evident, se pot 'inventa' si alte metode de parcurgere a matricii, importanta este doar conditia de
bijectie a functiei de transformare. Evident, in functie de natura problemei, a ideilor privind
constructia partiala se pot gasi si alte metode de parcurgere.

De asemenea, pe aceleasi idei se pot construi solutii peste matrici tridimensionale sau orice alt tip
de structuri de date, cu conditia gasirii bijectiei spre multimea indicilor vectorului X.

1. Modificarea algoritmului iterativ

Global a, p
Subprogram bt
k := 1

a [1, 1] := 0

Cat timp k > 0 Executa
Repeta

ii := sir2linie (k)
jj := sir2coloana (k)
incrementeaza (a [ii, jj])

ok := fi (k) sau (a [ii, jj] > p [ii, jj])
Pana Cand ok

Daca a [ii, jj] <= p [ii, jj] Atunci
Daca k = n * n Atunci

Apel prelucreaza_solutie

Altfel

incrementeaza (k)

a [ sir2linie (k), sir2coloana (k) ] := 0
Sfarsit Daca
Altfel

a [ sir2linie (k), sir2coloana (k) ] := 0

decrementeaza (k)
Sfarsit Daca
Sfarsit Cat Timp
Sfarsit Subprogram

Modificarea algoritmului recursiv

Global p, a

Subprogram btr (level)

Daca level = n * n + 1 Atunci

Apel prelucreaza_solutie
Altfel

ii := sir2linie (level)
jj := sir2coloana (level)
Pentru i := 1, p [ii, jj] Executa
a [ii, jj] := i
Daca fi (level) Atunci

btr (level Sfarsit Daca
a [ii, jj] := 0
Sfarsit Pentru
Sfarsit Daca
Sfarsit Subprogram

Exercitii si probleme

Demonstrati ca transformarile (1)-(3) reprezinta o bijectie si inversa ei.

Gasiti transformarile de la parcurgerea pe coloane.

Demonstrati ca transformarile de la problema precedenta reprezinta o bijectie.

Gasiti formulele pentru parcurgerea pe 'diagonale' :

5. EXtindeti parcurgerea pe linii/coloane la o matrice tridimensionala.

6. Extindeti parcurgerea pe 'diagonale' la o parcurgere in 'planuri secante diagonale' a unei
matrici tridimensionale cubice.

1.5. Rezolvarea exercitiilor si problemelor

1. Demonstram ca (3) reprezinta o bijectie, iar apoi ca (1) si (2) reprezinta componentele inversei
acesteea:

k injectiva: fie k(i1, j1) = k(i2, j2), avem atunci ca (i1 - 1) * n + j1 = (i2 - 1) * n + j Dar
cum a = b ^ a = b (mod n), avem ca j1 = j Inlocuind, obtinem (i1-1) * n = (i2 - 1) * n.
Deoarece n <> 0, avem ca i1 - 1 = i2 - 1, adica i1 = i Deci, (i1, j1) = (i2, j2).

ii.      k surjectiva: Fie k0 un element din . Conform teoremei impartirii cu rest, exista
a si b astfel incat a * n + b = k0 - 1 si 0 <= b < n. Fie i = 1 + a si j = 1 + b. Avem ca k (i, j)
= k0.

iii.     inversa lui k: Se aplica teorema impartirii cu rest.

Formulele sunt:

j(k) := 1 + (k - 1) div n
i(k) := 1 + (k - 1) mod n
k(i, j) := (j - 1) * n + i

Se procedeaza analog cu problema 1.

Vom distinge 2 cazuri:

Cazul 1. k este deasupra (sau inclusiv pe) diagonala secundara : Se observa ca pe diagonala a 'i'-a
sunt i elemente. Deci pentru un numar k, daca el se afla pe diagonala a 'l'-a, rezulta ca avem:

1 + 2 + + (l - 1) < k <= 1 + 2 + + l

adica :

l * (l - 1) / 2 < k <= l (l + 1) / 2
Aceasta inecuatie admite solutie unica :
l = l(k)

Prin urmare, elementul k se afla pe diagonala l(k), care incepe cu elementul (l(k), 1). Pentru a vedea
al catelea element este pe diagonala , va trebui sa efectuam scaderea numarului de elemente de pe
cele l(k) - 1 diagonale dinaintea celei de-a l(k) diagonale pe care se afla elementul:

k - l(k) * (l(k) - 1) /

Prin urmare, transformarea este:

i(k) = l(k) + 1 - j (k)
j(k) = k - l(k) * (l(k) - 1) / 2

Cazul k este sub (exclusiv) diagonala secundara. Fie k0 numarul de ordine in cadrul acestui
triunghi :

k0 = k - n * (n² + 1) / 2

Observam ca in acest triunghi, pe diagonala a 'i'-a sunt n-i elemente. Deci pentru un numar k, daca
el se afla pe diagonala a 'l'-a, rezulta ca avem:

(n - 1) + (n - 2) + + (n - (l - 1)) < k0 <= (n - 1) + (n - 2) + + (n - l)

adica:

(l - 1) * n - l * (l - 1) / 2 < k0 <= l * n - l * (l + 1) / 2
aceasta inecuatie admite solutie unica:
l = l'(k0)

Prin urmare, elementul k se afla pe diagonala l'(k0), care incepe cu elementul (n + 1 - l'(k0), l'(k0)
+ 1). Pentru a vedea al catelea element este pe diagonala, va trebui sa efectuam scaderea numarului
de elemente de pe cele l'(k0) - 1 diagonale dinaintea celei de-a l(k) diagonale pe care se afla
elementul:

k0 - l'(k0) * (l'(k0) - 1) /

Prin urmare, transformarea este:

i(k) = n + 2 - l'(k0) - k0 - l'(k0) * (l'(k0) - 1) / 2
j(k) = l'(k0) + k0 - l'(k0) * (l'(k0) - 1) / 2

Formulele sunt:

j(k) := 1 + (k - 1) div (n * n)
i(k) := 1 + (k - 1) div n mod n
l(k) := 1 + (k - 1) mod n

k(i, j, l) := (l - 1) * n * n + (j - 1) * n + i

Formulele se bazeaza pe faptul ca al l-lea plan are ecuatia:

i + j + k = l
unde l poate lua valori de la 1 pana la 3 * n.

Model de program in Pascal

program algoritmul_backtracking_pe_matrice;
const maxmatrice

type matrice = array [1..maxmatrice, 1..maxmatrice] of integer;
type tipbacktracking = (recursiv, iterativ);

var n: integer;
var a: matrice;
var p: matrice;

function sir2linie (k: integer): integer;
begin

sir2linie (k div n
end;

function sir2coloana (k: integer): integer;
begin

sir2coloana (k mod n
end;

function fi (k: integer): boolean;
begin
fi := true
end;

procedure prelucreaza_solutie;
var i, j: integer;
begin

writeln ('Solutie noua:');
for i := 1 to n do
begin

for j := 1 to n do

write (a [i, j], ' ');
writeln
end
end;

procedure btr (level: integer);

var i, ii, jj: integer;
begin

if (n > maxmatrice) or (n < 1) then
exit;

if (level > n * n + 1) or (level < 1) then
exit;

if level = n * n + 1 then

prelucreaza_solutie
else
begin

ii := sir2linie (level);
jj := sir2coloana (level);
for i := 1 to p [ii, jj] do

begin

a [ii, jj] := i;
if fi (level) then
btr (level + 1);
a [ii, jj] := 0
end
end
end;

procedure bt;

var k, ii, jj: integer;
var ok: boolean;
begin
k := 1;

a [1, 1] := 0;

if (n > maxmatrice) or (n < 1) then

exit;
while k > 0 do
begin
repeat

ii := sir2linie (k);
jj := sir2coloana (k);
inc (a [ii, jj]);

ok := fi (k) or (a [ii, jj] > p [ii, jj])
until ok;

if a [ii, jj] <= p [ii, jj] then
if k = n * n then

prelucreaza_solutie
else
begin
inc (k);

a [ sir2linie (k), sir2coloana (k) ] := 0
end

else
begin

a [ sir2linie (k), sir2coloana (k) ] := 0;
dec (k)
end
end
end;

procedure backtracking (tip: tipbacktracking);
begin

case tip of

recursiv: btr (1);
iterativ: bt
end
end;

procedure inita;

var i, j: integer;
begin

for i := 1 to n do
for i := 1 to n do
a [i, j] := 0

end;

writeln ('exemplificare backtracking recursiv');
inita;

backtracking (recursiv);

writeln ('exemplificare backtracking iterativ');
inita;

backtracking (iterativ)
end.

3. Modele de program in C

include <stdio.h>

define MAXMATRICE

define RECURSIV

define ITERATIV 2

int p [MAXMATRICE][MAXMATRICE];
int a [MAXMATRICE][MAXMATRICE];
int n;

define TRUE

define FALSE

// conversiile linie, coloana -> indice sir

int sir2linie (int k)

int sir2coloana (int k)

functia de continuare

int fi (int k)

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie ()

backtracking implementarea recursiva

void btr (int level)

void bt ()

if (a [ii][jj] <= p [ii][jj])
if (k n n)
prelucreaza_solutie else

else

void backtracking (int tip)

void inita ()

void main

4. Generarea careurilor magice

Enuntul si consideratii

Problema: Determinati toate careurile magice de ordin dat.
Rezolvare: Suma tuturor elementelor din careu este:

S = 1 + 2 + + n*n = n * n * (n * n + 1) / 2

adica suma pe o linie/coloana este :

VAL = S / n = n * (n * n + 1) / 2

Prin urmare, functia este:

(a[1,1],, a[n,n]) = L₁ a L₂ a L_n a C₁ a C₂ a C_n a DP a DS

unde:

Li = 'a[i, 1] + a[i, 2] + + a[i, n] = VAL', i=1,n
Ci = 'a[1, i] + a[2, i] + + a[n, i] = VAL', i=1,n
DP = 'a[1, 1] + a[2, 2] + + a[n, n] = VAL'
DS = 'a[1, n] + a[2, n - 1] + + a[n, 1] = VAL'

Aplicand principiul serializarii, rezulta ca functia omega este:

= L'₁ A L'₂ a L'_n A C'₁ A C'₂ A C'_n A DP' A DS'

unde:

L'_i = Li, daca j(k) = n (suntem la capat de coloana)
L'i = 'a[i, 1] + a[i, 2] + + a[i, n] <= VAL', in rest

C'_i = C_i, daca i(k) = n (suntem la capat de linie)
C'i = 'a[1, i] + a[2, i] + . + a[n, i] <= VAL', in rest

DP' = DP, daca i(k) = j(k) = n (suntem in dreapta-jos)
DP' = 'a[1, 1] + a[2, 2] + . + a[n, n] <= VAL', in rest

DS' = DS, daca i(k) = n, j(k) = 1 (suntem in stanga-jos)
DS' = 'a[1, n] + a[2, n - 1] + + a[n, 1] <= VAL', in rest

Programul in limbajul Pascal

program careuri_magice;

onst maxmatrice

type matrice = array [1..maxmatrice, 1..maxmatrice] of integer;
type tipbacktracking = (recursiv, iterativ);

var n: integer;
var a: matrice;
var p: matrice;

function sir2linie (k: integer): integer;
begin

sir2linie := 1 + (k - 1) div n
end;

function sir2coloana (k: integer): integer;
begin

sir2coloana := 1 + (k - 1) mod n
end;

function fi (k: integer): boolean;
var s, i, j, ii, jj, val: integer;
var rez: boolean;
begin

rez := true;

ii := sir2linie (k);

jj := sir2coloana (k);

if rez then

for i := 1 to ii - 1 do
for j := 1 to n do

rez := rez and (a [ii][jj] <> a [i][j]);
if rez then

for j := 1 to jj - 1 do

rez := rez and (a [ii][jj] <> a [ii][j]);

val := n * (n * n + 1) div 2;
if rez then
begin
s := 0;

for j := 1 to jj do

inc (s, a [ii][j]);
if jj = n then

rez := rez and (s = val)
else

rez := rez and (s <= val)
end;

if rez then
begin
s := 0;

for i := 1 to ii do

inc (s, a [i][jj]);
if ii = n then

rez:= rez and (s = val)
else

rez:= rez and (s <= val)
end;

if rez and (ii = n) and (jj = 1) then
begin
s := 0;

for i := 1 to n do

inc (s, a [i][n + 1 - i]);
rez:= rez and (s = val)
end;

if rez and (ii = n) and (jj = n) then
begin
s := 0;

for i := 1 to n do

inc (s, a [i][i]);
rez:= rez and (s = val)
end;
fi := rez
end;

procedure prelucreaza_solutie;
var i, j: integer;
begin

writeln ('Solutie noua:');
for i := 1 to n do
begin

for j := 1 to n do

write (a [i][j], ' ');
writeln
end
end;

procedure btr (level: integer);
var i, ii, jj: integer;
begin

if (n > maxmatrice) or (n < 1) then
exit;

if (level > n * n + 1) or (level < 1) then
exit;

if level = n * n + 1 then

prelucreaza_solutie
else
begin

ii := sir2linie (level);
jj := sir2coloana (level);
for i to p [ii][jj] do
begin

a [ii][jj] := i;

if fi (level) then
btr (level + 1);
a [ii][jj] := 0
end
end
end;

procedure bt;

var k, ii, jj: integer;
var ok: boolean;
begin
k := 1;

a [1][1] := 0;

if (n > maxmatrice) or (n < 1) then

exit;
while k > 0 do
begin
repeat

ii := sir2linie (k);
jj := sir2coloana (k);
inc (a [ii][jj]);

ok := fi (k) or (a [ii][jj] > p [ii][jj])
until ok;

if a [ii][jj] <= p [ii][jj] then
if k = n * n then

prelucreaza_solutie
else
begin
inc (k);

a [sir2linie (k)][sir2coloana (k)] := 0
end

else
begin

a [sir2linie (k)][sir2coloana (k)] := 0;
dec (k)
end
end
end;

procedure backtracking (tip: tipbacktracking);
begin

case tip of

recursiv: btr (1);
iterativ: bt
end
end;

procedure initap;
var i, j: integer;
begin

for i := 1 to n do
for j := 1 to n do

begin

a [i][j] p [i][j] n n

end

end;

begin
n

writeln ('careuri magice de ordinul ', n);
initap;

backtracking (iterativ)
end.

4.3. Programul in limbajul C

include <stdio.h>

define MAXMATRICE 10

define RECURSIV 1

define ITERATIV 2

int p [MAXMATRICE][MAXMATRICE];
int a [MAXMATRICE][MAXMATRICE];
int n;

define TRUE 1

define FALSE 0

// conversiile linie, coloana -> indice sir

int sir2linie (int k)

int sir2coloana (int k)

// functia de continuare

int fi (int k)

// verific sumele pe diag princ

if ((ii == n) && (jj == n))

return TRUE;
}

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie ()

// backtracking implementarea recursiva

void btr (int level)

void bt ()

if (a [ii][jj] <= p [ii][jj])
if (k == n * n)
prelucreaza_solutie ();
else

else

void backtracking (int tip)

void initap

void main ()

4.4. Exercitii si probleme

Rulati programul si determinati careurile magice de ordinul 3.

Modificati programul pentru a gasi careurile magice de ordinul 5. De ce programul ruleaza
semnificativ mult mai mult?

Cautati un algoritm de determinare a careurilor magice de ordin impar.

Argumentati de ce pentru n = 2 nu avem solutii.

4.5. Rezolvarea exercitiilor si problemelor

1. Rezultatul rularii programului:

careuri magice de ordinul 3
Solutie noua:
2 7 6
9 5 1
4 3 8

Solutie noua:

Solutie noua:
4 3 8
9 5 1

Solutie noua:
4 9 2

Solutie noua:
6 1 8

Solutie noua:
6 7 2
1 5 9

Solutie noua:
8 1 6

Solutie noua:
8 3 4
1 5 9
6 7 2

Se inlocuieste atribuirea n=3 (n:=3) din programul principal cu n=5 (n:=5). Programul are o
complexitate comparabila cu (n ^A 2) ^A (n ^A 2). Astfel ca daca in al doilea caz ruleaza de
aproximativ 25 a 25 / 9 a 9 ori mai mult, adica :

25 a 25 / 9 a 9 ^ (100 / 4) a 25 / 10 a 9 = (10 a 50 / 2 a 50 * 10 a 9) =
= 10 a 41 / (2 a 10) a 5 ^ 10 a 41 / (10 a 3) a 5 = 10 a 41 / 10 a 15 = 10 a 26.

Se porneste de la mijlocul primei linii si se completeaza in directia sus-dreapta elementele cu
mentiunea ca la iesirea din matrice se completeaza elementele care se obtin ajustand indicii cu
+n sau -n astfel incat sa se revina in matrice :

in momentul in care se ajunge la un impas (pozitia este deja ocupata) se completeaza prima pozitie
libera sub acest element:

4. Fie a, b, c, d cele patru elemente ale careului:

a b
c d

Vom avea ecuatiile:

Din prima si utima ecuatie rezulta ca a + b = b + c, adica a = c contradictie cu faptul ca elementele
careului sunt distincte.