Bài Toán Xếp 8 Quân Hậu
Đây là bài toán hay: cho bàn cờ 8*8 với 8 quân hậu, hãy xếp các quân hậu lên bàn cờ sao cho chúng không ăn được lẫn nhau.
Bài này có mấy thuật toán sau có thể làm:
1.Duyệt đệ quy
2.Duyệt theo thuật toán quay lui.
3.Duyệt theo thuật toán nhánh cận
...
Sau đây là code theo thuật toán quay lui:
Đây là bài toán hay: cho bàn cờ 8*8 với 8 quân hậu, hãy xếp các quân hậu lên bàn cờ sao cho chúng không ăn được lẫn nhau.
Bài này có mấy thuật toán sau có thể làm:
1.Duyệt đệ quy
2.Duyệt theo thuật toán quay lui.
3.Duyệt theo thuật toán nhánh cận
...
Sau đây là code theo thuật toán quay lui:
- Code:
//#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
#define KICHTHUOC 8 // Kich thuoc cua ban co
#define SODUONGCHEO (2*KICHTHUOC-1) // So duong cheo cua ban co
#define SOGIA (KICHTHUOC-1) // so gia
#define TRUE 1
#define FALSE 0
// prototypes
void hoanghau(int);
void inloigiai(int loigiai[]);
int cottrong[KICHTHUOC]; // mang cac cot co the dat hoang hau
int cheoxuoitrong[SODUONGCHEO]; // mang cac duong cheo xuoi co the dat hhau
int cheonguoctrong[SODUONGCHEO]; // mang cac duong cheo nguoc co the dat hhau
int loigiai[KICHTHUOC]; /* mang loigiai cho biet cot dat cac hoang
hau tren ban co. Vi du cac phan tu cua mang
la: 7 3 0 2 5 1 6 4
cho biet hoanghau0 dat o cot 7, hoanghau1
dat o cot 3, ..., hoanghau7 o cot 4 */
int SoLoiGiai = 0;
void T_HAU(void)
{
int i;
/* Khoi dong tat ca cac cot duong cheo xuoi, duong cheo nguoc deu co the
dat hoang hau */
for(i = 0; i < KICHTHUOC; i++)
cottrong[i] = TRUE;
for(i = 0; i < SODUONGCHEO; i++)
{
cheoxuoitrong[i] = TRUE;
cheonguoctrong[i] = TRUE;
}
// Goi ham de qui de bat dau dat HoangHau0 (hoang hau o hang 0)
hoanghau(0);
}
// Ham hoanghau giup dat hoang hau i (i tu 0 den KICHTHUOC-1) tren hang i
void hoanghau(int i)
{
int j;
for(j = 0; j < KICHTHUOC; j++)
if(cottrong[j] && cheoxuoitrong[i-j+SOGIA] && cheonguoctrong[i+j])
{
// Dat hoang hau vao o (i, j) tren ban co
loigiai[i] = j;
cottrong[j] = FALSE;
cheoxuoitrong[i-j+SOGIA] = FALSE;
cheonguoctrong[i+j] = FALSE;
if(i == KICHTHUOC-1) // Dkien dung, dat duoc con hoang hau cuoi
inloigiai(loigiai);
else // Buoc de qui, goi dat hoang hau i+1
hoanghau(i + 1);
// lan nguoc
cottrong[j] = TRUE;
cheoxuoitrong[i-j+SOGIA] = TRUE;
cheonguoctrong[i+j] = TRUE;
}
}
void inloigiai(int *loigiai)
{
int i, j;
char c;
randomize();
textmode(C80);
textbackground(BLACK);
clrscr();
textcolor(1 + random(15));
cprintf("\n CHUONG TRINH 8 HOANG HAU\n ");
cprintf("\n Loi giai %d", ++SoLoiGiai);
printf("\n\n 0 1 2 3 4 5 6 7");
printf("\n ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿");
printf("\n 0³ ³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 1³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³ ³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 2³ ³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 3³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³ ³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 4³ ³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 5³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³ ³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 6³ ³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³");
printf("\n ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
printf("\n 7³²²²²³ ³²²²²³ ³²²²²³ ³²²²²³ ³");
printf("\n ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
for(i = 0; i < KICHTHUOC; i++)
{
gotoxy(24+5*loigiai[i], 8+2*i);
textcolor(1 + random(15));
cprintf("Q");
}
gotoxy(13, 25);
printf("Nhan phim <ESC> de thoat, nhan phim bat ky de tiep tuc ...");
c = getche();
if(c == 27)
//return;
exit(1);
}
:bounce: 
