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++

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.

n
4
7
8
9
10
11
12
13
14
Hn
2
40
92
352
724
2680
14200
73712
365596

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).

Bạn thấy bài viết này như thế nào?: 
Average: 9.8 (24 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Các cách để save a node in Drupal

Các cách để save a node in Drupal

Every day, millions of nodes are saved. It happens every time content is created, migrated, or updated. It's probably the most common content management task in Drupal.

Giới thiệu 5 Hurdles cần phải biết tại Drupal 8

Giới thiệu 5 Hurdles cần phải biết tại Drupal 8

This means that if you have a 5-year-old Drupal 6 site, you will find major value in upgrading directly to Drupal 8. Many other benefits can justify the cost, including an easier to administer, responsive site.

Mua bán subscribe và cơn khát nổi tiếng của giới trẻ

Mua bán subscribe và cơn khát nổi tiếng của giới trẻ

Tuy chỉ mới xuất hiện trên Facebook chưa lâu  nhưng dịch vụ bán “sub” đang trở thành một trong những 

Tomdesgin.vn

 

Drupal Services