VuaTenMien.Com

Bài toán 8 quân hậu:

Bài toán 8 quân hậu là một bài toán rất nổi tiếng về phép thử - sai  và thuật toán quay lui.

 Đặc trưng của các bài toán này là không thể dùng các biện pháp phân tích để giải mà cần dùng các phương pháp tính toán thủ công, với sự kiên trì và độ chính xác cao.

  Tóm tắt bài toán 8 con hậu:

Tìm cách đặt 8 con hậu trên một bàn cờ sao cho không có 8 con nào ăn được nhau.

Hàm đặt hậu dùng để tìm vị trí đặt quân hậu tiếp theo:

void DatHau( int i)

{

     Khoi tao danh sach cac vi tri co the dat quan hau tiep theo;

     do{

          Lua chon vi tri dat quan hau tiep theo;

          if( vi tri dat la an toan)

          {

              Dat hau;

              if ( i<8)

              {

                   DatHau ( i+1);

                   if( Khong thanh cong)

                   Bo hau da dat ra khoi vi tri;

              }

          }

     }while ( Khong thanh cong && Van con lua chon);

     

     

Theo luật cờ:

Quân hậu sẽ ăn tất cả các quân cùng nằm trên 1 hàng, cột hay cùng 1 đường chéo

ð  Mỗi cột của bàn cờ chỉ chứa một quân hậu, quân hậu thứ i sẽ nằm ở cột thứ i

ð  Ta dùng biến i để biểu thị số cột .

ð  Quá trính lựa chọn vị trí đặt quân hậu là 1 trong 8 vị trí  trong cột cho biến chỉ số hàng j.

Ta dùng 3 mảng kiểu boolean  để biểu thị cho các hàng và các đường chéo trái và các đường chéo phải.

( Có tất cả 15 đường chéo trái và 15 đường chéo phải.)

int a[8];

int b[15], c[15];

trong đó:

nếu phần tử của mảng nhận giá trị không => chưa có quân hậu nào.

0,0	0,1	0,2	0,3	0,4	0,5	0,6	0,7
1,0	1,1	1,2	1,3	1,4	1,5	1,6	1,7
2,0	2,1	2,2	2,3	2,4	2,5	2,6	2,7
3,0	3,1	3,2	3,3	3,4	3,5	3,6	3,7
4,0	4,1	4,2	4,3	4,4	4,5	4,6	4,7
5,0	5,1	5,2	5,3	5,4	5,5	5,6	5,7
6,0	6,1	6,2	6,3	6,4	6,5	6,6	6,7
7,0	7,1	7,2	7,3	7,4	7,5	7,6	7,7

Các ô  (i , j)  nằm trên cùng  đường chéo trái  có cùng giá trị ( i + j), nằm cùng trên đường chéo phải có cùng giá trị ( i – j).

Nếu đánh số các đường chéo trái và phải từ 0 -> 14

Ô (i, j)  sẽ  nằm  trên  đường chéo trái thứ ( i + j) và đường chéo phải thứ ( i – j + 7)

Do vậy để kiểm tra xem ô (i , j ) có an toàn không, ta cần kiểm tra hàng j, đường chéo trái ( i + j) và đường chéo phải ( i – j +7 ) xem đã có quân hậu nào chiếm chỗ chưa.

Tức là kiểm tra a[i], b[i+ j] và c[i – j + 7].

Ngoài ra ta cần 1 mảng x để lưu chỉ số hàng của quân hậu trong mảng i :

int x[8];

vậy với thao tác đặt hậu vào vị trí hàng j cột i ta cần thực hiện các thao tác sau:

x[i] = j; a[j] = 1; b[i+j] = 1; c[i – j + 7] = 1;

với thao tác bỏ hậu ra khỏi hàng j cột I ta cần thực hiện các thao tác:

a[j] = 0;  b[i+j] = 0; c[i-j + 7] = 0;

Điều kiện để xét xem vị trí hàng i cột j có an toàn không ta kiểm tra:

(a[j] == 0) && (b[i+j] ==0) && (c[i – j +7] ==0)

  

//dat_hau.cpp



#include"iostream"

using namespace std;

int a[8];

int b[15],c[15];

int x[8];



void Init()

{

     for( int i = 0;i<8;i++)

      {

           a[i] = 0;

           x[i] = -1;

      }

      

     for( int i =0;i<15;i++)

     {

          b[i] = 0;

          c[i] = 0;

     }

}



void DatHau( int i, int &q)

{

     int j = 0;

     

     

     do{

            

     q = 0;

     if ((a[j] == 0) && (b[i+j] == 0) && (c[i-j+7] == 0))

     {

               a[j] = 1; b[i+j] = 1; c[i-j+7] = 1;

               x[i] = j;

               q = 1;

               

               if( i <7)

               {

                   DatHau( i +1,q);

                   if( q == 0){

                   

                   a[j] = 0;b[i+j] = 0; c[i-j+7] = 0;}

                   

               }

     }

     

     }while ( (++j < 8) && (q==0) );

} 

               

int main()

{

    Init();

    int q;

    DatHau(0,q);

    cout<< endl;

    for(int i =0;i<8;i++)

    cout<< " " << x[i];

    cout<<"\n......................................";

    int k[8][8];

    for( int i =0; i<8;i++)

    for(int j =0;j<8;j++)

    {

            if ( x[j] == i)k[i][j] = 1;

            else k[i][j] = 0;

    }

    for( int i =0;i<8;i++)

    {

         cout<<endl;

    for(int j = 0;j<8;j++)

    {

            cout<< " "<<k[i][j];

            

    }

    }

    

    cout<< endl;

    system("pause");

    return 0;

}