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

 
Mac Pro 2013 bị chê chẳng khác gì nhân vật Darth Vader

Mac Pro 2013 bị chê chẳng khác gì nhân vật Darth Vader

Trong lúc không ít người trầm trồ với thiết kế hình trụ độc đáo, đẹp mắt của Mac Pro 2013 mà Apple vừa ra mắt tại WWDC 2013, vẫn có ý kiến chê sản phẩm này chẳng khác gì nhân vật Darth Vader trong phim Chiến tranh giữa các vì sao, hay tệ hơn, y hệt thùng rác dưới ga điện ngầm.

Candy Crush - ứng dụng hot nhất trên iPhone năm 2013

Candy Crush - ứng dụng hot nhất trên iPhone năm 2013

Apple đã công bố những chương trình miễn phí được tải nhiều nhất trên hệ điều hành iOS và nhiều trong số đó là các ứng dụng rất quen thuộc với người sử dụng tại Việt Nam.

Bản đồ các quốc gia bị ảnh hưởng bởi botnet Necurs.

Microsoft đánh sập mạng botnet điều hành bởi Evil Corp có trụ sở ở Nga

Microsoft và các đối tác tại 35 quốc gia đánh sập mạng botnet spam và phát tán mã độc Necurs lây nhiễm khoảng chín triệu máy tính toàn cầu.

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

 

Diet con trung