Bây giờ, tôi sẽ giới thiệu tới các bạn một số bài toán ví dụ kinh điển về giải thuật quay lui. Hãy cùng nhau phân tích chúng và đối chiếu lại với phương pháp chung ở bài viết trước để hiểu rõ hơn về lý thuyết phương pháp nhé!
1. Bài toán xếp hậu
Đề bài
Một bàn cờ vua n×nn \times n đang để trống. Cần đặt nn quân hậu khác nhau vào bàn cờ vua sao cho không có hai quân hậu nào tấn công được nhau, biết rằng hai quân hậu sẽ tấn công nhau nếu như chúng đứng cùng hàng, cùng cột hoặc cùng đường chéo.
Input:
- Chứa duy nhất số nguyên dương nn - kích thước bàn cờ.
Ràng buộc:
- 1≤n≤81 \le n \le 8.
Output:
- In ra tất cả các cách xếp nn quân hậu lên bàn cờ n×nn \times n.
Ý tưởng
Trong bài toán xếp hậu, nghiệm có thể được biểu diễn dưới dạng một vector {x1,x2,...,xn}\{x_1, x_2,..., x_n\} thỏa mãn ba điều kiện sau:
- xix_i là tọa độ cột của quân hậu đang đứng ở dòng thứ i [1≤xi≤n]i \ [1 \le x_i \le n].
- Các quân hậu không được đứng cùng một cột, nghĩa là xi≠xj,∀i≠jx_i \ne x_j, \forall i \ne j.
- Hai quân hậu khác nhau không được nằm chung một đường chéo. Đường chéo ở đây có thể là các đường chéo chính [từ trên xuống dưới, từ trái qua phải] hoặc các đường chéo phụ [từ dưới lên trên, từ phải qua trái] [xem hình vẽ].
Dễ nhận thấy, hai ô [x1,y1][x_1, y_1] và [x2,y2][x_2, y_2] sẽ nằm trên cùng đường chéo chính nếu như x1−y1=x2−y2,x_1 - y_1 = x_2 - y_2, và sẽ nằm trên cùng đường chéo phụ nếu như x1+y1=x2+y2x_1 + y_1 = x_2 + y_2. Vậy điều kiện để hai quân hậu xếp ở hai ô [i,xi][i, x_i] và [j,xj][j, x_j] không nằm cùng một đường chéo là: {i−xi≠j−xj.i+xi≠j+xj.\begin{cases}i - x_i \ne j - x_j. \\ i + x_i \ne j + x_j. \end{cases}
Vậy tựu chung lại, khi đã xây dựng được vector nghiệm {x1,x2,...,xi−1},\{x_1, x_2,..., x_{i - 1}\}, thì xix_i tiếp theo được chọn phải thỏa mãn các điều kiện dưới đây:
{xi≠xjj−xj≠i−xjj+xj≠i+xi;∀j:1≤j≤i−1\begin{cases}x_i \ne x_j \\ j - x_j \ne i - x_j \\ j + x_j \ne i + x_i \end{cases}; \forall j: 1 \le j \le i - 1
Để xác định được tập SiS_i là các ứng cử viên cho thành phần xi,x_i, ta có thể thực hiện bằng cách sử dụng các mảng đánh dấu để chương trình trở nênn đơn giản hơn. Cụ thể, khi đặt một quân hậu jj vào ô [j,xj],[j, x_j], ta sẽ đánh dấu luôn cột xj,x_j, đường chéo chính có số hiệu j−xjj - x_j và đường chéo phụ có số hiệu j+xj,j + x_j, thể hiện rằng trên cột này và các đường chéo này đã có một quân hậu.
Độ phức tạp của giải thuật sẽ là O[nn],O[n^n], do ta có nn thành phần cần sinh và mỗi thành phần lại có nn khả năng.
Cài đặt
Dưới đây là chương trình cài đặt bằng mô hình đệ quy.
# include
# define task "XEPHAU."
# define inf 1e9 + 7
using namespace std;
const int maxn = 9;
int n, cnt, res[maxn], column[maxn], main_diagonal[maxn], secondary_diagonal[maxn];
// In nghiệm theo dạng: index. x1 x2 ... xn.
void printf_result[]
{
cout