™((¯`°»†:. Tập thể lớp 11A12 .:†«°´¯))™
Chào mừng bạn đã đến với forum của tập thể lớp 11A12 K 2008-2011. Forum được design và phát triển by [C]uong . Nếu có thắc mắc gì xin liên hệ theo dc manhcuongpro13@yahoo.com
Cám ơn bạn đã ghé thăm 4rum của chúng tôi, mong các bạn sẽ ủng hộ 4rum và ghé thăm nhiều hơn nữa
™((¯`°»†:. Tập thể lớp 11A12 .:†«°´¯))™
Chào mừng bạn đã đến với forum của tập thể lớp 11A12 K 2008-2011. Forum được design và phát triển by [C]uong . Nếu có thắc mắc gì xin liên hệ theo dc manhcuongpro13@yahoo.com
Cám ơn bạn đã ghé thăm 4rum của chúng tôi, mong các bạn sẽ ủng hộ 4rum và ghé thăm nhiều hơn nữa
™((¯`°»†:. Tập thể lớp 11A12 .:†«°´¯))™
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

™((¯`°»†:. Tập thể lớp 11A12 .:†«°´¯))™

™((¯`°»†:. MÁI NHÀ CHUNG CỦA TẬP THỂ 11A12 .:†«°´¯))™
 
Trang ChínhTìm kiếmLatest imagesĐăng kýĐăng Nhập

Chào mừng bạn đã ghé thăm forum của lớp 11A12 k2008-2011 trường THPT Diễn Châu 2. Nếu đây là lần đầu tiên bạn truy cập vào forum thì hãy đọc hướng dẫn sử dụng forum. Bạn có thể đăng kí là thành viên của forum. Forum được design và phát triển by admin: [C]uong. Xem forum tốt nhất với trình duyệt mozilla firefox

Latest topics
» adfaf
Thuật toán sudoku I_icon_latest_reply09/07/10, 02:17 pm by [C]uong

» Link down
Thuật toán sudoku I_icon_latest_reply18/05/10, 05:03 pm by [C]uong

» List nhạc cần down
Thuật toán sudoku I_icon_latest_reply16/05/10, 09:47 pm by [C]uong

» Crack kis 2010 eng 9.0.0.736 Thành công 100%
Thuật toán sudoku I_icon_latest_reply15/05/10, 09:39 pm by [C]uong

» Tạo forum miễn phí
Thuật toán sudoku I_icon_latest_reply03/05/10, 11:28 pm by [C]uong

» Cảm xúc hôm nay của bạn thế nào ??
Thuật toán sudoku I_icon_latest_reply17/04/10, 08:57 pm by [C]uong

» Đại chiến xích bích 2009
Thuật toán sudoku I_icon_latest_reply13/04/10, 12:50 pm by [C]uong

» Hot girl bà kon ui !!(*_*)
Thuật toán sudoku I_icon_latest_reply08/04/10, 09:09 pm by [C]uong

» ảnh thú vị về love 11a12(thú vị)
Thuật toán sudoku I_icon_latest_reply04/04/10, 08:50 pm by [C]uong

» Ai ko xem thì phí
Thuật toán sudoku I_icon_latest_reply03/04/10, 11:04 pm by [C]uong

» nhanh nhanh ảnh đặc biệt bởi bàn tay chuyên gia
Thuật toán sudoku I_icon_latest_reply03/04/10, 10:21 pm by [C]uong

» Ảnh 26-3 lớp 11A12 (cực kool)
Thuật toán sudoku I_icon_latest_reply03/04/10, 09:25 pm by [C]uong

» Slide ảnh 26-3 nà !
Thuật toán sudoku I_icon_latest_reply03/04/10, 08:06 pm by [C]uong

» Danh ngôn về tình bạn !!
Thuật toán sudoku I_icon_latest_reply02/04/10, 11:32 pm by [C]uong

» Theme royale cho deskop
Thuật toán sudoku I_icon_latest_reply01/04/10, 09:34 pm by [C]uong

Top posters
[C]uong (258)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
DaiDa (32)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
duc&tai (27)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
lehoa (12)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
bou123 (9)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
conduongmauxanh (6)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
blueocean0909 (6)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
pucca_garu_fun (4)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
ducdatpro (3)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
maruko (3)
Thuật toán sudoku Vote_lcap1Thuật toán sudoku I_voting_barThuật toán sudoku Vote_lcap1 
Đăng Nhập
Tên truy cập:
Mật khẩu:
Đăng nhập tự động mỗi khi truy cập: 
:: Quên mật khẩu
Tìm kiếm
 
 

Display results as :
 
Rechercher Advanced Search
Thống Kê
Hiện có 4 người đang truy cập Diễn Đàn, gồm: 0 Thành viên, 0 Thành viên ẩn danh và 4 Khách viếng thăm

Không

Số người truy cập cùng lúc nhiều nhất là 22 người, vào ngày 14/10/24, 10:40 pm

 

 Thuật toán sudoku

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giả Thông điệp
[C]uong
Admin
Admin
[C]uong

Khủng Long
Nam Pisces
Tổng số bài gửi : 258
Điểm Điểm : 466
Ngày tham gia Ngày tham gia : 08/07/2009
Age : 31
Đến từ Đến từ : Đô Thành CiTy

Character sheet
Point:
Thuật toán sudoku Left_bar_bleue50/50Thuật toán sudoku Empty_bar_bleue  (50/50)

Thuật toán sudoku Vide
Bài gửiTiêu đề: Thuật toán sudoku   Thuật toán sudoku I_icon_latest_reply28/07/09, 06:18 pm

Mình đã viết xong chương trình sodoku bằng pascal. Thuật giải cũng rất đơn giản nhưng vì tối ưu thời gian giải nên cấu trúc chương trình khá phức tạp. Nếu như ai đó nói Đệ qui quay lui thì coi chừng sai lầm đó. Mình cũng thử rồi, nhưng solve tới >15p (ặc ặc).
Thuật toán mình như sau:
Nhập dữ liệu vào mảng 2 chiều sdk[1..9,1..9] of byte; Set sdk[i,j] := 0
1. Đánh dấu hàng và cột bằng mảng: r[1..9,1..9] và c[1..9,1..9] of boolean
Kiểm tra 1 vị trí trên mảng sdk, nếu tồn tại sdk[i,j]> 0 :
[/indent]r[j,sdk[i,j]]:=true: TRên hàng đó đã có số sdk[i,j]
[indent][/indentc]r[sdk[i,j],i]:=true: TRên hàng đó đã có số sdk[i,j]
2. Đánh dấu mảng 3*3 chứa sdk[i,j] bằng mảng m[1..3,1..3,1..9] of boolean
[indent]
if sdk[i,j]> then m[(i div 3)+1,(j div 3) +1, sdk[i,j]]:=true;
2. Xử lý :
2.1 Dùng 3 procedure kiểm tra: Nếu trên 1 hàng hoặc 1 cột hoặc 1 mảng 3*3 mà tồn tại duy nhất 1 vị trí của số nào đó thì đặt nó vào, quay lại bước 1. Repeat cho đến khi ko có giá trị thay đổi (Ko có số nào được đặt vào.
procedure check_ROW(row,col:tp);
var i,j,k,coltmp,rowtmp,count,numtmp:tp;
a:array[1..9] of boolean;
begin
if sdk[row,col]>0 then exit;
count:=0;
coltmp:=0;
rowtmp:=0;
for i:=1 to n do a[i]:=true;
for i:=1 to n do
a[sdk[row,i]]:=false;

for i:=1 to n do {check col de so sanh logic}
a[sdk[i,row]]:=false;
for i:=1 to n do
if a[i]= true then
begin
inc(count);
numtmp:=i;
coltmp:=col;

end;
if (count=1) then
begin
sdk[row,col]:=numtmp;
RESET_Matrix;
savepos[row,col]:=true;
inc(Numsolved);
writeln('a[',row,' ',col,']=',numtmp);
end;

procedure check_COL(row,col:tp);
var i,j,k,coltmp,rowtmp,count,numtmp:tp;
a:array[1..9] of boolean;
begin
if sdk[row,col]>0 then exit;
count:=0;
coltmp:=0;
rowtmp:=0;
for i:=1 to n do a[i]:=true;
for i:=1 to n do
a[sdk[i,col]]:=false;

for i:=1 to n do {check col de so sanh logic}
a[sdk[col,i]]:=false;
for i:=1 to n do
if a[i]= true then
begin
inc(count);
numtmp:=i;
coltmp:=col;

end;
if (count=1) then
begin
sdk[row,col]:=numtmp;
RESET_Matrix;
savepos[row,col]:=true;
inc(Numsolved);
end;
end;

end;
procedure Check_Square(col,row,Num:tp); { Kiem tra kich thuoc 3x3}
var i,j,k,count,rowtmp,coltmp:tp;
begin
count:=0;
rowtmp:=0;
coltmp:=0;
for i:=1 to 3 do
for j:=1 to 3 do
if chk[col*3+i,row*3+j,num]=true then
begin
count:=count+1;
rowtmp:=row*3+j;
coltmp:=col*3+i;
end;
if count=1 then

begin
sdk[coltmp,rowtmp]:=Num;
savepos[coltmp,rowtmp]:=true;
RESET_matrix;
inc(Numsolved);
end;
end;

2.2 Sau khi xử lý bước 2.1 mà ma trận vẫn chưa full, ta mới dùng đệ qui:
2.2.1. Set 1 mảng bao gồm các vị trí có khả năng đặt tại 1 ô trống trên sdk:
pa[1..81, 1..9] of byte; (Lúc này ta bẻ mảng 9*9 thành mảng 1 chiều 81 đơn vị)
(Position availble num)
pac[1..81] of byte: Lưu lại số các số có khả năng đặt tại vị trí sdk[i,j]=0 (Position availble count)
p:=0;
for i:=1 to n do
for j:=1 to n do
if sdk[i,j]=0 then
begin
p:=p+1;
count:=0;
for k:=1 to n do
if (r[i,k]=true) and (c[k,j]=true) and (m[((i-1) div 3)+1,((j-1) div 3)+1,k]=true) then
begin
count2:=count+1;
pa[p,count]:=k;
pac[p]:=count;
end;

end;
2.2.3 Viết 1 procedure Set lại ma trận sau khi đặt 1 số và 1 Unreset khi ta lấy số đi, cần thiết cho Đệ qui và quay lui:
procedure RESET_BB(row,col,num:tp);
var i,j,p,q:tp;
begin
r[row,num]:=false;
c[num,col]:=false;
p:=((row-1) div 3)+1; { Tinh tien ma tran len 1 bac cho phu hop voi TYPE}
q:=((col-1) div 3)+1;
m[p,q,num]:=false;
end;
procedure UNRESET_BB(row,col,num:tp);
var i,j,p,q:tp;
begin
r[row,num]:=true;
c[num,col]:=true;
p:=((row-1) div 3)+1;
q:=((col-1) div 3)+1;
m[p,q,num]:=true;
end;

2.2.4 Đệ qui quay lui:
procedure BackBreak(cur:byte);
var i:tp;
begin
if (cur>count) then
begin
writeln('------------------');
output;
halt;
end;
for i:=1 to pac[cur] do
begin
if (r[rs[cur],pa[cur,i]]=true) and (c[pa[cur,i],cs[cur]]) then
begin
savepos[rs[cur],cs[cur]]:=true;
sdk[rs[cur],cs[cur]]:=pa[cur,i];
inc(numsolved);
reset_BB(rs[cur],cs[cur],pa[cur,i]);
backbreak(cur+1);
dec(numsolved);
sdk[rs[cur],cs[cur]]:=0;
UNRESET_BB(rs[cur],cs[cur],pa[cur,i]);
end;
end;
end;
2.2.5 Còn đây là phần kết hợp các module trên để giải quyết bài toán:
procedure SOLVE;
var i,j,k,num1,num2,num3,num:tp;
begin
repeat
num:=numsolved;
repeat
num1:=numsolved;
writeln('Checking square....');
for i:=0 to 2 do
for j:=0 to 2 do
for k:=1 to n do

check_square(i,j,k);
until (Num1=numsolved)or(numsolved=81){or(keypressed)};
repeat
num2:=numsolved;
writeln('Checking row....');
for i:=1 to n do
for j:=1 to n do
check_ROW(i,j);

until (Num2=numsolved)or(numsolved=81);{or(keypressed);}
repeat
num3:=numsolved;
writeln('Checking col....');
for i:=1 to n do
for j:=1 to n do
check_COL(i,j);
until (Num3=numsolved)or(numsolved=81);
until (numsolved=num)or(numsolved=81);{or(keypressed);}
if numsolved=81 then exit else
begin
writeln('Back breaking....');
INIT_BB;
BackBreak(1);
end;
end;
---------------------------------------------
Mình đã test thành công các bài trên trang 24h.com mà không cần đệ qui. Chỉ có các bài sodoku rất khó mới dùng tới đệ qui và kết quả ko tới 0.1s . Nay mong các bạn đóng ghóp các bài sodoku khó để mình hoàn thiện chương trình. Thân.
Về Đầu Trang Go down
https://lovetui.forumvi.com
 

Thuật toán sudoku

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum: Bạn không có quyền trả lời bài viết
™((¯`°»†:. Tập thể lớp 11A12 .:†«°´¯))™ :: ™((¯`°»†:. Công nghệ thông tin .:†«°´¯))™ :: Lập trình :: Pascal -