Bài 5: Bộ bài Domino

 Bài 5: Bộ bài Domino với bản đồ số
Bộ bài domino gồm 28 quân đánh số từ 1 đến 28. Mỗi quân bài là một thanh hình chữ nhật được chia làm hai hình vuông bằng nhau. Trong đó người ta ghi các số từ 0 (để trống) đến 6 bằng cách trổ các dấu tròn trắng. Dưới đây liệt kê 28 quân bài domino:

Sắp xếp 28 quân bài domino ta có thể tạo ra một hìmh chữ nhật kích thước 7*8 ô vuông. Mỗi cách sắp xếp như vậy sẽ tạo ra một bản đồ số. Ngược lại, mỗi bản đồ số có thể tương ứng với một số cách xếp.
Ví dụ bản đồ số:
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
tương ứng với hai cách xếp mô tả bởi hai bảng số sau:
16 16 24 18 18 20 12 11
06 06 24 10 10 20 12 11
08 15 15 03 03 17 14 14
08 05 05 02 19 17 28 26
23 01 13 02 19 07 28 26
23 01 13 25 25 07 21 04
27 27 22 22 09 09 21 04

16 16 24 18 18 20 12 11
06 06 24 10 10 20 12 11
08 15 15 03 03 17 14 14
08 05 05 02 19 17 28 26
23 01 13 02 19 07 28 26
23 01 13 25 25 07 21 04
27 27 22 22 09 09 21 04
Bài toán đặt ra là cho trước một bảnng số, hãy liệt kê tất cả các cách xếp có thể tạo ra từ nó.
Dữ liệu vào từ file DOMINO.INP là ma trận 7*8 mô tả bản đồ số ban đầu.
Kết quả ghi ra file DOMINO.OUT dòng đầu là số lượng p cách xếp tìm được. Tiếp theo là p nhóm dòng, mỗi nhóm gồm 7 dòng ghi các dòng của các bảng tương ứng với một bảng số tìm được.
Hướng dẫn giải
Với mỗi quân bài domino ta có thể có hai khả năng xếp vào hình chữ nhật: hoặc là đặt nằm ngang, hoặc là đặt nằm dọc. Ta sẽ thử tất cả các cách để đặt chúng vào hình chữ nhật cho đến khi nào đặt được cả 28 quân bài vào hình chữ nhật thì đó là một trong các cách xếp thoả mãn. Mỗi cách xếp thoả mãn sẽ được lưu vào mảng L[1..10,1..7,1..8].
Văn bản chương trình
Program Bo_bai_domino_voi_cac_ban_do_so;
Type Bandoso = array[1..7,1..8] of byte;
Sothutu = array[0..6,0..6] of byte;
Cauhinh = array[1..10,1..7,1..8] of byte;

Const Fi = ’DOMINO.INP’;
Fo = ’DOMINO.OUT’;
D : array[1..2] of byte = (0,1);
C : array[1..2] of byte = (1,0);

Var A,B : Bandoso;
L : Cauhinh;
Gt : Sothutu;
TS : set of byte;
T,dem: byte;
F : Text;

Procedure Read_inp;
Var i,j,k : byte;
Begin
Assign(F,Fi); Reset(F); dem:= 0;
For i:= 1 to 7 do
begin
For j:= 1 to 8 do read(F,A[i,j]);
Readln(F);
end;
For i:= 0 to 6 do
For j:= i to 6 do
begin
Inc(k); Gt[i,j]:= k; Gt[j,i]:= k;
end;
Close(F);
End;

Function Sott(x: byte) : String;
Var S : String;
Begin
Str(X,S);
If length(S) = 1 then S:= ’0’ + S;
Sott:= S;
End;

Procedure Result;
Var i,j : byte;
Begin
Inc(dem);
For i:= 1 to 7 do
For j:= 1 to 8 do L[dem][i,j]:= B[i,j];
End;

Procedure Try(i,j : byte);
Var k,u,v,x : byte;
Begin
While (j < 8) and (B[i,j] > 0) do inc(j);
If (j = 8) and (B[i,j] > 0) then Try(i+1,1) else
For k:= 1 to 2 do
begin
u:= i + D[k]; v:= j + C[k];
If (u in [1..7]) and (v in [1..8]) and (B[u,v] = 0) then
begin
x:= Gt[A[i,j],A[u,v]];
If not (x in Ts) then
begin
Inc(t); Ts:= Ts + [x];
B[i,j]:= x; B[u,v]:= x;
If t = 28 then Result else
If v = 8 then Try(i+1,1) else Try(i,v+1);
Dec(t); Ts:= Ts - [x];
B[i,j]:= 0; B[u,v]:= 0;
end
end;
end;
End;

Procedure Write_out;
Var k,i,j : byte;
Begin
Assign(F,Fo); Rewrite(F);
Writeln(dem);
For k:= 1 to dem do
begin
For i:= 1 to 7 do
begin
For j:= 1 to 8 do write(F,Sott(L[dem][i,j]),’ ’);
Writeln(F);
end;
Writeln(F); Writeln(F);
end;
Close(F);
End;

BEGIN
Read_inp;
Try(1,1);
Write_out;
END.