I have a task to find all latin squares of size N with Depth-first search. So, I need something as N*N nested "for" loops. This way will work only for some particular N, though. Instead of using this number of loops it'll be better to do it with recursive procedure. Please, explain how can I do this procedure as it seems pretty confusing.
CodePudding user response:
Ok, seems working. Hope someone'll find it useful.
procedure filling(pos: Integer);
var
I, J, str, col, I1, J1, a, b, fl: Integer;
begin
for I := 1 to N do begin
boa[pos]:=I;
if ((pos 1)<N_N) then filling(pos 1);
if (pos 1=N_N) then begin
str:=0;
col:=-1;
for J := 0 to N_N-1 do begin
if (col<N-1) then begin
inc(col);
lat_sq[str, col]:=boa[J];
end else if (str<N-1) then begin
col:=0;
inc(str);
lat_sq[str, col]:=boa[J];
end;
end;
fl:=1;
for I1 := 0 to N-1 do
for J1 := 0 to N-1 do begin
for a := 0 to N-1 do
if (a<>I1) and (lat_sq[I1, J1]=lat_sq[a, J1]) then begin
fl:=0;
break;
end;
for b := 0 to N-1 do
if (b<>J1) and (lat_sq[I1, J1]=lat_sq[I1, b]) then begin
fl:=0;
break;
end;
end;
if (fl=1) then begin
for I1 := 0 to N-1 do begin
for J1 := 0 to N-1 do
write(lat_sq[I1, J1]);
writeln;
end;
writeln;
end;
end;
end;
end;
CodePudding user response:
First, you need a permutation generator, like Heap's alghorithm:
https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
Start each row with 1, 2, ..., N.
For i = to N Take a permutation of row i, and check there are no repetitions in any column. I there are, take the next permutation of this row. If there are no repetitions, just take the next row (next i).