[C\C++] Bài toán Xếp Hậu (thuật toán quay lui) [Cấu trúc dữ liệu và giải thuật]

Cài đặt Bài toán Xếp Hậu

Bài toán tám quân hậu là bài toán đặt tám quân hậu trên bàn cờ vua kích thước 8×8 sao cho không có quân hậu nào có thể "ăn" được quân hậu khác, hay nói khác đi không quân hậu nào có để di chuyển theo quy tắc cờ vua. Mầu của các quân hậu không có ý nghĩa trong bài toán này. Như vậy, lời giải của bài toán là một cách xếp tám quân hậu trên bàn cờ sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường chéo. Bài toán tám quân hậu có thể tổng quát hóa thành bài toán đặt n quân hậu trên bàn cờ n×n (n ≥ 4).

[Code Turbo C\C++]

/* ------------------------ */
#include <stdio.h>
#include<conio.h>

int dong[8], cot[8], cheoxuoi[15], cheonguoc[15];
//

void print (){
   int i;
   printf("\n");
   for (i=0; i<8; i++)
     printf("%3d", dong[i]);
}

//
void thu(int i){
   int j;
   for (j=0; j<8; j++) {
    if(cot[j]==1&&cheoxuoi[i+j]==1&&cheonguoc[i-j+7]==1)
    {
      dong[i] = j;
      cot[j] = 0;
      cheoxuoi[i+j] = 0;
      cheonguoc[i-j+7] = 0;
      if (i<7)
        thu(i+1);
      else
         print();
         cot[j] = 1;
         cheoxuoi[i+j] = 1;
         cheonguoc[i-j+7] = 1;
      }
    }
}

// Hàm tìm
void tim(){
int i, q;
for (i=0; i<8; i++)
{
cot[i] = 1;
dong[i] = -1;
}
for (i=0; i<15; i++)
{
cheoxuoi[i] = 1;
cheonguoc[i] = 1;
}
thu(0);
}

// Hàm chính
void main(){
tim();
getch();
}

/***************/

>> Tải Code Chương trình tại đây

Lưu ý: Sau 5s, click Bỏ qua quảng cáo - Skin Ad)

* Mô phỏng Kết quả bài toán

//----------------------------------------------------//

>> DOWNLOAD TURBO C++ 3.0
>> DOWNLOAD TURBO C++ 4.5
Lưu ý: chờ 5s => click SKIN AD (bỏ qua quảng cáo)
* Download công cụ lập trình C\C++ tại đây [http://taiphanmemlaptrinh.blogspot.com]
* Download tài liệu học C\C++ và CTDL&GT tại đây [http://ebooks-ict.blogspot.com]