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 (22 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Anchor Text

Anchor Text

Anchor text is the visible characters and words that hyperlink display when linking to another document or location on the web

34 câu hỏi về iPad mới (Phần 1)

34 câu hỏi về iPad mới (Phần 1)

Giải đáp thắc mắc về màn hình Retina, độ phân giải, camera và chất lượng Facetime, RAM,... trong iPad mới đời 2012.

25% trong số 1000 website hàng đầu thế giới sử dụng nginx

25% trong số 1000 website hàng đầu thế giới sử dụng nginx

Nginx là một máy chủ Web mã nguồn mở có hiệu năng rất cao.