Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n bằng C/C++

Xem lại lý thuyết thuật toán Back Track

>> Lý thuyết về thuật toán quay lui Back Track

Bài toán:  Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ n x n sao cho chúng không ăn được nhau bằng thuật toán Back Track.

Giải. Bàn cờ có n hàng được đánh số từ 0 đến n-1, n cột được đánh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đánh số từ 0 đến 2*n -2, 2 *n -1 đường chéo ngược được đánh số từ 2*n -2. Ví dụ: với bàn cờ 8 x 8, chúng ta có 8 hàng được đánh số từ 0 đến 7, 8 cột được đánh số từ 0 đến 7, 15 đường chéo xuôi, 15 đường chéo ngược được đánh số từ 0..15.

Thuật toán Back Track

Vì trên mỗi hàng chỉ xếp được đúng một quân hậu, nên chúng ta chỉ cần quan tâm đến quân hậu được xếp ở cột nào. Từ đó dẫn đến việc xác định bộn thành phần x1, x2,.., xn, trong đó xi= j được hiểu là quân hậu tại dòng i xếp vào cột thứ j. Giá trị của i được nhận từ 0 đến n-1; giá trị của j cũng được nhận từ 0 đến n-1, nhưng thoả mãn điều kiện ô (i,j) chưa bị quân hậu khác chiếu đến theo cột, đường chéo xuôi, đường chéo ngược.

Việc kiểm soát theo hàng ngang là không cần thiết vì trên mỗi hàng chỉ xếp đúng một quân hậu. Việc kiểm soát theo cột được ghi nhận nhờ dãy biến logic aj với qui ước aj=1 nếu cột j còn trống, cột aj=0 nếu cột j không còn trống. Để ghi nhận đường chéo xuôi và đường chéo ngược có chiếu tới ô (i,j) hay không, ta sử dụng phương trình i + j = const và i - j = const, đường chéo thứnhất được ghi nhận bởi dãy biến bj, đường chéo thứ 2 được ghi nhận bởi dãy biến cj với qui ước nếu đường chéo nào còn trống thì giá trị tương ứng của nó là 1 ngược lại là 0. Như vậy, cột j được chấp nhận khi cả 3 biến aj, bi+j, ci+j đều có giá trị 1. Các biến này phải được khởi đầu giá trị 1 trước đó, gán lại giá trị 0 khi xếp xong quân hậu thứ i và trả lại giá trị 1 khi đưa ra kết quả.

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <dos.h>

#define N  8

#define D  (2*N-1)

#define SG  (N-1)

#define TRUE 1

#define FALSE 0

void hoanghau(int);

void inloigiai(int  loigiai[]); FILE *fp;

int  A[N], B[D], C[D], loigiai[N];

int soloigiai = 0;

void hoanghau(int i){

 int j;

 for (j = 0; j < N; j++){

  if (A[j] && B[i - j + SG] && C[i + j]) {

   loigiai[i] = j;

   A[j] = FALSE;

   B[i - j + SG] = FALSE;

   C[i + j] = FALSE;

   if (i == N - 1){

    soloigiai++;

    inloigiai(loigiai);

    delay(500);

   }

   else

    hoanghau(i + 1);

   A[j] = TRUE;

   B[i - j + SG] = TRUE;

   C[i + j] = TRUE;

  }

 }

}

void inloigiai(int *loigiai){

 int j;

 printf("\n Lời giải %3d:", soloigiai);

 fprintf(fp, "\n Lời giải %3d:", soloigiai);

 for (j = 0; j < N; j++){

  printf("%3d", loigiai[j]);

  fprintf(fp, "%3d", loigiai[j]);

 }

}

void main(void){

 int i; clrscr();

 fp = fopen("loigiai.txt", "w");

 for (i = 0; i < N; i++)

  A[i] = TRUE;

 for (i = 0; i < D; i++){

  B[i] = TRUE;

  C[i] = TRUE;

 }

 hoanghau(0);

 fclose(fp);

}

Dưới đây là số cách xếp hậu ứng với n.

Nghiệm đầu tiên mà chương trình tìm được ứng với n =8 là x =(1, 5, 8, 6, 3, 7, 2, 4).