Bàn luận về bài toán “8 hậu”

[kickme!]

Theo tôi thì các dạng toan này hầu như sách kỹ thuật lập trình nào cũng có rồi,họ nói nhiều nữa là khác,bạn ra nhà sách coi là hay nhất

[dark_life2]

Mọi người ra mua sách Toán rời rạc thì co' hết :
8 quân hậu ,mã đi tuần ,Hamilton ,Euler,Cây bao trùm ,.....Etc

[monkeyvu]

ủa mình nhét 9 con hậu vô bàn cờ 8*8 được hông dzậy?

[jonhnywalker]

neu con ma quay ve dung o ma no xuat phat thi goi la chu trinh Hamilton,neu con ma di het ma khong quay tro ve o xuat phat thi goi la lo trinh Hamilton.
bai toan nay den nay van chua co cach giai tong quat bang toan hoc

[dongsong]

lỡ xem gùi cho tui hỏi luôn :
Hoán vị ko dùng hàm đệ quy , ai bit chỉ dùm . Và bài này mở rộng : (1 1 2 3 3 3) chẳng hạn , thế nó hoán vị bằng cách nèo ta ... tui bí quá nhờ anh em giúp vài ngón tay !!! hè hè

[msn]

Hamilton thì chẳng phải là duyệt à. Chỉ có thêm nhánh cận vào thì chạy được với 100 đỉnh(tương đương bàn cờ 10*10). Nếu duyệt có nhánh cận cho bài mã đi tuần thì có thể chạy được với bàn cờ 100*100

[Huynh Phong]

Cái chủ đề này đã có đăng trong tạp chí PcWorld '96. Trong đó, người ta dùng thuật toán quay lui. Tui mạn phép copdê lên cho anh em cùng xem, post thành từng đoạn nhé:

{Doan 1-----------------------------------------------------------------}

PROGRAM Xepconhau;
LABEL xettiep;
CONST DOLON = 8;
VAR songhiem : Integer;
banco : ARRAY [1..DOLON,1..DOLON] OF Boolean;
daxet : ARRAY [1..DOLON] OF Integer;
i,j,h,c : Integer;
hang, dangxet : Integer;

{Het doan 1 -------------------------------------------------------------}

[Huynh Phong]

{Doan 2. Co 2 thu tuc --------------------------------------------------- }

PROCEDURE HienKetqua; {Hien mot ket qua }
VAR h,c : Integer;
BEGIN
songhiem := songhiem + 1; writeln('Nghiem thu : ',songhiem);
for h:=1 to DOLON do
BEGIN
writeln('===========');
for c:=1 to DOLON do if banco[h,c] then write('| x ') else write('| ');
writeln('|');
end;
writeln('========='); writeln;
END;

FUNCTION Deduoc(h,c: Integer) : Boolean; {Kiem tra xem co de duoc con hau o vi tri h,c ? }
BEGIN
Deduoc := FALSE; {Kiem tra xem hang h da co con hau nao chua ?}
for i:= 1 to c-1 do
if banco[h,i] then exit;
{ Kiem tra xem duong cheo tu tren trai xuong duoi phai }
{ xuyen qua vi tri h,c da co con hau nao chua ?}
i:= h-1; j:= c-1;
while (i>0) AND (j>0) do begin if banco[i,j] then exit; i:=i-1; j:=j-1; end;
{ Kiem tra xem duong cheo tu tren phai xuong duoi trai }
{ xuyen qua vi tri h,c da co con hau nao chua ?}
i:= h+1; j:= c-1;
while (i<=DOLON) AND (j>0) do begin if banco[i,j] then exit; i:=i+1; j:=j-1; end;
Deduoc := TRUE
END;

{Het doan 2 -------------------------------------------------------------}

[Huynh Phong]

{Doan 3 Chuong trinh chinh ----------------------------------------------}


BEGIN
{Xoa ban co}
for h:=1 to DOLON do
for c:=1 to DOLON do banco[h,c]:= FALSE;
songhiem := 0;
dangxet := 0;
{Lap tim nghiem theo ky thuat backtracking}
xettiep:
dangxet := dangxet+1;
hang:=1;
repeat
while hang <= DOLON do
begin
if Deduoc(hang,dangxet) then
begin
banco[hang,dangxet] := TRUE;
if dangxet = DOLON then begin {tim duoc nghiem}
HienKetqua;
banco[hang,dangxet] := FALSE;
end else begin
daxet[dangxet] := hang; {giu lai hang da xet}
goto xettiep;
end
end;
hang := hang+1;
end;
dangxet := dangxet - 1; {Lui lai con hau truoc}
if dangxet = 0 then exit; { da thu het cac kha nang }
hang := daxet[dangxet]; {Lay lai hang da xet}
banco[hang,dangxet] := FALSE;
hang := hang + 1; {Tiep tuc xet tiep}
until FALSE;
END.


[END OF FILE]-----------------------------------------------------------

[Huynh Phong]

Thoạt tiên, cứ tưởng rằng để tìm được 1 vị trí mà 8 hậu này không hậu nào "chiếu bí" hậu nào là khó khăn nhắm. Thế nhưng, chương trình trên đã tìm ra ..92 thế đứng lận đấy!!! Tuyệt không !