class="bi x1 y1 w1 h1"
Bài toán lit kê
Lê Minh Hoàng
{ 1z
MC LC
§
0. GI
I THIU
2
§
1. NH
C LI MT S KIN THC I S T HP
3
I. CH
NH HP LP
3
II. CH
NH HP KHÔNG LP
3
III. HOÁN V

3
IV. T
 HP
3
§
2. PH
NG PHÁP SINH (GENERATE)
5
I. SINH CÁC DÃY NH

22
I. BÀI TOÁN T
I U
22
II. S
 BÙNG N T HP
22
III. MÔ HÌNH K
 THUT NHÁNH CN
22
IV. BÀI TOÁN NG
I DU LCH
23
V. DÃY ABC 25
Bài toán lit kê
Lê Minh Hoàng
{ 2z
§
0. GII THIU
Trong thc t, có mt s bài toán yêu cu ch rõ: trong mt tp các đi tng cho trc có bao
nhiêu đi tng tho mãn nhng điu kin nht đnh. Bài toán đó gi là bài toán đm cu hình t
hp.
Trong lp các bài toán đm, có nhng bài toán còn yêu cu ch rõ nhng cu hình tìm đc tho
mãn điu kin đã cho là nhng cu hình nào. Bài toán yêu cu đa ra danh sách các cu hình có th
có gi là bài toán lit kê t hp.
 gii bài toán lit kê, cn phi xác đnh đc mt thut toán đ có th theo đó ln lt xây dng
đc tt c các cu hình đang quan tâm. Có nhiu phng pháp lit kê, nhng chúng cn phi đáp
ng đc hai yêu cu di đây:
• Không đc lp li mt cu hình
• Không đc b sót mt cu hình

chnh hp lp chp k ca S. Nh ví d trên (E, C, E) là mt chnh hp lp chp 3 ca S. D dàng
chng minh đc kt qu sau bng quy np hoc bng phng pháp đánh giá kh nng la chn:
S chnh hp lp chp k ca tp gm n phn t:
k
k
n
nA =
II. CHNH HP KHÔNG LP
Khi f là đn ánh có ngha là vi ∀i, j ∈ X ta có f(i) = f(j) ⇔ i = j. Nói mt cách d hiu, khi dãy giá
tr f(1), f(2), , f(k) gm các phn t thuc S khác nhau đôi mt thì f đc gi là mt chnh hp
không lp chp k ca S. Ví d mt chnh hp không lp (C, A, E):
i 123
f(i) C A E
S chnh hp không lp chp k ca tp gm n phn t:
)!kn(
!n
)1kn) (2n)(1n(nA
k
n
−
=+−−−=
III. HOÁN V
Khi k = n. Mt chnh hp không lp chp n ca S đc gi là mt hoán v các phn t ca S.
Ví d: mt hoán v: (A, D, C, E, B, F) ca S = {A, B, C, D, E, F}
i123456
f(i) A D C E B F
 ý rng khi k = n thì s phn t ca tp X = {1, 2, , n} đúng bng s phn t ca S. Do tính cht
đôi mt khác nhau nên dãy f(1), f(2), , f(n) s lit kê đc ht các phn t trong S. Nh vy f là
toàn ánh. Mt khác do gi thit f là chnh hp không lp nên f là đn ánh. Ta có tng ng 1-1 gia
các phn t ca X và S, do đó f là song ánh. Vy nên ta có th đnh ngha mt hoán v ca S là mt

1
n
0
n
2)11(C CC
=+=+++
Bài toán lit kê
Lê Minh Hoàng
{ 5z
§
2. PHNG PHÁP SINH (GENERATE)
Phng pháp sinh có th áp dng đ gii bài toán lit kê t hp đt ra nu nh hai điu kin sau
tho mãn:
1. Có th xác đnh đc mt th t trên tp các cu hình t hp cn lit kê. T đó có th xác
đnh đc cu hình đu tiên và cu hình cui cùng trong th t đã xác đnh
2. Xây dng đc thut toán t cu hình cha phi cu hình cui, sinh ra đc cu hình k
tip nó.
Phng pháp sinh có th mô t nh sau:
<Xây dng cu hình đu tiên>;
repeat
<a ra cu hình đang có>;
<T cu hình đang có sinh ra cu hình k tip nu còn>;
until <ht cu hình>;
Th t t đin
Trên các kiu d liu đn gin chun, ngi ta thng nói ti khái nim th t. Ví d trên kiu s
thì có quan h: 1 < 2; 2 < 3; 3 < 10; , trên kiu ký t Char thì cng có quan h 'A' < 'B'; 'C' < 'c'
Xét quan h th t toàn phn "nh hn hoc bng" ký hiu "≤" trên mt tp hp S, là quan h hai
ngôi tho mãn bn tính cht:
Vi ∀a, b, c ∈ S
• Tính ph bin: Hoc là a ≤ b, hoc b ≤ a;

• Hoc a
i
= b
i
vi ∀i: 1 ≤ i ≤ n.
• Hoc tn ti mt s nguyên dng k: 1 ≤ k < n đ:
a
1
= b
1
a
2
= b
2

a
k-1
= b
k-1
a
k
= b
k
a
k+1
< b
k+1
Trong trng hp này, ta có th vit a < b.
Th t đó gi là th t t đin trên các dãy đ dài n.
Khi đ dài hai dãy a và b không bng nhau, ngi ta cng xác đnh đc th t t đin. Bng cách

-1.
Ví d: Khi n = 3, các dãy nh phân đ dài 3 đc lit kê nh sau:
p(x)01234567
x 000 001 010 011 100 101 110 111
Nh vy dãy đu tiên s là 00 0 và dãy cui cùng s là 11 1. Nhn xét rng nu dãy x = (x
1
, x
2
, ,
x
n
) là dãy đang có và không phi dãy cui cùng thì dãy k tip s nhn đc bng cách cng thêm 1
( theo c s 2 có nh) vào dãy hin ti.
Ví d khi n = 8:
Dãy đang có:
10010000
Dãy đang có:
10010111
cng thêm 1:
+ 1
cng thêm 1:
+ 1
 
Dãy mi:
10010001
Dãy mi:
10011000
Nh vy k thut sinh cu hình k tip t cu hình hin ti có th mô t nh sau: Xét t cui
dãy v đu (xét t hàng đn v lên), gp s 0 đu tiên thì thay nó bng s 1 và đt tt c các phn
t phía sau v trí đó bng 0.

{ 7z
var
x: array[1 max] of Integer;
n, i: Integer;
begin
{nh ngha li thit b nhp/xut chun}
Assign(Input, 'BSTR.INP'); Reset(Input);
Assign(Output, 'BSTR.OUT'); Rewrite(Output);
ReadLn(n);
FillChar(x, SizeOf(x), 0);
{C
u hình ban đu x
1
= x
2
= = x
n
:= 0}
repeat
{Thu
t toán sinh}
for i := 1 to n do Write(x[i]);
{In ra c
u hình hin ti}
WriteLn;
i := n;
{x
i
là ph
n t cui dãy, lùi dn i cho ti khi gp s 0 hoc khi i = 0 thì dng}

đó, ta có nhn xét nu x = {x
1
, x
2
, , x
k
} và x
1
< x
2
< < x
k
thì gii hn trên (giá tr ln nht có
th nhn) ca x
k
là n, ca x
k-1
là n - 1, ca x
k-2
là n - 2
C th: gii hn trên ca x
i
= n - k + i;
Còn tt nhiên, gii hn di ca x
i
(giá tr nh nht x
i
có th nhn) là x
i-1
+ 1.

, x
6
bng các gii hn di ca nó. Tc là:
• x
3
:= x
2
+ 1 = 4
• x
4
:= x
3
+ 1 = 5
• x
5
:= x
4
+ 1 = 6
• x
6
:= x
5
+ 1 = 7
Ta đc cu hình mi x = {1, 3, 4, 5, 6, 7} là cu hình k tip. Nu mun tìm tip, ta li nhn thy
rng x
6
= 7 cha đt gii hn trên, nh vy ch cn tng x
6
lên 1 là đc x = {1, 3, 4, 5, 6, 8}.
Vy k thut sinh tp con k tip t tp đã có x có th xây dng nh sau:

(1, 3, 4, 5, 6, 7)
Input: file vn bn SUBSET.INP cha hai s nguyên dng n, k (1 ≤ k ≤ n ≤ 30) cách nhau ít nht
mt du cách
Output: file vn bn SUBSET.OUT các tp con k phn t ca tp {1, 2, , n}
SUBSET.INP SUBSET.OUT
5 3 {1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 3, 4}
{1, 3, 5}
{1, 4, 5}
{2, 3, 4}
{2, 3, 5}
{2, 4, 5}
{3, 4, 5}
PROG02_2.PAS * Thut toán sinh lit kê các tp con k phn t
program Combinations;
const
max = 30;
var
x: array[1 max] of Integer;
n, k, i, j: Integer;
begin
{nh ngha li thit b nhp/xut chun}
Assign(Input, 'SUBSET.INP'); Reset(Input);
Assign(Output, 'SUBSET.OUT'); Rewrite(Output);
ReadLn(n, k);
for i := 1 to k do x[i] := i;
{x
1

u cha lùi đn 0 có ngha là cha phi cu hình kt thúc}
―― begin
Inc(x[i]); {Tng x
i
lên 1,
t các phn t đng sau x
i
b
ng gii hn di ca nó}
for j := i + 1 to k do x[j] := x[j - 1] + 1;
end;
until i = 0;
{Lùi
đn tn 0 có ngha là tt c các phn t đã đt gii hn trên - ht cu hình}
Close(Input); Close(Output);
end.
Bài toán lit kê
Lê Minh Hoàng
{ 9z
III. LIT KÊ CÁC HOÁN V
Ta s lp chng trình lit kê các hoán v ca {1, 2, , n} theo th t t đin.
Ví d vi n = 4, ta phi lit kê đ 24 hoán v:
1.1234 2.1243 3.1324 4.1342 5.1423 6.1432
7.2134 8.2143 9.2314 10.2341 11.2413 12.2431
13.3124 14.3142 15.3214 16.3241 17.3412 18.3421
19.4123 20.4132 21.4213 22.4231 23.4312 24.4321
Nh vy hoán v đu tiên s là (1, 2, , n). Hoán v cui cùng là (n, n-1, , 1).
Hoán v s sinh ra phi ln hn hoán v hin ti, hn th na phi là hoán v va đ ln hn hoán v
hin ti theo ngha không th có mt hoán v nào khác chen gia chúng khi sp th t.
Gi s hoán v hin ti là x = (3, 2, 6, 5, 4, 1), xét 4 phn t cui cùng, ta thy chúng đc xp gim

Ta có nhn xét gì qua ví d này: on cui ca hoán v đc xp gim dn, s x
5
= 4 là s nh nht
trong đon cui gim dn tho mãn điu kin ln hn x
2
= 2. Nu đi ch x
5
cho x
2
thì ta s đc x
2
= 4 và đon cui vn đc sp xp gim dn. Khi đó mun biu din nh nht cho các giá tr
trong đon cui thì ta ch cn đo ngc đon cui.
Trong trng hp hoán v hin ti là (2, 1, 3, 4) thì hoán v k tip s là (2, 1, 4, 3). Ta cng có th
coi hoán v (2, 1, 3, 4) có đon cui gim dn, đon cui này ch gm 1 phn t (4)
Vy k thut sinh hoán v k tip t hoán v hin ti có th xây dng nh sau:
• Xác đnh đon cui gim dn dài nht, tìm ch s i ca phn t x
i
đng lin trc đon cui đó.
iu này đng ngha vi vic tìm t v trí sát cui dãy lên đu, gp ch s i đu tiên tha mãn x
i
< x
i+1
. Nu toàn dãy đã là gim dn, thì đó là cu hình cui.
i := n - 1;
while (i > 0) and (x
i
> x
i+1
) do i := i - 1;

PERMUTE.INP PERMUTE.OUT
3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Bài toán lit kê
Lê Minh Hoàng
{ 10z
PROG02_3.PAS * Thut toán sinh lit kê hoán v
program Permute;
const
max = 12;
var
n, i, k, a, b: Integer;
x: array[1 max] of Integer;
procedure Swap(var X, Y: Integer);
{Th
 tc đo giá tr hai tham bin X, Y}
var
Temp: Integer;
begin
Temp := X; X := Y; Y := Temp;
end;
begin
Assign(Input, 'PERMUTE.INP'); Reset(Input);
Assign(Output, 'PERMUTE.OUT'); Rewrite(Output);
ReadLn(n);
for i := 1 to n do x[i] := i;―

}
Swap(x[k], x[i]); {i ch x
k
và x
i
}
―――――― a := i + 1; b := n;
{L
t ngc đon cui gim dn, a: đu đon, b: cui đon}
―― while a < b do
begin
Swap(x[a], x[b]); {i ch x
a
và x
b
}
Inc(a);
{Ti
n a và lùi b, đi ch tip cho ti khi a, b chm nhau}
Dec(b);
end;
end;
until i = 0;―
{Toàn dãy là dãy gi
m dn - không sinh tip đc - ht cu hình}
Close(Input); Close(Output);
end.
Bài tp:
1. Các chng trình trên x lý không tt trong trng hp tm thng, đó là trng hp n = 0 đi
vi chng trình lit kê dãy nh phân cng nh trong chng trình lit kê hoán v, trng hp k = 0

sinh cng không nm ngoài nhn xét đó. Phng pháp sinh không th sinh ra đc cu hình th
p nu nh cha có cu hình th p - 1, chng t rng phng pháp sinh t ra u đim trong trng
hp lit kê toàn b mt s lng nh cu hình trong mt b d liu ln thì li có nhc đim và
ít tính ph dng trong nhng thut toán duyt hn ch. Hn th na, không phi cu hình ban đu
lúc nào cng d tìm đc, không phi k thut sinh cu hình k tip cho mi bài toán đu đn gin
nh trên (Sinh các chnh hp không lp chp k theo th t t đin chng hn). Ta sang mt chuyên
mc sau nói đn mt phng pháp lit kê có tính ph dng cao hn, đ gii các bài toán lit kê
phc tp hn đó là: Thut toán quay lui (Back tracking).
Bài toán lit kê
Lê Minh Hoàng
{ 12z
§
3. THUT TOÁN QUAY LUI
Thut toán quay lui dùng đ gii bài toán lit kê các cu hình. Mi cu hình đc xây dng
bng cách xây dng tng phn t, mi phn t đc chn bng cách th tt c các kh nng.
Gi thit cu hình cn lit kê có dng (x
1
, x
2
, , x
n
). Khi đó thut toán quay lui thc hin qua các
bc sau:
1) Xét tt c các giá tr x
1
có th nhn, th cho x
1
nhn ln lt các giá tr đó. Vi mi giá tr th
gán cho x
1

) bng cách th cho x
1
nhn ln lt các giá tr có th. Vi mi giá tr th gán cho x
1
li
lit kê tip cu hình n - 1 phn t (x
2
, x
3
, , x
n
).
Mô hình ca thut toán quay lui có th mô t nh sau:
{Th
 tc này th cho x
i
nh
n ln lt các giá tr mà nó có th nhn}
procedure Try(i: Integer);
begin
for (mi giá tr V có th gán cho x
i
) do
begin
<Th cho x
i
:= V>;
if (x
i
là phn t cui cùng trong cu hình) then

1
, x
2
, , x
n
). Ta s lit kê các dãy này bng cách th
dùng các giá tr {0, 1} gán cho x
i
. Vi mi giá tr th gán cho x
i
li th các giá tr có th gán cho
x
i+1
.Chng trình lit kê bng thut toán quay lui có th vit:
PROG03_1.PAS * Thut toán quay lui lit kê các dãy nh phân đ dài n
program BinaryStrings;
const
max = 30;
var
x: array[1 max] of Integer;
n: Integer;
procedure PrintResult;
{In c
u hình tìm đc, do th tc tìm đ quy
Try g
i khi tìm ra mt cu hì nh}
var
i: Integer;
begin
for i := 1 to n do Write(x[i]);

end;
end;
begin
Assign(Input, 'BSTR.INP'); Reset(Input);
Assign(Output, 'BSTR.OUT'); Rewrite(Output);
ReadLn(n);
{Nh
p d liu}
Try(1);
{Th
 các cách chn giá tr x
1
}
Close(Input);
Close(Output);
end.
Ví d: Khi n = 3, cây tìm kim quay lui nh sau:
Try(3)
Try(2)
Try(3) Try(3) Try(3)
Try(2)
Try(1)
x
1
:= 0
x
1
:= 1
x
2

:= 0
x
3
:= 1
000
001
010
011
100
101
110
111
result
Hình 2: Cây tìm kim quay lui trong bài toán lit kê dãy nh phân
Bài toán lit kê
Lê Minh Hoàng
{ 14z
II. LIT KÊ CÁC TP CON K PHN T
Input/Output có khuôn dng nh trong PROG02_2.PAS
 lit kê các tp con k phn t ca tp S = {1, 2, , n} ta có th đa v lit kê các cu hình (x
1
, x
2
,
, x
k
)  đây các x
i
∈ S và x
1

t 1 (=x
0
+ 1) đn n - k + 1, vi mi giá tr đó, xét tip tt
c các cách chn x
2
t x
1
+ 1 đn n - k + 2, c nh vy khi chn đc đn x
k
thì ta có mt cu
hình cn lit kê. Chng trình lit kê bng thut toán quay lui nh sau:
PROG03_2.PAS * Thut toán quay lui lit kê các tp con k phn t
program Combinations;
const
max = 30;
var
x: array[0 max] of Integer;
n, k: Integer;
procedure PrintResult;
(*In ra t
p con {x
1
, x
2
, , x
k
}*)
var
i: Integer;
begin

i
,  chng trình lit kê dãy nh phân ta
th chn các giá tr 0 hoc 1 còn  chng trình lit kê các tp con k phn t ta th chn x
i
là mt
trong các giá tr nguyên t x
i-1
+ 1 đn n - k + i. Qua đó ta có th thy tính ph dng ca thut toán
quay lui: mô hình cài đt có th thích hp cho nhiu bài toán, khác vi phng pháp sinh tun t,
vi mi bài toán li phi có mt thut toán sinh k tip riêng làm cho vic cài đt mi bài mt khác,
bên cnh đó, không phi thut toán sinh k tip nào cng d cài đt.
III. LIT KÊ CÁC CHNH HP KHÔNG LP CHP K
 lit kê các chnh hp không lp chp k ca tp S = {1, 2, , n} ta có th đa v lit kê các cu
hình (x
1
, x
2
, , x
k
)  đây các x
i
∈ S và khác nhau đôi mt.
Nh vy th tc Try(i) - xét tt c các kh nng chn x
i
- s th ht các giá tr t 1 đn n, mà các giá
tr này cha b các phn t đng trc chn. Mun xem các giá tr nào cha đc chn ta s dng
k thut dùng mng đánh du:
• Khi to mt mng c
1
, c

i
đã nhn mt giá tr khác ri thì các phn
t đng sau: x
i+1
, x
i+2
hoàn toàn có th nhn li giá tr j đó. iu này hoàn toàn hp lý trong
phép xây dng chnh hp không lp: x
1
có n cách chn, x
2
có n - 1 cách chn, Lu ý rng khi
th tc Try(i) có i = k thì ta không cn phi đánh du gì c vì tip theo ch có in kt qu ch
không cn phi chn thêm phn t nào na.
Input: file vn bn ARRANGES.INP cha hai s nguyên dng n, k (1 ≤ k ≤ n ≤ 20) cách nhau ít
nht mt du cách
Output: file vn bn ARRANGES.OUT ghi các chnh hp không lp chp k ca tp {1, 2, , n}
ARRANGES.INP ARRANGES.OUT
3 2 1 2
1 3
2 1
2 3
3 1
3 2
PROG03_3.PAS * Thut toán quay lui lit kê các chnh hp không lp chp k
program Arranges;
const
max = 20;
var
x: array[1 max] of Integer;

u đã chn đc đn xk thì ch vic in kt qu}
―― else
begin
c[j] := False; {ánh du: j đã b chn}
―――――――― Try(i + 1);
{Th
 tc này ch xét nhng giá tr còn t do gán cho x
i+1
, t
c là s không chn phi j}
―― c[j] := True;
{B
 đánh du: j li là t do, bi sp ti s th mt cách chn khác ca x
i
}
―――――――― end;
end;
end;
begin
Assign(Input, 'ARRANGES.INP'); Reset(Input);
Assign(Output, 'ARRANGES.OUT'); Rewrite(Output);
ReadLn(n, k);
FillChar(c, SizeOf(c), True);
{T
t c các s đu cha b chn}
Try(1);
{Th
 các cách chn giá tr ca x
1
}

3. Vì s phn t thc s ca mng x là không c đnh nên th tc PrintResult dùng đ in ra 1 cách
phân tích phi có thêm tham s cho bit s in ra bao nhiêu phn t.
4. Th tc đ quy Try(i) s th các giá tr có th nhn ca x
i
(x
i
≥ x
i - 1
)
5. Khi nào thì in kt qu và khi nào thì gi đ quy tìm tip ?
Lu ý rng t
i - 1
là tng ca tt c các phn t t x
1
đn x
i-1
do đó
• Khi t
i
= n tc là (x
i
= n - t
i - 1
) thì in kt qu
• Khi tìm tip, x
i+1
s phi ln hn hoc bng x
i
. Mt khác t
i+1

đc na.
Mt cách d hiu ta gi đ quy tìm tip khi giá tr x
i
đc chn còn cho phép chn thêm mt
phn t khác ln hn hoc bng nó mà không làm tng vt quá n. Còn ta in kt qu ch khi
x
i
mang giá tr đúng bng s thiu ht ca tng i-1 phn t đu so vi n.
6. Vy th tc Try(i) th các giá tr cho x
i
có th mô t nh sau: (đ tng quát cho i = 1, ta đt x
0
=
1 và t
0
= 0).
• Xét các giá tr ca x
i
t x
i - 1
đn (n - t
i-1
) div 2, cp nht t
i
:= t
i - 1
+ x
i
và gi đ quy tìm tip.
• Cui cùng xét giá tr x

procedure Init;
{Kh
i to}
begin
ReadLn(n);
x[0] := 1;
t[0] := 0;
end;
procedure PrintResult(k: Integer);
var
i: Integer;
begin
Write(n,' = ');
for i := 1 to k - 1 do Write(x[i], '+');
WriteLn(x[k]);
end;
procedure Try(i: Integer);
var
j: Integer;
begin
for j := x[i - 1] to (n - T[i - 1]) div 2 do
{Tr
ng hp còn chn tip x
i+1
}
begin
x[i] := j;
Bài toán lit kê
Lê Minh Hoàng
{ 18z

Vy mt nghim ca bài toán s đc bit khi ta tìm ra đc v trí ct ca nhng quân hu.
• Nu ta đnh hng ông (Phi), Tây (Trái), Nam (Di), Bc (Trên) thì ta nhn thy rng:
♦ Mt đng chéo theo hng ông Bc - Tây Nam (B-TN) bt k s đi qua mt s ô, các ô
đó có tính cht: Hàng + Ct = C (Const). Vi mi đng chéo B-TN ta có 1 hng s C và
vi mt hng s C: 2 ≤ C ≤ 2n xác đnh duy nht 1 đng chéo B-TN vì vy ta có th đánh
ch s cho các đng chéo B- TN t 2 đn 2n
♦ Mt đng chéo theo hng ông Nam - Tây Bc (N-TB) bt k s đi qua mt s ô, các ô
đó có tính cht: Hàng - Ct = C (Const). Vi mi đng chéo N-TB ta có 1 hng s C và
vi mt hng s C: 1 - n ≤ C ≤ n - 1 xác đnh duy nht 1 đng chéo N-TB vì vy ta có th
đánh ch s cho các đng chéo N- TB t 1 - n đn n - 1.
Bài toán lit kê
Lê Minh Hoàng
{ 19z
12345678
1
2
3
4
5
6
7
N
S
EW
8
Hình 4: ng chéo B-TN mang ch s 10 và đng chéo N-TB mang ch s 0, ô chung (5, 5)
Cài đt:
1. Ta có 3 mng logic đ đánh du:
•
Mng a[1 n]. a

4. Khi th đt đc quân hu th i vào ct j, nu đó là quân hu cui cùng (i = n) thì ta có mt
nghim. Nu không:
• Trc khi gi đ quy tìm cách đt quân hu th i + 1, ta đánh du ct và 2 đng chéo b quân
hu va đt khng ch (a
j
= b
i+j
= c
i-j
:= FALSE) đ các ln gi đ quy tip sau chn cách đt
các quân hu k tip s không chn vào nhng ô nm trên ct j và nhng đng chéo này na.
•
Sau khi gi đ quy tìm cách đt quân hu th i + 1, có ngha là sp ti ta li th mt cách đt
khác cho quân hu th i, ta b đánh du ct và 2 đng chéo b quân hu va th đt khng ch
(a
j
= b
i+j
= c
i-j
:= TRUE) tc là ct và 2 đng chéo đó li thành t do, bi khi đã đt quân hu i
sang v trí khác ri thì ct và 2 đng chéo đó hoàn toàn có th gán cho mt quân hu khác
Hãy xem li trong các chng trình lit kê chnh hp không lp và hoán v v k thut đánh du. 
đây ch khác vi lit kê hoán v là: lit kê hoán v ch cn mt mng đánh du xem giá tr có t do
không, còn bài toán xp hu thì cn phi đánh du c 3 thành phn: Ct, đng chéo B-TN,
đng chéo N- TB. Trng hp đn gin hn: Yêu cu lit kê các cách đt n quân xe lên bàn c
nxn sao cho không quân nào n quân nào chính là bài toán lit kê hoán v
Input: file vn bn QUEENS.INP cha s nguyên dng n ≤ 12
Output: file vn bn QUEENS.OUT, mi dòng ghi mt cách đt n quân hu
Bài toán lit kê

{M
i đng chéo ông Bc - Tây Nam đu t do}
――FillChar(c, SizeOf(c), True);
{M
i đng chéo ông Nam - Tây Bc đu t do}
end;
procedure PrintResult;
var
i: Integer;
begin
for i := 1 to n do Write('(', i, ', ', x[i], '); ');
WriteLn;
end;
procedure Try(i: Integer);
{Th
 các cách đt quân hu th i vào hàng i}
var
j: Integer;
begin
for j := 1 to n do
if a[j] and b[i + j] and c[i - j] then
{Ch
 xét nhng ct j mà ô (i, j)
ch
a
b
 khng ch}
――――――begin
x[i] := j;
{Th

nó s gi đ quy đ tìm tip x
i+1
có ngha là quá trình s duyt tin sâu xung phía di
đn tn nút lá, sau khi đã duyt ht các nhánh, tin trình lùi li th áp đt mt giá tr khác cho x
i
, đó
chính là ngun gc ca tên gi "thut toán quay lui"
Bài tp:
1. Mt s chng trình trên x lý không tt trong trng hp tm thng (n = 0 hoc k = 0), hãy
khc phc các li đó
2. Vit chng trình lit kê các chnh hp lp chp k ca n phn t
3. Cho hai s nguyên dng l, n. Hãy lit kê các xâu nh phân đ dài n có tính cht, bt k hai xâu
con nào đ dài l lin nhau đu khác nhau.
4. Vi n = 5, k = 3, v cây tìm kim quay lui ca chng trình lit kê t hp chp k ca tp {1, 2, ,
n}
5. Lit kê tt c các tp con ca tp S gm n s nguyên {S
1
, S
2
, , S
n
} nhp vào t bàn phím
6. Tng t nh bài 5 nhng ch lit kê các tp con có max - min ≤ T (T cho trc).
7. Mt dãy (x
1
, x
2
, , x
n
) gi là mt hoán v hoàn toàn ca tp {1, 2, , n} nu nó là mt hoán v và

i
s ng vi ch 2 nút tng ng vi 2 giá tr mà x
i+1
có
th nhn thì cây n cp s có ti 2
n
nút lá, con s này ln hn rt nhiu ln so vi d liu đu vào n.
Chính vì vy mà nu nh ta có thao tác tha trong vic chn x
i
thì s phi tr giá rt ln v chi phí
thc thi thut toán bi quá trình tìm kim lòng vòng vô ngha trong các bc chn k tip x
i+1
, x
i+2
,
Khi đó, mt vn đ đt ra là trong quá trình lit kê li gii ta cn tn dng nhng thông tin đã tìm
đc đ loi b sm nhng phng án chc chn không phi ti u. K thut đó gi là k thut
đánh giá nhánh cn trong tin trình quay lui.
III. MÔ HÌNH K THUT NHÁNH CN
Da trên mô hình thut toán quay lui, ta xây dng mô hình sau:
procedure Init;
begin
<Khi to mt cu hình bt k BESTCONFIG>;
end;
{Th tc này th chn cho x
i
tt c các giá tr nó có th nhn}
procedure Try(i: Integer);
begin
for (Mi giá tr V có th gán cho x

<Thông báo cu hình ti u BESTCONFIG>
end.
Bài toán lit kê
Lê Minh Hoàng
{ 23z
K thut nhánh cn thêm vào cho thut toán quay lui kh nng đánh giá theo tng bc, nu ti
bc th i, giá tr th gán cho x
i
không có hi vng tìm thy cu hình tt hn cu hình
BESTCONFIG thì th giá tr khác ngay mà không cn phi gi đ quy tìm tip hay ghi nhn kt
qu làm gì. Nghim ca bài toán s đc làm tt dn, bi khi tìm ra mt cu hình mi (tt hn
BESTCONFIG - tt nhiên), ta không in kt qu ngay mà s cp nht BESTCONFIG bng cu hình
mi va tìm đc
IV. BÀI TOÁN NGI DU LCH
Bài toán
Cho n thành ph đánh s t 1 đn n và m tuyn đng giao thông hai chiu gia chúng, mng li
giao thông này đc cho bi bng C cp nxn,  đây C
ij
= C
ji
= Chi phí đi đon đng trc tip t
thành ph i đn thành ph j. Gi thit rng C
ii
= 0 vi ∀i, C
ij
= +∞ nu không có đng trc tip t
thành ph i đn thành ph j.
Mt ngi du lch xut phát t thành ph 1, mun đi thm tt c các thành ph còn li mi thành
ph đúng 1 ln và cui cùng quay li thành ph 1. Hãy ch ra cho ngi đó hành trình vi chi phí ít
nht. Bài toán đó gi là bài toán ngi du lch hay bài toán hành trình ca mt thng gia

mi cách th chn x
2
nh vy thì x
3
có th chn mt trong các thành ph mà x
2
có đng đi ti
(ngoài x
1
). Tng quát: x
i
có th chn 1 trong các thành ph cha đi qua mà t x
i-1
có đng đi
trc tip ti.(1 ≤
i ≤ n)
3) Nhánh cn: Khi to cu hình BestConfig có chi phí = +∞. Vi mi bc th chn x
i
xem chi
phí đng đi cho ti lúc đó có < Chi phí ca cu hình BestConfig?, nu không nh hn thì th
giá tr khác ngay bi có đi tip cng ch tn thêm. Khi th đc mt giá tr x
n
ta kim tra xem x
n
có đng đi trc tip v 1 không ? Nu có đánh giá chi phí đi t thành ph 1 đn thành ph x
n
cng vi chi phí t x
n
đi trc tip v 1, nu nh hn chi phí ca đng đi BestConfig thì cp
nht li BestConfig bng cách đi mi.