Bài toán xếp hậu

Phân tích, cài đặt thuật toán quay lui để giải bài toán xếp hậu: xếp n con hậu vào bàn cờ n x n sao cho không con nào khống chế lẫn nhau.

Bài toán

Có một bàn cờ kích thước n x n (n ≥ 4). Yêu cầu: tìm tất cả các cách để đặt n con hậu trên bàn cờ sao cho không có con nào khống chế (*) lẫn nhau. Biết rằng, một con hậu có thể khống chế tất cả các quân cờ trên hàng ngay, cột dọc và hai đường chéo đi qua vị trí của nó.

	0	1	2	3	4	5	6	7			a	b	c	d	e	f	g	h
0										8
1										7
2										6
3										5
4										4
5										3
6										2
7										1
	Ký hiệu ô cờ để tiện lập trình										Ký hiệu ô cờ theo chuẩn quốc tế

Hình 1. Bàn cờ vua 8x8 (ký hiệu các ô cờ và ví dụ đặt 8 quân hậu)

(*) người ta thường sử dụng từ ăn, tuy nhiên, "hoàng hậu lại đi ăn các quân cờ" thì có vẻ không hợp lý nên T thay từ ăn bởi từ khống chế.

Phân tích

Biểu diễn bàn cờ

Do yêu cầu của bài toán là tìm các vị trí để đặt n quân hậu nên thay vì sử dụng mảng 2 chiều ta chỉ cần sử dụng mảng một chiều h[0..n-1] trong đó h[i] thuộc đoạn [0..n-1] là vị trí (cột) của quân hậu thứ i. Với ví dụ ở hình 1, mảng h sẽ là: [3 6 2 7 2 4 1 5] (quân hậu hàng 0 sẽ ở cột 3, quân hậu hàng 1 sẽ ở cột 6,...).

Đánh dấu các vị trí đã bị khống chế

Trong quá trình thử (đệ quy - quay lui), ta sẽ lần lượt đặt quân hậu tại một số vị trí trong bàn cờ. Mỗi lần thử đặt một quân hậu tại một ô nào đó thì phải đánh dấu các ô trong hàng, cột và hai đường chéo đi qua ô vừa đặt để các lần thử tiếp theo không đặt quân hậu nào khác vào các ô này (vì chũng đã bị khống chế bởi 1 quân hậu).

Để tiện trong việc trình bày ý tưởng cũng như lập trình, ta sẽ ký hiệu các đường chéo chính (theo hướng tây nam - đông bắc) và các đường chéo phụ (theo hướng tây bắc - đông nam) như hình 2. Ta thấy ô (i, j) sẽ thuộc:

• Đường chéo chính có số thứ tự là (i + j),
• Đường chéo phụ có số thứ tự là (i - j + n).

Mỗi lần đặt một con hậu tại vị trí (i, j) nào đó, ta phải đánh dấu các ô trên hàng i, cột j, đường chéo chính (i + j) và đường chéo phụ (i - j + n) để sau này không được đặt con hậu nào vào những vị trí này. Do đó, thay vì phải lưu phần đánh dấu cho tất cả các ô trên bàn cờ (nghĩa là cần một mảng n x n), ta chỉ cần đánh dấu cho các hàng, cột, đường chéo chính và đường chéo phụ tương ứng (nghĩa là cần hai mảng một chiều n phần tử để đánh dấu các hàng, cột và cần thêm hai mảng một chiều 2n+1 phần tử để đánh dấu các đường chéo).

	0	1	2	3	4	5	6	7			0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7		0	7	8	9	10	11	12	13	14
1	1	2	3	4	5	6	7	8		1	6	7	8	9	10	11	12	13
2	2	3	4	5	6	7	8	9		2	5	6	7	8	9	10	11	12
3	3	4	5	6	7	8	9	10		3	4	5	6	7	8	9	10	11
4	4	5	6	7	8	9	10	11		4	3	4	5	6	7	8	9	10
5	5	6	7	8	9	10	11	12		5	2	3	4	5	6	7	8	9
6	6	7	8	9	10	11	12	13		6	1	2	3	4	5	6	7	8
7	7	8	9	10	11	12	13	14		7	0	1	2	3	4	5	6	7
	Số thứ tự các đường chéo chính										Số thứ tự các đường chéo phụ

Hình 2. Số thứ tự các đường chéo trên bàn cờ
(các số có màu đỏ thẩm)

Ý tưởng

Sử dụng thuật toán quay lui để thử đặt lần lượt n quân hậu trên bàn cờ:

• Đầu tiên, thử đặt quân hậu 0 (ở hàng 0) vào các cột (có ncách đặt), Với mỗi vị trí của quân hậu này:
  • Thử đặt quân hậu 1 (ở hàng 1) vào các cột mà không bị quân hậu 0 khống chế, Với mỗi vị trí của quân hậu này:
    • Thử đặt quân hậu 2 (ở hàng 2) vào các cột mà không bị quân hậu 0 và quân hậu 1 khống chế, và cứ tiếp tục như vậy với các quân hậu tiếp theo.

Tìm được vị trí đặt cho quân hậu cuối cùng (mà không bị n-1 quân hậu trước đó khống chế) nghĩa là ta đã tìm được một phương án cho bài toán.

Mỗi lần thử đặt một con hậu tại một vị trí (i, j) nào đó thì phải đánh dấu khống chế cho cột j, đường chéo chính (i + j) và đường chéo phụ (i - j + n) sau đó mới thử đặt các con hậu tiếp theo (để khỏi đặt vào các hàng, cột, đường chéo đã bị các con hậu trước đó khống chế). Chú ý: do cách duyệt là từ hàng 0 đến hàng (n - 1) nên không cần phải đánh dấu khống chế cho hàng.

Khi quay lui để thử đặt vị trí khác thì phải hủy đánh dấu các hàng, cột và đường chéo tương ứng.