N quân hậu

Nguồn: CLUE OJ – Chương 20: Quay lui (MarisaOJ) Độ khó: Dễ Quay lui Đánh dấu cột / đường chéo

Đề bài

Đếm số lượng cách đặt $n$ quân hậu trên bàn cờ kích cỡ $n \times n$ sao cho không có 2 quân hậu nào tấn công được nhau.

Ví dụ một cách đặt 5 quân hậu (x là quân hậu):

x....
...x.
.x...
....x
..x..

♛
			♛
	♛
				♛
		♛

Input: một số nguyên $n$.

Output: một số nguyên duy nhất là số lượng cách đặt $n$ quân hậu.

Điều kiện: $1 \le n \le 10$.

Nhắc lại luật cờ vua: quân hậu tấn công mọi ô cùng hàng, cùng cột và cùng đường chéo (cả 2 hướng chéo) với nó.

Ví dụ – input

5

Ví dụ – output

10

Lời mở đầu

Bài toán 8 quân hậu là "bài kinh điển số 1" khi học quay lui. Ở bài này mình sẽ đi từ cách ngây thơ nhất (thử mọi hoán vị) tới cách quay lui chuẩn có đánh dấu cột và đường chéo – cách mà các bạn sẽ dùng lại ở rất nhiều bài sau trong chương. Mỗi khối code đều có khung chạy tay để em thấy rõ ngăn xếp lời gọi đệ quy lớn lên rồi co lại như thế nào.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test10 testÝ tưởngmỗi hàng 1 hậuCách 1thử n! hoán vịCách 2quay luiTổng kếtkết quả chạy

Bộ testBộ test chính thức có gì?

Số test	Giá trị n	Test có đáp án 0
10	1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (mỗi giá trị 1 test)	2 test

Đề không chia subtask: bộ test có đúng mỗi giá trị $n$ từ 1 đến 10 một test. Có những $n$ không có cách đặt nào (đáp án 0) – em thử nghĩ xem đó là $n$ nào nhé (gợi ý: thử bằng widget bên dưới). Kết quả chạy thật của các cách (giới hạn 1 giây):

Mức	Điều kiện	Test	Cách 1 (hoán vị)	Cách 2 (quay lui)
$n \le 9$	$1 \le n \le 9$	1–9	9/9	9/9
$n = 10$	$n = 10$	10	1/1	1/1

(Cả 2 cách C++ đều qua hết; khác biệt chỉ thấy rõ ở bản Python – xem phần tổng kết.)

Ý tưởngMỗi hàng đúng một quân hậu

Hai quân hậu cùng hàng thì ăn nhau, mà có $n$ quân trên $n$ hàng, nên mỗi hàng có đúng một quân hậu. Tương tự mỗi cột cũng có đúng một quân. Vậy một cách đặt chính là: hàng $i$ đặt hậu ở cột $p_i$, với $p_0, p_1, \dots, p_{n-1}$ là một hoán vị của $0, 1, \dots, n-1$.

Còn lại điều kiện đường chéo. Hai ô $(i_1, j_1)$ và $(i_2, j_2)$ cùng đường chéo khi và chỉ khi:

• cùng chéo "↘": $i_1 - j_1 = i_2 - j_2$;
• cùng chéo "↙": $i_1 + j_1 = i_2 + j_2$.

Gộp lại: cùng đường chéo $\Leftrightarrow |j_1 - j_2| = |i_1 - i_2|$.

Quay lui

Đặt hậu lần lượt từng hàng $i = 0, 1, \dots$. Ở hàng $i$ thử từng cột $j$; nếu ô $(i, j)$ không bị các quân đã đặt tấn công thì đặt vào và gọi đệ quy sang hàng $i + 1$. Đặt được tới hàng $n$ là có thêm 1 cách. Gọi xong thì nhấc quân hậu ra (quay lui) để thử cột tiếp theo.

Điểm mạnh của quay lui: hễ một hàng không còn ô nào đặt được thì cả nhánh bị cắt bỏ, không phải đi hết mọi hoán vị. Em chọn $n$ rồi bấm Tiếp để xem bàn cờ và cây quay lui lớn dần (nút xanh = một cách đặt, nút đỏ = ngõ cụt):

n =

Ví dụ nhanh:

Cách 1Thử mọi hoán vị – O(n!·n²)

Cách "không cần nghĩ": dùng next_permutation sinh lần lượt mọi hoán vị $p$ của $0..n-1$ (đã đảm bảo khác hàng, khác cột), với mỗi hoán vị kiểm tra mọi cặp hàng $i < j$ xem có cùng đường chéo không.

C++▶ Chạy tay từng dòng codeCách 1: sinh mọi hoán vị bằng next_permutation, hàm ok() kiểm tra đường chéo.

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hai vòng for trong ok() được gộp vào bước ở dòng if (mỗi cặp i, j một bước) cho gọn.

1. abs(p[i] - p[j]) == j - i: khoảng cách cột bằng khoảng cách hàng → cùng đường chéo → hoán vị hỏng, return false ngay.
2. Vòng do { ... } while(next_permutation(p, p + n)); bắt đầu từ hoán vị tăng dần $0, 1, \dots, n-1$ và đi qua đủ $n!$ hoán vị.

Không gian$O(n)$

Thời gian$O(n! \cdot n^2)$

Với $n = 10$: $10! = 3\,628\,800$ hoán vị, mỗi hoán vị thường bị loại sau vài phép so sánh, nên vẫn đủ nhanh.

Kết quả chạy thật: Bản C++ đúng 10/10 test; test đúng chạy lâu nhất 0.04s. Còn bản Python đúng 9/10 test, quá thời gian ở test 10; test đúng chạy lâu nhất 0.36s (dùng itertools.permutations).

Cách 2Quay lui + đánh dấu cột, đường chéo

Thay vì sinh trọn hoán vị rồi mới kiểm tra, ta kiểm tra ngay khi đặt từng quân. Để kiểm tra trong $O(1)$, dùng 3 mảng đánh dấu:

• cot[j]: cột $j$ đã có hậu chưa;
• c1[i + j]: đường chéo "↙" có tổng $i + j$ (từ $0$ đến $2n - 2$) đã có hậu chưa;
• c2[i - j + n]: đường chéo "↘" có hiệu $i - j$ (cộng thêm $n$ cho khỏi âm) đã có hậu chưa.

C++▶ Chạy tay từng dòng codeCách 2: quay lui từng hàng, 3 mảng đánh dấu cột và 2 loại đường chéo.

Dữ liệu vào (stdin) – sửa thoải mái4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(i == n): đã đặt xong các hàng $0..n-1$ → đếm thêm 1 cách rồi return.
2. Đặt hậu = bật 3 dấu, gọi Try(i + 1), rồi tắt 3 dấu – đây là bước "quay lui" trả bàn cờ về như cũ cho lần thử cột kế tiếp.
3. Ngăn xếp lời gọi sâu tối đa $n + 1$ tầng (Try(0) … Try(n)), nên không lo tràn ngăn xếp.

Không gian$O(n)$

Thời giannhỏ hơn nhiều so với $O(n!)$

Số nút thật sự được thăm nhỏ hơn $n!$ rất nhiều (với $n = 10$ chỉ khoảng 35 nghìn lần gọi Try) nhờ cắt nhánh sớm.

Kết quả chạy thật: Bản C++ đúng 10/10 test; test đúng chạy lâu nhất 0.01s. Còn bản Python đúng 10/10 test; test đúng chạy lâu nhất 0.04s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Thử mọi hoán vị	C++	10/10	0.04s	Full
	Python	9/10	> 1s	Quá thời gian test 10 (n = 10)
2. Quay lui + đánh dấu	C++	10/10	0.01s	Full
	Python	10/10	0.04s	Full

Ghi chú của mình: vì $n \le 10$ nên cả 2 cách C++ đều qua hết 10 test; cách thử hoán vị bằng Python thì quá thời gian ở $n = 10$. Cách quay lui có đánh dấu chạy nhanh hơn hẳn và là "khuôn mẫu" cho cả chương: chọn → đánh dấu → gọi đệ quy → bỏ đánh dấu.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇