我的任務是通過深度優先搜索找到所有大小為 N 的拉丁方格。我需要檢查所有可能的正方形大小 N 的變體是否是拉丁文。可以使用從 1 到 N 的 N * N 個嵌套回圈“for”來完成（位置（0,0）的第一個回圈，位置（0,1）的第二個嵌套回圈，依此類推）。顯然，它只適用于某些特定的 N?。我需要一個更通用的解決方案，它可以用于隨機 N，所以我想撰寫一個遞回程序，根據輸入的 N 模擬這些 N * N 個回圈。
現在我相信，我有一個解決方案。
uj5u.com熱心網友回復：
首先，您需要一個置換生成器，例如 Heap 的演算法：
https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
每行以 1、2、...、N 開頭。
For i = to N 對第 i 行進行排列，并檢查任何列中沒有重復。我有，取這一行的下一個排列。如果沒有重復，只需取下一行（下一個 i）。
uj5u.com熱心網友回復：
好的，似乎作業。希望有人會發現它有用。
更新：洗掉了無用的一維陣列，現在似乎作業得更快（正如我計算的（但沒有通過實驗檢查），以前的方法需要 ≈218.07 小時 N=4）。
Upd2：從在 LS 檢查中使用標志和“如果”轉移到標簽，似乎更快（兩次實驗平均 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 次迭代。找到 N=4 的 LS 不到 1 毫秒，找到 N=6 的 1468.687 秒，更高的 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;
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/471643.html
上一篇：在DelphiTEdgeBrowser中單擊HTML元素？
下一篇：一個物件與另一個物件的統一碰撞