Bài toán

Chúng ta cần đặt 8 con hậu vào bàn cờ 8 * 8 sao cho chúng không tấn công nhau, tức là không có cặp con hậu nào nằm cùng hàng, cùng cột, cùng đường chéo.

Bài toán này là một ví dụ nổi tiếng về việc dùng các phương pháp thử và sai và phương pháp quay lui.

Phân tích và thiết kế thuật toán

Mấu chốt của thuật toán rõ ràng là xét xem có thể đặt quân hậu tiếp theo như thế nào. Theo luật cờ vua, một quân hậu có thể ăn các quân khác nếu nằm trên cùng 1 đường, đường này có thể là :

- Hàng,

- Cột,

- Các đường chéo (đi qua tọa độ vị trí của hậu).

Suy ra rằng mỗi hàng chỉ có thể chứa 1 và chỉ 1 quân hậu. Nên việc chọn vị trí cho quân hậu thứ i có thể giới hạn được ở hàng thứ i. Như thế tham số i trở thành chỉ hàng, và quá trình chọn vị trí cho quân hậu tiến hành trên toàn giá trị có thể có của các cột j.

Ta quy ước :

x[i] // Chỉ quân hậu thứ i : nằm ở hàng i.

x[i] = j // quân hậu thứ i đặt ở cột j;

Để quân hậu i (trên hàng i) chấp nhận cột j thì cột j và 2 đường chéo qua ô <i,j> phải còn trống ( tức là không có quân hậu khác chiếm lĩnh)

Lưu ý rằng trong 2 đường chéo :

- Đường chéo ngược (vuông góc với đường chéo chính) : tất cả các ô đều có tổng 2 tọa độ i và j là hằng số;

- Đường chéo thuận (song song với đường chéo chính) : gồm tất cả các ô(i,j) mà có hiệu các tọa độ (i-j) là hằng số.

Do đó ta sẽ chọn các mảng Boole 1 chiều để biểu diễn các trạng thái này :

a[j] = 1 : Có nghĩa là không có quân hậu nào ở cột.

b[i+j] = 1 : Có nghĩa là không có quân hậu nào ở đường chéo ngược (i+j) .

c[i -j] = 1 : Có nghĩa là không có quân hậu nào ở đường chéo thuận (i- j) .

Vì :

1 ≤ i,j ≤ 8 → 2 ≤ i+j ≤ 16 Và -7 ≤ i - j ≤ 7.

Nên ta có thể khai báo :

int x[8],

a[8],

b[15],

c[15];

Với các dữ liệu đã cho, thì lệnh đặt quân hậu sẽ thể hiện bởi :

x[ i ] = j; // đặt quân hậu thứ i trên cột j.

a[ j ] = 0;//Khi đặt hậu tại cột j , thì cột j không còn trống nữa

b[ i+ j ] = 0;//Các đường chéo tương ứng cũng không còn c[ i - j ] = 0;//trống nữa .

Còn lệnh Dời quân hậu là :

//Làm cho hàng i và các đường chéo tương ứng trở thành trống

a[ j ]= 1;

b[ i+ j ] = 1;

c[ i - j ] = 1;

Còn điều kiện an toàn là ô có tọa độ ( i, j ) nằm ở hàng và các đường chéo chưa bị chiếm (được thể hiện bằng giá trị True). Do đó, có thể được thể hiện bởi biểu thức logic : a[ji ] && b[ i + j ] && c[ i - j ]

Try (i)

{

for (j = 1; j <= 8; j++)

if (a[j] && b[i+j] && c i[ -j])

{

x[i] = j; a[j] = 0; b[i+j] = 0;

c[i-j] = 0;

if (i < 8 )

try (i+1);

else

Xuất(x);

/* Sau khi in 1 lời giải xong, trả lại tình trạng ban đầu còn trống cho hàng a[ j], đường chéo i+j và đường chéo i-j, để tìm lời giải khác */

a[ j ] = 1;

b[i+j] = 1;

c[i-j] = 1;

}

}

Ghi chú :

Thuật toán này tìm được tất cả 92 lời giải. Thực ra là chỉ có 12 lời giải khác nhau thật sự, đó là vì thuật toán không ghi nhận tính đối xứng.