Giải thuật đệ quy quay lui với bài toán sắp xếp ô chữ thuật ngữ
Võ Công Chương
Cácbạn đã từng gặp và giải đáp các ô chữ thuật ngữ thường xuất hiện trên các tạp chí và
các cuộc thi. Bạn cũng có thể tạo ra được một ô chữ thuật ngữ như thế để giúp vui trong
một cuộc thi nho nhỏ ở trường. Tuy nhiên, vấn đề đặt ra là khi đã có trong tay các từ hàng
ngang, bạn không dễ để sắp xếp chúng trở thành một ô chữ theo từ hàng dọc. Bài viết này
xây dựng giải thuật để tìm tấtcả các phương án sắp xếp các từ hàng ngang theo từ hàng
dọc cho trước,giúp bạn tạo ra một trò chơi ô chữ thuật ngữ như mong muốn.
1.Bài toán:
Chon Từ hàng ngang và một Từ hàng dọc có k kí tự. Hãy tìmtất cả các phương án xây
dựng ô chữ thuật ngữ với các Từ hàngngang đã cho theo Từ hàng dọc ấy.
Ví dụ: Ta có 10 Từ để tạo các hàng ngang: PROGRAM,USES, CRT, UNIT, LABEL,
REAL, BYTE, CHAR, BEGIN, END. Từ > hàng dọc là PASCAL. Ta có tất cả 4
phươngán sắp xếp ô chữ như sau:
Vớibài toán này, ta dùng giải thuật đệ quy quay lui để vét cạn các phươngán.
2. Giải thuật đệ quy quay lui tổng quát:
{Tìm bước đi thứ i cho phương án}
Begin
FOR [mỗi cách đi] DO
IF [chấp nhận được] THEN
Begin [Thực hiện bước đi];
IF [Thành công] THEN [Thông báo phương án]
ELSE Try(i+1);
{Tìm bước đi thứ i+1}
[Hủy bước đi];
End;
End;
3. Xây dựng các khái niệmxuất hiện trong giải thuật:
- Ô chữ thuật ngữ của bài toán trên là một ma trận có k dòng và mcột (ta chỉ quan tâm
đến số k, k chính là số kí tự củaTừ hàng dọc đã cho trước).
- Phương án là một cách sắp xếp vị trí của k Từ trên k hàngngang.

{hủy bước đi}
End;
End;
{Thủ tục hiển thị phương án tìm được}
Procedure Thong_bao_phuong_an;
Begin
Writeln(’Phuong an tim duoc:’);
FOR i:=1 TO k DO Writeln(D[i]);
End;
Khi đó, trong chương trình chính, thực hiện các công việc sau:
- Nhập dữ liệu cho bài toán; {Các từ hàng ngang và từ hàng dọc}
- Khởi tạo: B[j] : = False; với mọi j=1..n {chưa có từ nào được chọn vào phương án}
- Gọi Try(1);
- Kết thúc.
Hy vọng rằng, với những gì đã trình bày, các bạn trẻ sẽ có thêm một công cụ để có thể tự
tạo ra các chương trình trò chơi ô chữ với nhiều chủ đề khác nhau trong các dịp thi đố vui,
giải trí và học hành. Tuy là một bài toán nhỏ, nhưng cũng mong nhận được ý kiến đóng
góp của bạn đọc nhằm tìm giải thuật tối ưu hơn cho bài toán.