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

 

Sergio Aguero mua tặng siêu xe McLaren Spider có giá 166.000 bảng

Hai đồng đội của Sergio Aguero là Benjamin Mendy và Fabian Delph đã công nhận điều này trong cuộc trả lời vấn đáp nhanh với ứng dụng trực tuyến hẹn hò Tinder cuối năm ngoái.

Best To Do Apps for Android Phones

Best To Do Apps for Android Phones

Android phones are lovely little gadgets that make your life absolutely fun, simply because they can do so many things that other phones cannot.

11 Thủ thuật tìm kiếm trên Google Search

11 Thủ thuật tìm kiếm trên Google Search

Tìm từ ngữ, trang web, tìm theo thời gian, loại tập tin, tính toán, hay thậm chí đổi đơn vị trên Google Search đều có "chiêu" cả!

Công ty diệt chuột T&C

 

Diet con trung