Backtracking pe tabla de sah

Backtracking pe tabla de sah

1. Problema turelor

1.1. Enuntul si consideratii

Problema: Sa se aranjeze pe o tabla de sah de dimensiuni n x n un numar de n ture astfel incat
oricare doua ture sa nu se ameninte.

Rezolvare: trebuie sa observam mai intai ca nu pot fi doua ture pe aceeasi coloana, caci astfel ar fi
doua ture care s-ar ameninta reciproc, rezulta ca fiecare coloana are exact 1 tura. Fie x[i] linia pe
care se afla tura de pe coloana i. Tinand cont ca nu pot fi doua ture pe aceeasi linie, este:

(xx, x . , xn) = a (xi <>xj)
1 <= i < j <= n

De unde, prin serializare obtinem functia omega corespunzatoare:

Wk(x[1], x[2], , x[k]) = a (x[i]<>x[k])

1<=i<k

1.2. Programul in limbajul Pascal

program problema_turelor;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k do
if x [i] x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for i := l to n do
begin

for j := l to n do
if x [i] = j then

write ('X')
else

write ('o');
writeln
end
end;

i backtracking implementarea recursiva I
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + l then

prelucreaza_solutie (np, x)
else

for i := l to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level l, np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := l;
x [k] O;
while k > O do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] O;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Problema turelor pentru o tabla de n x n');

write ('n=');

readln (np);

for i := 1 to np do

p [i] := np;
backtracking (iterativ, np, p)
end.

1.3. Programul in limbajul C

include <stdio.h>

define MAXSIR

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])

void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p[])

void main ()

1.4. Exercitii si probleme

Demonstrati ca problema turelor este echivalenta cu problema generarii permutarilor.

Modificati procedura de afisare astfel incat rezultatul sa apara sub forma:

+ + +

I T | | |
+---- + + +

I I T | |
+---- + + +

| | | T |

1.5. Rezolvarea exercitiilor si problemelor

Avem aceleasi functii 9

Codul sursa este:

i. In limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for j := 1 to n do

write ');

writeln ('+');
for i := 1 to n do

begin

for j to n do
if x [i] = j then

write ('| T else

write ('| writeln ('|');
for j := 1 to n do

write ');

writeln end
end;

ii. in limbajul C:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])

2. Problema damelor

2.1. Enuntul si consideratii

Problema: Sa se aranjeze pe o tabla de sah de dimensiuni n x n un numar de n dame astfel incat
oricare doua dame sa nu se ameninte.

Rezolvare: trebuie sa observam mai intai ca nu pot fi doua ture pe aceeasi coloana, caci astfel ar fi
doua ture care s-ar ameninta reciproc, rezulta ca fiecare coloana are exact 1 tura. Fie x[i] linia pe
care se afla tura de pe coloana i. Tinand cont ca nu pot fi doua ture pe aceeasi linie sau aceeasi
diagonala, este :

(x x . , xn) = a (xi <>xj A | xi - xj | <> j - i)

1 <= i < j <= n

De unde, prin serializare obtinem functia omega corespunzatoare:

fflk(x[1], x[2], , x[k]) = a (x[i]<>x[k] a I x[i] - x[k] I <> k - i)

1<=i<k

2.2. Programul in limbajul Pascal

program problema_damelor;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);

var p: sir;

var np: indicesir;

function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do

if (x [i] x [k]) or (abs (x [i] x [k]) k i) then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for i := 1 to n do
begin

for j := 1 to n do
if x [i] = j then

write ('X')
else

write ('o');
writeln
end
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level + 1, np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] := 0;
while k > 0 do
begin
repeat

inc (x [k]);

ok := fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin

case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Problema damelor pentru o tabla de n x n');

write ('n=');

readln (np);

for i := 1 to np do

p [i] := np;
backtracking (iterativ, np, p)
end.

2.3. Programul in limbajul C

include <stdio.h>

include <math.h>

define MAXSIR

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

ll prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie (int n, int x[])
i

printf ('O noua solutie este:n');
for (int i i <= n; i++)
i

for (int j j <= n; j++)

printf ('%c', x [i] j 'X' 'o');

printf ('n');
j

j

ll backtracking implementarea recursiva
void btr (int level, int np, int p[], int x[])
i

if (level > MAXSIR)

return;
if (level == np + 1)

prelucreaza_solutie (np, x);
else

for (int i i <= p [level]; i++)
i

x [level] = i;

if fi (level, x)

btr (level np, p, x);

void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k np)
prelucreaza_solutie (np, x);
else

else
k--;

void backtracking (int tip, int np, int p

void main ()

printf ('Problema damelor pentru o tabla de n x nn');

printf ('n=');

scanf ('%d', &np);

for (int i = 1; i <= np; i++)

p [i] = np;
backtracking (ITERATIV, np, p);

2.4. Exercitii si probleme

Problema are solutie pentru orice n natural?

Deeterminati solutiile pentru n<=4.

2.5. Rezolvarea exercitiilor si problemelor

nu, de exemplu, pentru 2 si 3 nu avem solutii

Pentru n=1 avem doar solutia banala, pentru n=2 si n=3 nu avem solutii, pentru n=4 avem
urmatoarele doua solutii:

.X..
X
X
..X.

si:

..X.
X
X
.X.