Home > Blockchain >  Recursive cycles and DFS
Recursive cycles and DFS

Time:04-15

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).

  • Related