View Full Version : Bàn luận về bài toán “8 hậu”
The_Wall
14-12-2002, 20:24
Các bạn chắc là đã nghe qua bài toán sắp xếp 8 con hậu trên bàn cờ vua 8x8 sao cho không con hậu nào khống chế con nào . Hãy liệt kê tất cả các cách sắp xếp như vậy . Từ đó mở rộng ra với n x n cột . Hình như bài này có nhiều cách giải khác nhau phải không các bạn ? Giúp tui với ha ?
thôi, viết mail cho tui đi, tui có sách nè ông ơi
The_Wall
15-12-2002, 16:52
Tôi sẽ hỏi code qua e-mail ông ha, nhưng tui muốn bàn thêm về thuật toán bài này nữa
real_time
17-12-2002, 08:57
Bài này là một bài điển hình cho thuật toán quay lui và thử sai.
Nhưng mình có một cách khác để làm đó là liệt kệ hoán vị của các quân hậu mà những vị trí của nó có thể đứng được (dùng theo cách này thì nhanh hơn quay lui và thử sai!)
Ai còn cách nào khác nữa không đưa tiếp lên đi.
khôngtên
17-12-2002, 12:44
Chỉ có quay lui thử sai thôi !
The_Wall
17-12-2002, 14:08
Real_Time ơi , chỉ tui biết cách liệt kê hoán vị những quân hậu đi có được không, tui không biết nhiều thuật toán lắm nên đành "chịu" thôi .
cauberungxanh
19-12-2002, 20:08
real_time chỉ thuật toán hoán vị đi....
The_Wall
21-12-2002, 14:57
Real_Time hổm nay bận lắm hay sao mà chưa thấy vào trả lời nữa . Real_Time ơi (hay một ai đó) chỉ giúp mình đi chứ !
The_Wall
06-01-2003, 15:17
Cho mình gửi lời cám ơn bạn Lovely nhiều lắm . Chương trình của bạn rất trực quan và dễ hiểu .
Thanks
real_time
13-01-2003, 12:46
tư tưởng của thuật toán dùng hoán vị là bạn sẽ đặt 8 quân hậu đó lên bàn cờ 8x8 và tìm tất cả hoán vị của tất cả những vị trí của những quân hậu đó lên bàn cờ thế thoả mãn điều kiện ko ăn nhau là được t hôi. và như vậy liệt kê hết tất cả các trường hợp của bài toán là 8! với bàn cờ nxn thì cũng chỉ có n! nhanh hơn thử sai và quay lui!
Ứng dụng hoán vị để giải bài toán tám hậu quả nhiên là một phương pháp hay nhưng không thể nhanh hơn quay lui đâu. Độ phức tạp của thuật toán hoán vị là n! còn của quay lui là n*n thôi.
Tiện cho mình hỏi "mã đi tuần " là gì vậy ?
Có ai có chương trình (đò họa) minh hoạ cho bàn cờ n*n ô không ?
C'est la vie
21-02-2003, 17:08
Một quân mã xuất phát từ một ô đi qua tất cả các ô còn lại mỗi ô 1 lần và trở lại vị trí ban đầu.
The_Wall
02-03-2003, 11:13
cái bài này ta dùng vét cạn là được hà. Có nhiều sách nói về bài này lắm
Bài mã đi tuần vét cạn cũng được nhưng không hiệu quả lắm, nên đưa về đồ thị rồi tìm chu trình Hamilton là tốt nhất.
Bạn có thể nói cụ thể hơn được không ? Hamilton là gì vậy ?
Không thể nói rỏ vấn đề trong khuôn khổ bài viết này được. Bạn đã học lý thuyết đồ thị chưa.
- Nếu chưa thì bạn sẽ khó mà hiểu được, hãy kiếm sách về lý thuyết đồ thị hoặc đọc trong cuốn Toán rời rạc cũng được.
- Nếu đã học rồi thì hãy xem lại. Chu trình Hamilton chính là chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh chỉ đi qua duy nhất một lần.
Ồ ! Nhưng tôi chưa học toán rời rạc , bạn có bản demo nào gửi cho tôi nhé
del_gate
03-04-2003, 17:39
Bạn nên tìm sách thì hơn vì đây toàn là thuật toán cơ bản thôi.
Sách nói về vấn đề này nhiều lắm.
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
17-04-2003, 11:03
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
09-05-2003, 21:59
ủa mình nhét 9 con hậu vô bàn cờ 8*8 được hông dzậy?
jonhnywalker
19-07-2003, 22:11
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
31-12-2003, 23:14
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è
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
03-01-2004, 14:53
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
03-01-2004, 14:57
{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
03-01-2004, 15:00
{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
03-01-2004, 15:05
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 !
cho coi demo viet trong 1h ne` (nổ ti ay ma)
http://nguoiyeusach.com/8_QUEEN.exe
nhấn vào, và đừng cố gắng làm nó dừng khi nó đang chạy, hè hè
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
Kha kha...
To co cach giai quyet bai ma di tuan voi do lon ban co nxn tuy y...
Chay nhanh nhu chao chop. Thuat toan Heuristic ay ma...
real_time
08-01-2004, 23:27
tui chưa nghe thuật toán bạn giới thiệu tui học với được ko?
Mã đi tuần n*n đúng là có thuật toán heuristic, nhưng chỉ có điều không phải lúc nào cũng ra được thôi.
x3winofall
09-01-2004, 14:47
thuật toán heuristic là thuật toán đoán đại dành cho máy
cứ thấy cái nào có lợi gần nhất thì thực hiện nên cho ra kết qua ko ổn định và thwừong bị sai
thuật toán heuristic là thuật toán đoán đại dành cho máy
cứ thấy cái nào có lợi gần nhất thì thực hiện nên cho ra kết qua ko ổn định và thwừong bị sai
Co le ban nham doi chut, thuat toan "cứ thấy cái nào có lợi gần nhất thì thực hiện" la thuat toan tham lam chu khong phai heuristic.
Dieu cac ban noi ve ket qua cua cac thuat toan heuristic la dung trong nhieu truong hop. Trong bai ma di tuan, tuy la thuat toan heuristic nhung to da khao sat va chung minh tong quat duoc cho moi truong hop ma cach duyet thong thuong co nghiem thi thuat toan heuristic cung co nghiem roi. Vi du ma di tuan co the coi nhu la vi du dien hinh cua thuat toan heuristic day.
Gan day, da phan cac bai toan duyet to hop nhu the, nguoi ta deu co gang dua ve cac thuat toan heuristic.
Em cung dang rat can thuat toan cho bai toan 8 con hau tren ban co n*n o.Mong cac anh chi giup em voi.Em that su rat can
Mong cac anh quan tam !
Ứng dụng hoán vị để giải bài toán tám hậu quả nhiên là một phương pháp hay nhưng không thể nhanh hơn quay lui đâu. Độ phức tạp của thuật toán hoán vị là n! còn của quay lui là n*n thôi.
Tui đoán ý của bạn real_time là: với cách hoán vị => 8! (8 giai thừa) . Còn nếu xài thử sai & quay lui mà mình làm theo kiểu:
Thử đặt quân hậu thứ 1 vô 1 trong 8 cột
Thử đặt quân hậu thứ 2 vô 1 trong 8 cột
...................
Thử đặt quân hậu thứ 8 vô 1 trong 8 cột
==> tới 8^8 > 8! (8*8*8*8*8*8*8*8 > 1*2*3*4*5*6*7*8)
Tui xin có thắc mắc:
1) cho real_time: nếu mình chỉ hoán vị toạ độ cột (hay tọa độ dòng) 0 thôi thì đúng là n! thiệt . Nhưng tui nghĩ mình phải hoán vị vừa tọa độ cột lẫn tọa độ dòng; và phải làm lồng nhau: với mỗi cách hoán vi tọa độ cột phảI xét TẤT CẢ các cách hóan vị tọa độ dòng => có còn là n! (hay sẽ là (n!)^2)? bạn real_time có thể cho biết rõ hơn bạn hoán vị như thế nào 0 ?
2) cho btkiet: tui nghĩ thử sai & quay lui phải xét (n^2)*(n^2-1)*(n^2-2)*(n^2-3)*(n^2-4)*(n^2-5)*(n^2-6)*(n^2-7) ~ (n^2)^8 = n^16 ? (nếu mình chỉ đặt quân hậu thứ 1 thôi thì xét n^2 cách chọn; đặt tiếp quân hậu thứ 2 thì xét n^2-1 cách chọn)
Không biết tui có sai chỗ nào 0 => mấy bồ chỉ giúp (nếu so sánh hóan vị ((n!)^2) & quay lui (n^16) thì tui thấy n^16 = (n^8)^2 > (n!)^2 => hoán vị nhanh hơn thiệt)
Tui nghĩ nếu lợi dụng thêm tính đói xứng của bàn cờ thì có thể chạy nhanh gấp 8 lần (thay vì xét đặt quân hậu thứ 1 KHẮP bàn cờ thì chỉ xét đặt quân hậu thứ 1 ở 1/8 bàn cờ; các quân hậu còn lại vẫn phải xét đặt KHẮP bàn cờ)
3) cho lovely: tiếc quá, cái zip file củA bạn là 0 byte => tui muốn coi thử nhưng mà chịu !
Tui xin có tí ý kiến cùn về heuristic: heuristic là tốt nếu đề bài yêu cầu tìm chỉ 1 cách giải => sẽ giúp mình tìm nhanh nhứt . Nhưng nếu đề bài yêu cầu tìm TẤT CẢ cách giải thì mình vẫn phải xét TẤT CẢ các trường hợp => cũng tốn thời gian như 0 xài heuristic (nhưng người xài sẽ thấy cách giải đầu tiên mau hơn (hoặc các cách giải được hiển thị gần nhau hơn) => đỡ chán hơn -- bù lại vì phải lập trọng số (như trong mã đi tuần chẳng hạn) => thời gian tổng cộng sẽ lâu hơn) ?
Không biết nghĩ như trên có đúng 0 ?
Gủi mayngan
Em cung dang rat can thuat toan cho bai toan 8 con hau tren ban co n*n
có vẻ như bài đăng của Huynh_Phong xài được cho N quân hậu với bàn cờ NxN: bạn sửa DOLON = N như bạn muốn
Nếu bạn muốn đặt M quân hậu trên bàn cờ NxN thì sửa thêm:
if dangxet = DOLON then begin {tim duoc nghiem}
=> if dangxet = M then begin {tim duoc nghiem}
Gửi msn
Mã đi tuần n*n đúng là có thuật toán heuristic, nhưng chỉ có điều không phải lúc nào cũng ra được thôi.
Tui nghĩ với bài toán kiểu có N lựa chọn => heuristic sẽ lượng giá các cách chọn (dĩ nhiên tốt hay xấu là tùy cách mình làm heuristic) . Nếu mình xét TẤT CẢ các các cách chọn theo thứ tự của heuristic gợi ý thì vẫn tìm ra mọi cách giải; điểm lợi hơn là người dùng sẽ thấy các giải hiện ra sớm hơn (nếu heuristic là tốt) . Còn nếu mình chỉ xét cách chọn đầu tiên thì có thể sẽ 0 có hết được mọi cách giải
Bai toan ma di tuan that dung co cach Heuristic, nhung chi dung doi voi ban co co N > 5 thoi (minh cung ko chac lam, tai vi chua cai bao gio, chi doc thoi, hinh nhu = 5 cung dung)
Vay ta co hai truong hop
Neu n <= 5 ta dung quay lui de liet ke
voi n > 5 ta di heuristic nhu sau
Xet tai mot o bat ky, ta tim 1 o trong cac o ma co the toi duoc la gan bien nhat, cho ma di theo o do
Y tuong do xuat phat tu suy nghi sau day
Tai moi buoc, ban se di toi nhung o co it duong di nhat va de lai nhung o co nhieu duong di hon. Nhu vay ban se duyet duoc cac o tu it duong di -> nhieu duong di, dieu do giup chung ta ko bi het duong di
Thuat toan tren da duoc chung minh la dung dan (Nhung chung minh the nao thi minh ko biet
Tui nghĩ heurisstic cho mã đi tuần áp dụng được với mọi N >= 3
Hiển nhiên N=1 hay 2 thì lời giải dễ thấy rồi
Trường hợp tìm TẤT CẢ lời giải của mã đi tuần thì làm heurisstic kiểu nào cũng ra được HẾT mọi lời giải . Giả sử bài toán có 10 lời giải & cần mất 1 giờ để xét hết các khả năng; nếu mình làm heuristic tốt thì có thể vài giây đầu đã có được lời giải thứ nhất; vài giây sau nữa có lời giải thứ 2; .... sau 10 phút đã ra 10 lời giải => người dùng vẫn sẽ phải chờ thêm 50 phút còn lại để chương trình kết thúc . Nếu làm heurisstic dở hơn thì có thể chạy 40 phút đầu mà 0 ra được lời giải nào, sau đó các lời giải lần lượt được in ra trong 20 phút còn lại . Như vậy chạy heuristic kiểu nào cũng sẽ thấy 10 lời giải & chương trình sẽ phải chạy mất 1 giờ (giả sử 2 cách heuristic 0 chênh lệch về thời gian chạy mà chỉ khác nhau về cách đặt trọng số cho các khả năng của bước kế). Cách giải thuần túy (0 xài heuristic) có thể coi như là 1 cách heuristic thật đơn giản thôi
HunterLeader
22-03-2004, 23:00
Dùng thuật toán alpha-beta + trí tuệ nhân tạo
Em muon hoi neu ban co n*n voi n>=100 thi co the ap dung thuat toan nao de dat n hau?Neu dung de qui thi Overflow or Run time erro mat.Ai biet chi em voi
0 rõ mây ngàn chỉ cần tìm 1 lời giải hay phải tìm TẤT CẢ lời giải
Nếu phải tìm tất cả lời giải thì n>100 chắc máy 0 chịu nổi (100! lớn lắm)
Yêu cầu bài toán đặt ra là tìm tất cả lời giải để đặt n hậu trên bàn cờ n*n.Co thuật giải nào giả quyết được ko.Nghe nói trên thế giới người ta viết được cho n=1000.000
mayngan có thể coi:
http://www.durangobill.com/N_Queens.html
(đoạn cuối "Computational Considerations" có cho biết N lớn thì lời giải tìm khó như thế
nào)
http://www.schoolnet.ca/vp/AMOF/e_permI.htm
(có nói qua về "hoán vị" của real_time; đúng là N! thiệt)
http://www.cs.mcgill.ca/~emal-a/queen.htm
(theo như họ thỉ đây là NP-hard => thấy rầu rồi :()
http://portal.acm.org/citation.cfm?id=324620&coll=portal&dl=ACM&CFID=19399374&CFTOKEN=44922255
(có 1 bài cho code của các giải thuật: backtracking, permutation,...)
Tóm lại đây là 1 bài khó (có ai đó mà làm được cho N=1000 thì ngầu ghê lắm !!!)
Nếu mayngan muốn vẫn muốn biết thêm thì thử
http://www.google.com/search?q=352++724++2680++14200&hl=en&lr=&ie=UTF-8&oe=UTF-8&start=20&sa=N
cảm ơn bete nhiều nha.Nhưng gì bạn cung cấp thật hữu ích.Nhưng thật sự mình vẫn bế tắc vì n lớn quá.Hi vọng sẽ có cao thủ.
[QUOTE=mayngan]Neu dung de qui thi Overflow or Run time erro mat[\QUOTE]
Không rõ mayngan xài ngôn ngữ lập trình nào (Pascal, C, ...) ? Và cái trình biên dịch mà mayngan đang xài có cho phép tăng độ sâu của stack ? Tui nghĩ nếu TBD chỉ cho dưới 100 lần gọi đệ qui thì hơi ít (ngoại trừ bạn xài nhiều tham số & biến cục bộ quá vì 2 lọai này được cấp phát trên stack) .
Bạn có thể thử giảm tham số & biến cục bộ hoặc khử đệ qui .
Nếu giải thuật của bạn là thử từng cột, mỗi cột thử từng dòng => gọi đệ qui ứng với mỗi cột, bên trong hàm đệ qui thì lặp để thử từng dòng . Ở mỗi bước mình chỉ cần nhớ là đã đặt được quân hậu cho tới cột nào & quân hậu nằm trên dòng nào ứng với mỗi cột .
Nếu áp dụng ý của thuật toán hoán vị thì có thể biểu diễn trạng thái của bàn cờ ở 1 bước nào đó bằng 1 mảng A có N phần tử: A[i] = j => có 1 quân hậu trên dòng j của cột i .
Nếu bạn chọn mỗi phần tử là 1 byte thì biểu diễn được tới 255 => áp dụng được cho bàn cờ 255x255. Nếu bạn chọn mỗi phần tử là 2 bytes thì biểu diễn được tới 65535 => áp dụng được cho bàn cờ 65535x65535 .
Nếu bạn khai mảng này là biến toàn cục thì sẽ tốn N bytes (maximum: giải tới N=255 => 256 bytes) hoặc 2N bytes (maximum: giải tới N=65535 => 65536*2 bytes = 128KB -- bạn coi chừng bứt bộ nhớ :)) cho mảng này .
Nếu bạn giải cho N=255: xài biến A toàn cục & đệ qui (tham số là cột đang xét -> 1 byte) thì bạn tốn 256 bytes cho mảng A & 256 bytes cho tham số trên stack (cộng thêm các biến toàn cục + biến cục bộ khác) => tui nghĩ 0 đến nỗi nào bạn bị stack overflow error .
Nếu bạn giải cho N=255: xài biến A toàn cục & khử đệ qui thì bạn tốn 256 bytes cho mảng A (cộng thêm các biến toàn cục khác) => cũng 0 đến nỗi 0 đủ bộ nhớ
Chỉ có điều N lớn thì e rằng phải chạy khá lâu (mất hàng ngày, tuần, tháng, ..) để có được tất cả các đáp số thôi !
Nếu bạn coi hàm DeDuoc trong bài đăng của HuynhPhong thì thấy mình phải qúet 1 phần của bàn cờ NxN : nếu mình đang thử đặt quân hậu ở cột c hàng h thì phải xét các ô cùng dòng (cho tới cột trước đó), cùng đường chéo (cho tới cột trước đó)
Bạn có thể thử làm cách khác (0 chắc là sẽ nhanh hơn nhé). Xét thử bàn cờ 3x3:
(h=1,c=1) (h=1,c=2) (h=1,c=3)
(h=2,c=1) (h=2,c=2) (h=2,c=3)
(h=3,c=1) (h=3,c=2) (h=3,c=3)
Nếu tại mỗi phần tử mình tính tổng của chỉ số cột & chỉ số hàng (c+h)
2 3 4
3 4 5
4 5 6
==> các ô có cùng giá trị của tổng sẽ nằm trên cùng đường chéo . Có tất cả 5 giá trị khác nhau (2,3,4,5,6) => có 5 (2N-1) đuờng chéo (trên -> xuống, phải -> trái)
Nếu tại mỗi phần tử mình tính hiệu của chỉ số cột & chỉ số hàng (c-h)
0 1 2
-1 0 1
-2 -1 0
==> các ô có cùng giá trị của hiệu sẽ nằm trên cùng đường chéo . Có tất cả 5 giá trị khác nhau (-2,1,0,1,2) => có 5 (2N-1) đuờng chéo (trên -> xuống, trái -> phải)
Như vậy mình có thể xài 3 mảng
dong : array [1..N] of số nguyên
dcheo1 : array [1..2N-1] of số nguyên
dcheo2 : array [1..2N-1] of số nguyên
để kiểm xem dòng, đường chéo nào đó là chưa bị chiếm hay bị chiếm rồi (mỗi lần đặt 1 quân hậu thì đánh dấu 3 phần tử (tương ứng cho dong, dchéo, dcheo2); mỗi lần kiếm thì xét 3 phần tử (tương ứng cho dong, dchéo, dcheo2); mỗi lần quay lui thì đánh dấu 3 phần tử (tương ứng cho dong, dchéo, dcheo2))
==> đỡ công hơn khi kiếm vị trí trống, nhưng tốn công hơn khi đặt quân hậu & quay lui (hy vọng với N lớn thì sẽ thấy hiệu quả hơn)
Có gì sai sót thì mong các bạn cho ý kiến (xin cám ơn trước)
real_time
30-03-2004, 22:14
quá hay rồi bete ạ khó có thể nói gì hơn!!! xin phép mọi người vào đây hỏi một câu ngoài lề một chút!
giải bài toán 8 hậu này bằng hoán vị đồng ý là có n! phép tính thôi nhưng lấy hoán vị cách nào nhanh nhất và tốc độ cao nhất??? vì nếu giải quyết bằng hoán vị mà ko quan tâm đến tốc độ lấy hoán vị thì cũng vứt!
lấy hoán vị cách nào nhanh nhất
Tui nghĩ nếu N là nhỏ (N=8 chẳng hạn) thì bài đăng của HuynhPhong dư sức tìm ra đáp số trong khỏang thời gian ngắn . Nhưng nếu muốn thử với N lớn cỡ 20 thì chắc phải thử hoán vị quá .
Về tìm hoán vị thì tui thấy có 3 hướng (bạn nào biết thêm hướng khác thì bổ sung giúp, xin cám ơn):
1) hướng 1: xài đệ qui & chèn -> để tìm tất cả hoán vị cho N phần tử mình tìm tất cả hoán vị của N-1 phần tử (băng đệ qui) -> (N-1) giai thừa trường hợp . Với mỗi trường hợp mình chèn phần tử còn lại vô N vị trí => N giai thừa trường hợp
Ví dụ: (1, 2, 3) . Với đệ qui cho 2 phần tử đầu -> mình tìm được (1,2) & (2,1)
==> chèn phần tử 3 còn lại vô 3 vị trí của trường hợp 1 -> (1,2,3), (1,3,2), (3,1,2),
& chèn phần tử 3 còn lại vô 3 vị trí của trường hợp 2 -> (2,1,3), (2,3,1), (3,2,1)
2) Huớng 2: mình tìm hoán vị theo thứ tự tăng dần (nếu dữ liệu cần hoán vị 0 là số nguyên thì mình có thể sắp vô 1 mảng & xài chỉ số của mảng cho hoán vị)
Ví dụ: (1,2,3) -> mình tìm tất cả các trường hợp hoán vị theo thứ tự tăng dần:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
3) Hướng 3: mình tìm tất cả các hoán vị theo thứ tự "hoán chuyển" (xin tạm dịch từ "tranposition oder"): 2 trường hợp hoán vị được liệt kê kế nhau -> sẽ chỉ khác nhau bởi phép hoán chuyển 2 phần tử:
Vị dụ (1,2,3) -> (1,2,3), (1,3,2), (3,1,2), (3,2,1), (2,3,1), (2,1,3)
==> mình để ý thấy:
(1,2,3): hoán vị 2 & 3 -> (1,3,2)
(1,3,2): hoán vị 1 & 3 -> (3,1,2)
(3,1,2): hoán vị 1 & 2 -> (3,2,1)
(3,2,1): hoán vị 3 & 2 -> (2,3,1)
(2,3,1): hoán vị 3 & 1 -> (2,1,3)
(2,1,3): hoán vị 2 & 1 -> (1,2,3) (vòng trở lại trường hợp đầu tiên)
Tui nghĩ hướng 3 là nhanh nhứt (vì chỉ cần hoán vị 2 phần tử là có được trường hợp kế) .
Tuy nhiên nếu hoán chuyển 0 khéo thì sẽ thiếu trường hợp.
Ví dụ cho (a,b,c,d) mình làm như sau:
Bắt đầu từ (a,b,c,d):
(a,b,c,d): hoán vị phần tử thứ 3 & phần tử thứ 4 -> (a,b,d,c)
(a,b,d,c): hoán vị phần tử thứ 2 & phần tử thứ 3 -> (a,d,b,c)
(a,d,b,c): hoán vị phần tử thứ 1 & phần tử thứ 2 -> (d,a,b,c)
(d,a,b,c): hoán vị phần tử thứ 3 & phần tử thứ 4 -> (d,a,c,b)
(d,a,c,b): hoán vị phần tử thứ 2 & phần tử thứ 3 -> (d,c,a,b)
(d,c,a,b): hoán vị phần tử thứ 1 & phần tử thứ 2 -> (c,d,a,b)
(c,d,a,b): hoán vị phần tử thứ 3 & phần tử thứ 4 -> (c,d,b,a)
(c,d,b,a): hoán vị phần tử thứ 2 & phần tử thứ 3 -> (c,b,d,a)
(c,d,b,a): hoán vị phần tử thứ 1 & phần tử thứ 2 -> (b,c,d,a)
(b,c,d,a): hoán vị phần tử thứ 3 & phần tử thứ 4 -> (b,c,a,d)
(b,c,a,d): hoán vị phần tử thứ 2 & phần tử thứ 3 -> (b,a,c,d)
(b,a,c,d): hoán vị phần tử thứ 1 & phần tử thứ 2 -> (a,b,c,d)
==> chỉ có được 12 trường hợp thay vì 24 trường hợp (thiếu mất 12 trường hợp)
Thứ tự hoán chuyển phải như thế nào để có được tất cả các hoán vị thì tui chưa rõ (cần phải lục & tìm) :) Bạn nào biết thì nói giùm, xin cám ơn
Có vẻ hướng 3 & hướng 1 liên hệ với nhau . Ví dụ cho 4 phần tử (1,2,3,4), mi`nfh có 1 cách liệt kê các hoán vị sao cho 2 trường hợp hoán vị được liệt kê kế nhau sẽ chỉ khác nhau bởi phép hoán chuyển 2 phần tử:
(1,2,3,4) (1,2,4,3) (1,4,2,3) (4,1,2,3)
(4,1,3,2) (1,4,3,2) (1,3,4,2) (1,3,2,4)
(3,1,2,4) (3,1,4,2) (3,4,1,2) (4,3,1,2)
(4,3,2,1) (3,4,2,1) (3,2,4,1) (3,2,1,4)
(2,3,1,4) (2,3,4,1) (2,4,3,1) (4,2,3,1)
(4,2,1,3) (2,4,1,3) (2,1,4,3) (2,1,3,4)
Nếu mình coi kỹ thì sẽ thấy cách liệt kê này chính là:
Chèn 4 từ phải sang trái vô từng vị trí của (1,2,3)
Chèn 4 từ trái sang phải vô từng vị trí của (1,3,2)
Chèn 4 từ phải sang trái vô từng vị trí của (3,1,2)
Chèn 4 từ trái sang phải vô từng vị trí của (3,2,1)
Chèn 4 từ phải sang trái vô từng vị trí của (2,3,1)
Chèn 4 từ trái sang phải vô từng vị trí của (2,1,3)
Và mình lại coi kỹ chuỗi liệt kê
(1,2,3), (1,3,2), (3,1,2), (3,2,1), (2,3,1), (2,1,3)
thì thấy nó chính là
Chèn 3 từ phải sang trái vô từng vị trí của (1,2)
Chèn 3 từ trái sang phải vô từng vị trí của (2,1)
Cuối cùng chuỗi liệt kê (1,2), (2,1) chính là chèn 2 từ phải sang trái vô từng vị trí của (1)
Tóm lại có thể liệt kê 24 trường hợp hoán vị của (1,2,3,4) như sau:
bắt đầu từ (1,2,3,4)
thử dời 4 qua trái 1 bước: hoán vị 3 & 4 -> (1,2,4,3)
thử dời 4 qua trái 1 bước: hoán vị 2 & 4 -> (1,4,2,3)
thử dời 4 qua trái 1 bước: hoán vị 1 & 4 -> (4,1,2,3)
thử dời 4 qua trái 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua trái 1 bước: hoán vị 2 & 3 -> (4,1,3,2)
thử dời 4 qua phải 1 bước: hoán vị 4 & 1 -> (1,4,3,2)
thử dời 4 qua phải 1 bước: hoán vị 4 & 3 -> (1,3,4,2)
thử dời 4 qua phải 1 bước: hoán vị 4 & 2 -> (1,3,2,4)
thử dời 4 qua phải 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua trái 1 bước: hoán vị 1 & 3 -> (3,1,2,4)
thử dời 4 qua trái 1 bước: hoán vị 2 & 4 -> (3,1,4,2)
thử dời 4 qua trái 1 bước: hoán vị 1 & 4 -> (3,4,1,2)
thử dời 4 qua trái 1 bước: hoán vị 3 & 4 -> (4,3,1,2)
thử dời 4 qua trái 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua trái 1 bước: 0 được -> đảo hướng của 3 (nhưng 0 dời 3); thử dời 2 qua trái 1 bước: hoán vị 1 & 2 -> (4,3,2,1)
thử dời 4 qua phải 1 bước: hoán vị 4 & 3 -> (3,4,2,1)
thử dời 4 qua phải 1 bước: hoán vị 4 & 2 -> (3,2,4,1)
thử dời 4 qua phải 1 bước: hoán vị 4 & 1 -> (3,2,1,4)
thử dời 4 qua phải 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua phải 1 bước: hoán vị 3 & 2 -> (2,3,1,4)
thử dời 4 qua trái 1 bước: hoán vị 1 & 4 -> (2,3,4,1)
thử dời 4 qua trái 1 bước: hoán vị 3 & 4 -> (2,4,3,1)
thử dời 4 qua trái 1 bước: hoán vị 2 & 4 -> (4,2,3,1)
thử dời 4 qua trái 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua phải 1 bước: hoán vị 3 & 1 -> (4,2,1,3)
thử dời 4 qua phải 1 bước: hoán vị 4 & 2 -> (2,4,1,3)
thử dời 4 qua phải 1 bước: hoán vị 4 & 1 -> (2,1,4,3)
thử dời 4 qua phải 1 bước: hoán vị 4 & 3 -> (2,1,3,4)
thử dời 4 qua phải 1 bước: 0 được -> đảo hướng của 4 (nhưng 0 dời 4); thử dời 3 qua phải 1 bước: 0 được -> đảo hướng của 3 (nhưng 0 dời 3); thử dời 2 qua trái 1 bước: 0 được -> đảo hướng của 2 (nhưng 0 dời 2); thử dời 1 --> ngưng tại đây
Mình để ý vài điều:
1) Phần tử 4 dời chỗ 3 lần thì phải đảo hướng, phần tử 3 dời chỗ 2 lần thì phải đảo hướng, phần tử 2 dời chỗ 1 lần thì phải đảo hướng, khi nào phải dời chỗ phần tử 1 thì ngưng lại . Hướng dời ban đầu của tất cả các phần tử là từ phải sang trái
Mình có thể xài 1 mảng count[1..4] của số nguyên . Khởi tạo count[i] bằng i cho mọi i
=> count[i]: chạy được từ i -> 1 (phần tử i dời qua trái được i-1 lần) và chạy được từ 1 -> i (phần tử i dời qua phải được i-1 lần) .
count[i] = 1 hoặc count[i] = i thì phải đảo hướng (phần tử i đã dời đủ i-1 lần)
2) Mình xài thêm mảng huong[1..N] . Khởi tạo huong[i] = 0 (dời qua trái) cho mọi i . Khi đảo hướng cho phần tử i thì huong[i] đổi từ 0 sang 1 (count[i]=1 -> đang dời qua trái chuyển sang dời qua phải) hoặc huong[i] đổi từ 1 sang 0 (count[i]=i -> đang dời qua phải chuyển sang dời qua trái)
3) Khi đảo hướng phần tử i thì phải thử dời phần tử i-1, nếu 0 dời được (vì count[i-1] = 1 hoặc count[i-1] = (i-1)) thì thử dời tiếp phần i-2, .. cho đến khi nào tìm được 1 phần tử để dời hoặc 0 còn phần tử để dời (dời đến phần tử 1)
4) Xét trường hợp (4,3,1,2) -> (4,3,2,1): 0 thể dời 4 qua trái; đảo hướng 4; 0 thể dời 3 qua trái; đảo hướng 3; dời 2 qua trái . Xét phần tử 2: count[2] = 2 -> trong biến chuyển từ chuỗi con (1,2) sang (2,1): 2 đổi từ vị trí thứ 2 sang vị trí thứ 1 . Nhưng nếu xét trong biến chuyển từ chuõi (4,3,1,2) -> (4,3,2,1): 2 đổi từ vị trí thứ 4 sang vị trí thứ 3 (là vì đã có phần tử 4 & 3 chiếm ở vị trí 1 & vị trí 2 => phải tăng các vị trí lên 2) -> hoán vị phần tử ở vị trí (count[2]+2) với phần tử ở (count[2]+1)
Như vậy, muốn dời chỗ số 2 chẳng hạn, mình xét count[2] & độ dời d . Độ dời d là huong[3] + huong[4]. Nếu muốn dời phần tử 2 sang trái thì mình hoán vị phần tử ở vị trí (count[2]+d) với phần tử ở vị trí (count[2]+d-1). Nếu muốn dời phần tử 2 sang phải thì mình hoán vị phần tử ở vị trí (count[2]+d) với phần tử ở vị trí (count[2]+d+1) . Tổng quát độ dời d cho phần tử i là tổng của huong[j] (j>i)
Mình tạm đi đến 1 thuật toán (chưa chạy thử -> có thể sai):
cho mảng A[1..N]: dữ liệu cần tìm hoán vị
khai báo count[1..N] số nguyên, huong[1..N] số nguyên
bước 1: khởi tạo count[i] = i với mọi i;
khởi tạo huong[i] = 0 với mọi i (sẽ dòi qua trái trước)
i = N (mình sẽ thử dời phần tử cuối cùng trong mảng A truớc nhứt)
bước 2:
trong khi (i > 1) lặp /* khi phải dời phần tử 1 là đã xét hết mọi trường hợp */
.. nếu huong[i] là 0 thì /* đang cần dời phần tử i qua trái */
.... nếu count[i] > 1 thì /* còn có thể dời phần tử i qua trái được */
...... d = tổng của huong[j] với j>i
...... hoán vị A[count[i]+d] và A[count[i]+d-1]
...... giảm count[i] đi 1 (bớt đi 1 lần lặp cho phần tử i)
...... i = N /* sẽ thử tiếp với phần tử cuối cùng */
.... ngược lại /* 0 thể dời phần tử i qua trái được nữa => đảo hướng */
...... huong[i] = 1
...... giảm i đi 1 /* sẽ thử phần tử i-1 */
.... hết nếu /*count[] > 1*/
.. ngược lại /* huong[i] là 1 : đang cần dời phần tử i qua phải */
.... nếu count[i] < i thì /* còn có thể dời phần tử i qua phải được */
...... d = tổng của huong[j] với j>i
...... hoán vị A[count[i]+d] và A[count[i]+d+1]
...... tăng count[i] lên 1 (bớt đi 1 lần lặp cho phần tử i)
...... i = N /* sẽ thử tiếp với phần tử cuối cùng */
.... ngược lại /* 0 thể dời phần tử i qua phải được nữa => đảo hướng */
...... huong[i] = 0
...... giảm i đi 1 /* sẽ thử phần tử i-1 */
.... hết nếu /*count[] > 1*/
.. hết nếu /*huong[i] là 0*/
hết lặp /*trong khi i > 1*/
(vẫn còn phải xài 1 vòng lặp để tính d :()
Ở
http://www.geocities.com/permute_it/sjt_algo.html
họ có cho giải thuật hoán vị "Johnson-Trotter" xài đệ qui
Ở http://www.stud.uni-bayreuth.de/~a8...son_trotter.cpp
họ có thuật toán hoán vị 0 xài đệ qui
Để khử vòng lặp khi tính d, mình có thể sửa lại 1 tí:
bước 1: khởi tạo count[i] = i với mọi i;
khởi tạo huong[i] = 0 với mọi i (sẽ dời qua trái trước)
i = N (mình sẽ thử dời phần tử cuối cùng trong mảng A truớc nhứt)
d = 0 (chưa có độ dời) <=======
dN = 0;
bước 2:
trong khi (i > 1) lặp /* khi phải dời phần tử 1 là đã xét hết mọi trường hợp */
.. nếu huong[i] là 0 thì /* đang cần dời phần tử i qua trái */
.... nếu count[i] > 1 thì /* còn có thể dời phần tử i qua trái được */
...... hoán vị A[count[i]+d] và A[count[i]+d-1]
...... giảm count[i] đi 1 (bớt đi 1 lần lặp cho phần tử i)
...... i = N /* sẽ thử tiếp với phần tử cuối cùng */
...... d = dN /* phục hồi độ dời từ phần tử cuối cùng*/
.... ngược lại /* 0 thể dời phần tử i qua trái được nữa => đảo hướng */
...... huong[i] = 1
...... giảm i đi 1 /* sẽ thử phần tử i-1 */
...... nếu (i là N) thì
........ dN = 1 /* phần tử cuối cùng đang ở vị trí 1 -> lưu độ dời là 1 */
........ d = dN /* phần tử cuối cùng đang ở vị trí 1 -> những phần tử nhỏ hơn sẽ bị dời qua phải thêm 1 vị trí */
...... ngược lại
........ tăng d lên 1 /* phần tử này đang ở bên trái -> những phần tử nhỏ hơn sẽ bị dời qua phải thêm 1 vị trí */
...... hết nếu /*i là N*/
.... hết nếu /*count[] > 1*/
.. ngược lại /* huong[i] là 1 : đang cần dời phần tử i qua phải */
.... nếu count[i] < i thì /* còn có thể dời phần tử i qua phải được */
...... hoán vị A[count[i]+d] và A[count[i]+d+1]
...... tăng count[i] lên 1 (bớt đi 1 lần lặp cho phần tử i)
...... i = N /* sẽ thử tiếp với phần tử cuối cùng */
...... d = dN /* phục hồi độ dời từ phần tử cuối cùng*/
.... ngược lại /* 0 thể dời phần tử i qua phải được nữa => đảo hướng */
...... huong[i] = 0
...... giảm i đi 1 /* sẽ thử phần tử i-1 */
...... nếu (i là N) thì
........ dN = 0 /* phần tử cuối cùng đang ở vị trí cuối -> lưu độ dời là 0 */
........ d = dN /* phần tử cuối cùng đang ở vị trí cuối -> những phần tử nhỏ hơn sẽ KHÔNG bị dời qua phải thêm 1 vị trí */
...... hết nếu /*i là N*/
.... hết nếu /*count[] > 1*/
.. hết nếu /*huong[i] là 0*/
hết lặp /*trong khi i > 1*/
kienbon2
13-11-2008, 23:22
HIX, đọc những bài này mìn hoa hết cả mắt! có bạn nào dư thời gian và lòng hảo tâm hưóng dẫn cách tính độ phứac tạp của bài toán 8 hậu này được ko? mìn đọc sách của gv mà ko hiểu chi hết!
baby_xiucuibap
17-11-2008, 09:25
tui mứi học ```!mzzyx pác thông cảm......
đang nạp kiến thức.....
pnjsilver
20-11-2008, 14:02
8 hậu và mã đi tuần thì cần chú ý các lý thuyết về thuật giải, toán đồ thị
Các bạn ai có duyệt rộng 8 quân hậu bằng pascal ko? mình viết rồi mà không chạy được. các bạn xem sửa giup minh nhé.
đây là chuong trình của mình:
uses crt;
type mang=array[1..8]of byte;
queue= ^pt;
pt=record
b:array[1..8]of byte;
tr,link:queue;
end;
var
cuoi,mo,p,q:queue;
kt,i,k,m,j: byte;
a:array[1..8]of byte;
ok:boolean;
procedure push(var mo, p:queue);
begin
p^.link:=mo;
p^.tr:=nil;
mo^.tr:=p;
mo:=p;dispose(mo);
if cuoi=nil then cuoi:=mo;
end;
function pop( mo:queue): queue;
begin
p:=cuoi;
cuoi:=p^.tr ;
cuoi^.link:=nil;
pop:=p;
end;
procedure dr(var mo:queue);
begin kt:=1 ;
while (mo<>nil)and(kt<20) do
begin
p:=pop(mo);
for i:=1 to 8 do
a[i]:=p^.b[i];
for k:=1 to 8 do
if a[k]=0 then begin i:=k; break; end;
for j:=1 to 8 do
begin
ok:=true;
a[i]:=j;
if i=1 then i:=2
else
for m:=1 to i-1 do
begin
if (j=p^.b[m])or (m+p^.b[m]=i+j)or(j-i=p^.b[m]-m)then
ok:= false;
end;
if ok then begin
new(q);
for k:=1 to 8 do q^.b[k]:=a[k];
push(mo,q);
end;
end;
if i=8 then
for i:=1 to 8 do
begin
writeln(i ,a[i]);
break;
end;
end; kt:=kt+1; writeln(kt);
end;
begin clrscr;
mo:=nil;
for k:=1 to 8 do
a[k]:=0;
new(p);
for k:=1 to 8 do p^.b[k]:=a[k];
push(mo,p) ;
dr(mo);
readln;
end.
hức , căg cả mắt lên đọc cả đoạn code , cả đoạn phân tích mà vẫn chưa hỉu lắm . Dưới đây là đoạn code n quân hậu đặt trên bàn cờ nxn nhưg ct này chắc k hay = của các pác vì n=15 nó đã chạy đến cả 1min mấy s rồi nhưg khá đơn giản & dễ hỉu
const fi='hau.inp';
fo='hau.out';
var f:text;
ddc:array[1..1000] of boolean;
dddc1:array[2..2000] of boolean;
dddc2:array[-1000..1000] of boolean;
x:array[1..1000] of integer;
i,n,dem:longint;
procedure nhap;
begin
assign(f,fi);
reset(f);
readln(f,n);
close(f);
end;
procedure ghikq;
var k:integer;
begin
for k:=1 to n do write(f,k,',',x[k],' ');
inc(dem);
writeln(f);
end;
procedure try(i:integer);
var j:integer;
begin
for j:=1 to n do
if (ddc[j]=false) and (dddc1[i+j]=false) and (dddc2[i-j]=false) then
begin
x[i]:=j;
ddc[j]:=true;
dddc1[i+j]:=true;
dddc2[i-j]:=true;
if i=n then ghikq
else try(i+1);
ddc[j]:=false;
dddc1[i+j]:=false;
dddc2[i-j]:=false;
end;
end;
procedure xuly;
begin
fillchar(ddc,sizeof(ddc),false);
fillchar(dddc1,sizeof(dddc1),false);
fillchar(dddc2,sizeof(dddc2),false);
try(1);
end;
begin
nhap;
assign(f,fo);
rewrite(f);
xuly;
writeln(f,dem);
close(f);
end.
darklordvn14
01-01-2009, 12:02
Nói về bài xếp hậu trên bàn cờ n*n sao cho số hâu là nhiều nhất thì các sách tham khảo nào cũng có .
Tôi đã đọc và được biết rằng ở bàn 8*8 có 92 cách xếp tám quân hậu cơ!!!có thể tìm mua những quyển sách này ở nhiều nơi!
Còn bài mã đi tuần thì cũng có thôi!!
Tôi nghĩ bạn nên xếp bằng tay trước khi làm trên máy !
Chúc các bạn thành công!
truongmaitrang
13-02-2009, 09:44
Bài toán 8 quân hậu thì có 92 lời giải! và dùng giải thuật quay lui là hiệu quả nhất!
hichic_huhu
07-03-2009, 11:57
có ai làm rui` không vạy
cho em xin
^!^
nguyen cao dinh
20-03-2009, 16:07
cac bac oi cho em xin loi giai bai toan 8 quan hau
lời giải đây:
http://www.pgranks.com/game/game6.htm
ndphuong74
01-04-2009, 17:59
bạn truongmaitrang ơi bạn có thể nói rỏ hơn về giải thuật quay lui không?mình thật sự không hiểu cho lắm. Mình không biết trong bài 8 quân hậu chỗ nào thể hiện quay lui.
Đây mình có code bài này nè!!!!!!!!!mình cũng không biết ai viết nữa chỉ sưu tập được thôi.
code:
/* Bai toan tam hoang hau */
#include <stdio.h>
#include<conio.h>
int dong[8], cot[8], cheoxuoi[15], cheonguoc[15];
int socach = 0;
void print ()
{
int i;
printf("\n");
if (socach %5==0)
getch();
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();
socach++;
}
cot[j] = 1;
cheoxuoi[i+j] = 1;
cheonguoc[i-j+7] = 1;
}
}
}
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);
}
void main()
{
tim();
getch();
}
mình không hiểu hàm void thu(int i) chạy ra sao, thứ tự các câu lệnh chạy như thế nào.Monh các bác chỉ giáo.Em chân thành cám ơn!!!!!!!!!!!
bác Bete cho em hỏi 1 câu ngoài lề đc ko ạ ?
bác bao nhiêu tuổi rồi ạ, đang làm j` ?
Chẳng qua em học CNTT ^^~ nhưng có lẽ thầy em cũng chưa thể nào pro đc như bác ^^~
program xep_hau;
uses crt;
var c,dc1,dc2:array[1..100] of boolean;
a:array[1..100] of byte;
n:byte;dem:byte;
procedure nhap;
begin
write('Ban hay nhap co : ');
readln(n);
end;
procedure init;
begin
nhap;
dem:=0;
fillchar(c,sizeof(c),true);
fillchar(dc1,sizeof(dc1),true);
fillchar(dc2,sizeof(dc2),true);
end;
procedure ghinhan;
var i:byte;
begin
for i:=1 to n do write(a[i]);
writeln;
inc(dem);
end;
procedure try(i:byte);
var j:byte;
begin
for j:=1 to n do
if c[j] and dc1[i-j] and dc2[i+j] then
begin
a[i]:=j;
c[j]:=false;
dc1[i-j]:=false;
dc2[i+j]:=false;
if i=n then ghinhan
else try(i+1);
c[j]:=true;
dc1[i-j]:=true;
dc2[i+j]:=true;
end;
end;
begin
clrscr;
init;
try(1);
write('So cach xep ',n,' quan hau la : ',dem);
readln
end.
alibaba314
15-10-2009, 00:24
#include <stdio.h>
#define N 4
int col[N+1], up_diag[2*N+1], dn_diag[2*N+1], coln[N+1] ;
void addqueen(void);
main( )
{
int i ;
for ( i = 0 ; i <= N ; i++ )
col[i] = 1 ;
for ( i = 0 ; i <= 2*N ; i++ )
up_diag[i] = dn_diag[i] = 1 ;
addqueen( ) ;
getchar();
}
void addqueen(void)
{
int i, c, r ;
static int comb, row = -1 ;
row++ ; //hang
/*kiem tra cot */
for ( i = 0 ; i <= N ; i++ )
{
/* neu o co khong nam trong vung bi chieu */
if ( col[i] && up_diag[i+row] && dn_diag[row-i+N])
{
/* nho vi tri con co */
coln[row] = i ;
/* danh dau cot va duong cheo chua con hau */
col[i] = 0 ;
up_diag[i+row] = 0 ;
dn_diag[row-i+N] = 0 ;
/* khi hoan thanh tat cac hang */
if ( row >= N )
{
comb++ ;
printf ( "\n\n\ncombination no. %d", comb ) ;
for ( r = 0 ; r <= N ; r++ )
{
printf ( "\n\n" ) ;
for ( c = 0 ; c <= N ; c++ )
{
if ( c == coln[r] )
printf ( " Q " ) ;
else
printf ( " . " ) ;
}
}
}
else
addqueen( ) ;
/* bo danh dau o hang va duong cheo */
col[ coln[row] ] = 1 ;
up_diag[ row + coln[row] ] = 1 ;
dn_diag[ row - coln[ row ] + N ] = 1 ;
}
}
row-- ; /* giam hang, va tinh kha nang tiep theo */
}
bupbetainang
14-01-2010, 14:07
Bạn ui, mình cũng đang rất cần bài code của bài toán 8 quân hậu, nó là đề tài niên luận của mình trong học kì này đó, nhưng không hiểu sao mình không down được của love_ly, các bạn có tài liệu nào hay cho mình xin với
kiemkhach123
01-03-2010, 22:33
Bài toán 8 quân hậu thì có 92 lời giải! và dùng giải thuật quay lui là hiệu quả nhất!
cũng không hẳn là như vậy. Quay lui thử sai có cái lợi và cũng có cái hại của nó. Cái lợi là ở chỗ nó có thể tìm được 100% các lời giải. cái hại là ở chỗ chạy chậm + tốn ram (kể cả khi chúng ta chỉ tìm 1 lời giải, nó vẫn chậm).
Với bài toán N hậu, nhiều khi chúng ta chỉ cần tìm ra 1 lời giải đúng nhưng phải tìm thật nhanh.Để đáp ứng yêu cầu đó thì có 1 phương pháp đơn giản như sau:
Ký hiệu quân hậu đứng ở ô nằm trên hàng thứ i của lời giải là Q[i,j]. Các chỉ số dòng cột đánh từ trên xuống dưới, trái sang phải theo cách đánh số trong ma trận). Trong một ma trân vuông:
* các phần tử nằm trên cùng hàng có chỉ số hàng bằng nhau;
* các phần tử nằm trên cùng cột có chỉ số cột bằng nhau;
* các phần tử nằm trên cùng một đường chéo song song với đường chéo chính có hiệu chỉ số hàng với chỉ số cột bằng nhau;
* các phần tử nằm trên cùng một đường chéo song song với đường chéo phụ có tổng chỉ số hàng với chỉ số cột bằng nhau;
Vì thế ta gọi các đường chéo song song với đường chéo chính là đường chéo trừ (hay hiệu), các đường chéo song song với đường chéo phụ là đường chéo cộng (hay tổng).
Do đó, mỗi lời giải có thể được biểu diễn bởi dãy Q[1,i1],Q[2,i2],...,Q[n,in],thỏa mãn các điều kiện:
* Các chỉ số cột i1, i2,..., in đôi một khác nhau, hay chúng lập thành một hoán vị của các số 1, 2,.., n.
* Tổng chỉ số dòng và cột của các quân hậu 1+i1, 2+i2,..., n+in đôi một khác nhau;
* Hiệu chỉ số dòng và cột của các quân hậu 1-i1, 2-i2,...,n-in đôi một khác nhau.
Chẳng hạn lời 1 lời giải cho N = 8 được biểu diễn bới dãy ô (1 ,4),(2, 7), (3, 3), (4, 8), (5,2), (6,5), (7,1), (8,6). Ta có thể kiểm tra các điều kiện trên trong bảng:
i 1 2 3 4 5 6 7 8
j 4 7 3 8 2 5 1 6
i+j 5 9 6 12 7 11 8 14
i-j -3 -5 0 -4 3 1 6 2
Có một giải thuật đơn giản tìm một lời giải cho bài toán n quân hậu với n = 1 hoặc n ≥ 4:
1. Chia n cho 12 lấy số dư r. (r= 8 với bài toán tám quân hậu).
2. Viết lần lượt các số chẵn từ 2 đến n.
3. Nếu số dư r là 3 hoặc 9, chuyển 2 xuống cuối danh sách.
4. Bổ sung lần lượt các số lẻ từ 1 đến n vào cuối danh sách, nhưng nếu r là 8, đổi chỗ từng cặp nghĩa là được 3, 1, 7, 5, 11, 9, ….
5. Nếu r = 2, đổi chỗ 1 và 3, sau đó chuyển 5 xuống cuối danh sách.
6. Nếu r = 3 hoặc 9, chuyển 1 và 3 xuống cuối danh sách.
7. Lấy danh sách trên làm danh sách chỉ số cột, ghép vào danh sách chỉ số dòng theo thứ tự tự nhiên ta được một lời giải của bài toán.
Sau đây là một số ví dụ
* 14 quân hậu (r = 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
* 15 quân hậu (r = 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
* 20 quân hậu (r= 8): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17.
lehuydung
07-04-2010, 23:31
:D
anh oi ! em down không được
gui cho e voi traitimbang_sbtt@yahoo.com.vn
thank
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.