递归循环和 DFS

Question

我的任务是使用深度优先搜索找到所有大小为 N 的拉丁方块。我需要检查正方形大小 N 的所有可能变体是否是拉丁语。它可以通过从 1 到 N 的 N * N 嵌套循环 'for' 来完成（位置（0,0）的第一个循环，位置（0,1）的第二个嵌套等等）。显然，它只适用于某些特定的 N₀。我需要一个更通用的解决方案，它可以适用于随机 N，所以我想编写一个递归过程，根据输入的 N 来模仿这些 N * N 循环。

现在我相信，我有办法了。

Answer 1

好的，似乎有效。希望有人会发现它有用。

更新：删除无用的一维数组，现在似乎工作得更快（正如我计算的（但未通过实验检查），对于 N=4，以前的方法将花费 ≈218.07 小时）。

Upd2：从在 LS 检查中使用标志和 'if' 移动到标签，似乎更快（两次实验平均 271.172 秒找到大小为 4 的 LS（检查 4294967296 变体）与之前的 4041.453 秒相比更新）。

procedure filling(str, col: Integer);
var
I, I1, J1, a, b, fl: Integer;
label
skip;

begin
 for I := 1 to N do begin
  lat_sq[str, col]:=I;
  if (col<N-1) then filling(str, col+1)
   else if  (str<N-1) then filling(str+1, 0)
  else if (str=N-1) and (col=N-1) then begin
  

   
   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 goto skip; 
      for b := 0 to N-1 do
       if (b<>J1) and (lat_sq[I1, J1]=lat_sq[I1, b]) then goto skip; 
    end;

   
    for I1 := 0 to N-1 do begin
     for J1 := 0 to N-1 do
     write(lat_sq[I1, J1]);
     writeln;
    end;

    writeln;

  
   skip:
  end;
 end;

end;

upd3: 决定保留以前的代码，因为这个新代码有另一种 LS 检查方法：如果无法填充检查的单元格，它会移动到另一个循环进行 I 迭代。在不到 1 毫秒的时间内找到 N=4 的 LS，在 1468.687 秒内找到 N=6，更高的 N 需要无意义的时间。 N_1表示N-1。

upd4：删除无用的额外检查，如果发现 N=6 的 LSs 持续 1410.719 秒。

procedure filling(str, col: Integer);
var
I, I1, J1, a, b, fl: Integer;
label
skip;

begin
 for I := 1 to N do begin

  lat_sq[str, col]:=I;

  fl:=1;

  for I1 := 0 to str-1 do
   if (lat_sq[I1, col]=lat_sq[str, col]) then goto skip;

  for J1 := 0 to col-1 do
   if (lat_sq[str, J1]=lat_sq[str, col]) then  goto skip; 



  if (col<n_1) then filling(str, col+1)
   else if (str<n_1) then filling(str+1, 0)




   else begin
    
    for I1 := 0 to N-1 do begin
     for J1 := 0 to N-1 do
     write(lat_sq[I1, J1]);
     writeln;
    end;

    writeln;
    

    inc(count);

   end; 
  skip:
 end;

end;

Answer 2

首先，你需要一个排列生成器，比如 Heap 的算法：

https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/

每行以 1、2、...、N 开头。

对于我=到N 对第 i 行进行排列，并检查其中没有重复任何专栏。我在那里，采取这一行的下一个排列。如果没有重复，就取下一行（next i）。

递归循环和 DFS

Recursive cycles and DFS

delphi

recursion

depth-first-search