请用pl/sql解欧拉计划594题:菱形划分法

〇〇

根据
O1,1中间有4点，必须用3点，连上2条线（与边缘上的点连的不算），所有点的度 之和=4
猜测
O2,1中间有9点，必须用8点，连上9条线（与边缘上的点连的不算），所有点的度 之和=18

〇〇

〇〇 发表于 2017-4-7 10:50
根据
O1,1中间有4点，必须用3点，连上2条线（与边缘上的点连的不算），所有点的度 之和=4
猜测

连线只能和邻居，即纵横坐标差距都在1以内的

〇〇

〇〇 发表于 2017-4-7 10:55
连线只能和邻居，即纵横坐标差距都在1以内的

同在一个单位正方形中的4点最多只能连3条线（如果有斜线），或4条直线

〇〇

〇〇 发表于 2017-4-7 11:16
同在一个单位正方形中的4点最多只能连3条线（如果有斜线），或4条直线

https://github.com/JuliaGraphs/LightGraphs.jl 一个图论的包

〇〇

〇〇 发表于 2017-4-7 10:50
根据
O1,1中间有4点，必须用3点，连上2条线（与边缘上的点连的不算），所有点的度 之和=4
猜测

猜测错误,左图的度=16,右图的度=18

newkid

〇〇 发表于 2017-4-7 09:09
已知3点求第4点的算法 p4=p1+p3-P2仍然可用

为什么要求第四点？
按我的方法变成整数格子坐标后，所有图形都可以轻易画出来。先构造所有小线段，然后四个线段首位衔接组成图形。
拼图的算法也不难，就是不知道对付大图的效率如何。

〇〇

newkid 发表于 2017-4-7 21:30
为什么要求第四点？
按我的方法变成整数格子坐标后，所有图形都可以轻易画出来。先构造所有小线段，然后 ...

算第4点和摆线段本质是一样的

〇〇

把坐标上的格点标号,再把相邻格点间的线段也编号,就能得到所有正方形和平行四边形的编号.其中ln是线段编号，端点，nl是端点，线段编号的字典.
N=4
NN=N*N
po=map(x->(x,ceil(Int,x/N),(x-1)%N+1),1:NN);
nb=Array{Array{Int}}(NN);
map(z->(nb[z]=1:NN;map(x->nb[z][x]=0,1:NN)),1:NN);
k=[1,N,NN+1-N,NN]
ln=Dict{Int,Tuple{Int,Int}}(); #n (x, y)
nl=Dict{Tuple{Int,Int},Int}(); #(x, y) n
#sq=Dict{Array{Int}}[];
for i in po
for j in po
if !(i[1] in k) && !(j[1] in k) && i[1]<j[1] && abs(i[2]-j[2])<=1 && abs(i[3]-j[3])<=1
nb[i[1]][countnz(nb[i[1]])+1]=j[1]
ln[length(ln)+1]=(i[1],j[1])
nl[(i[1],j[1])]=length(ln)
end
end
end
ln_no=length(ln)
for Ln1 in 1:ln_no
p1,p2=ln[Ln1][1],ln[Ln1][2]
for Ln2 in 1:ln_no
p_1,p3=ln[Ln2][1],ln[Ln2][2]
if p1==p_1 && p2<p3  #x1,y1 -- x1 ,y2
x4=po[p2][2]+po[p3][2]-po[p1][2]
y4=po[p2][3]+po[p3][3]-po[p1][3]
p4=0
Ln3=Ln4=0
for p in po
  if (p[2],p[3])==(x4,y4) p4=p[1] end
end
if p4>0 && !(p4 in k)
  Ln3=nl[min(p2,p4),max(p2,p4)]
  Ln4=nl[min(p3,p4),max(p3,p4)]
  #($x4,$y4,[$p4])
  println("$Ln1--$Ln2--$Ln3--$Ln4($p1 $p2 $p4 $p3)")
end
end
end
end
下面是O1,1的4*4格点的四边形,把上述程序的N值改为5，就能得到O2,1的
1--2--5--8(2 3 6 5)
1--3--6--11(2 3 7 6)
1--4--7--15(2 3 8 7)
2--3--9--12(2 5 9 6)
2--4--10--16(2 5 10 7)
3--4--14--17(2 6 11 7)
5--6--13--16(3 6 10 7)
5--7--14--19(3 6 11 8)
6--7--18--20(3 7 12 8)
8--9--13--21(5 6 10 9)
8--10--14--23(5 6 11 10)
9--10--22--24(5 9 14 10)
11--12--16--21(6 7 10 9)
11--13--17--23(6 7 11 10)
11--14--18--26(6 7 12 11)
12--14--22--27(6 9 14 11)
13--14--25--28(6 10 15 11)
15--16--19--23(7 8 11 10)
15--17--20--26(7 8 12 11)
16--17--24--27(7 10 14 11)
16--18--25--29(7 10 15 12)
19--20--28--29(8 11 15 12)
21--22--25--30(9 10 15 14)
23--24--28--30(10 11 15 14)
26--27--29--30(11 12 15 14)

〇〇

把每个单元格用对角线划分成4个三角形,在每个三角形中各选择1点,如果某个编号的正方形或平行四边形包含了一些点,
那么也包含其中某个点的其他正方形或平行四边形就不能再用了。
下面的语句产生这些点（对于O1,1,有9*4=36个黑点，其中8个边角的无用）
a=Array{Array{Float64,1}}(36);
u=[[.5,.25],[.5,.75],[.25,.5],[.75,.5]]
N=4
for i in 1:9
for j in 1:4
p=[ceil(Int,i/3),(i-1)%3+1]
a[(i-1)*4+j]=p+u[j]
print(a[(i-1)*4+j])
end
end

这是判断某点在四边形内部的函数
function pt_in_rect(t::Array{Float64},r::Array{Array{Int,1},1})
c=0
for i in 1:4
s=r
e=r[i%4+1]
#println(s,e)
if s[2]==e[2] continue; end
if t[2]<min(s[2],e[2]) continue; end
if t[2]>max(s[2],e[2]) continue; end
d=(t[2]-s[2])*(e[1]-s[1])/(e[2]-s[2])+s[1]
if d>t[1] c=c+1 end
end
c%2
end
下面的语句储存所有可能的形状(O1,1包含4*4个格点，四角的无用)
N=4
NN=N*N
po=map(x->(x,ceil(Int,x/N),(x-1)%N+1),1:NN);

nb=Array{Array{Int}}(NN);

map(z->(nb[z]=1:NN;map(x->nb[z][x]=0,1:NN)),1:NN);

k=[1,N,NN+1-N,NN]

ln=Dict{Int,Tuple{Int,Int}}(); #n (x, y)

nl=Dict{Tuple{Int,Int},Int}(); #(x, y) n



for i in po
for j in po
if !(i[1] in k) && !(j[1] in k) && i[1]<j[1] && abs(i[2]-j[2])<=1 && abs(i[3]-j[3])<=1
nb[i[1]][countnz(nb[i[1]])+1]=j[1]
ln[length(ln)+1]=(i[1],j[1])
nl[(i[1],j[1])]=length(ln)
end
end
end

sq=Dict{Int,Array{Int}}();

ln_no=length(ln)

for Ln1 in 1:ln_no
p1,p2=ln[Ln1][1],ln[Ln1][2]
for Ln2 in 1:ln_no
p_1,p3=ln[Ln2][1],ln[Ln2][2]
if p1==p_1 && p2<p3  #x1,y1 -- x1 ,y2

x4=po[p2][2]+po[p3][2]-po[p1][2]
y4=po[p2][3]+po[p3][3]-po[p1][3]

p4=0
Ln3=Ln4=0
for p in po
  if (p[2],p[3])==(x4,y4) p4=p[1] end
end
if p4>0 && !(p4 in k)
  Ln3=nl[min(p2,p4),max(p2,p4)]
  Ln4=nl[min(p3,p4),max(p3,p4)]
  #($x4,$y4,[$p4])
  println("$Ln1--$Ln2--$Ln3--$Ln4($p1 $p2 $p4 $p3)")
  sq[length(sq)+1]=[p1 ,p2 ,p4 ,p3]
end
end
end
end

共有25种形状，sq的4元数组记录它的顶点编号
julia> sq
Dict{Int32,Array{Int32,N}} with 25 entries:
  25 => [11,12,15,14]
  19 => [7,8,12,11]
  24 => [10,11,15,14]
  15 => [6,7,12,11]
  10 => [5,6,10,9]
  20 => [7,10,14,11]
  5  => [2,5,10,7]
  3  => [2,3,8,7]
  2  => [2,3,7,6]
  9  => [3,7,12,8]
  11 => [5,6,11,10]
  18 => [7,8,11,10]
  6  => [2,6,11,7]
  14 => [6,7,11,10]
  16 => [6,9,14,11]
  12 => [5,9,14,10]
  17 => [6,10,15,11]
  22 => [8,11,15,12]
  8  => [3,6,11,8]
  13 => [6,7,10,9]
  23 => [9,10,15,14]
  4  => [2,5,9,6]
  21 => [7,10,15,12]
  7  => [3,6,10,7]
  1  => [2,3,6,5]

julia> sq_len=length(sq)
25


下面的语句产生覆盖了每个点的编号形状
for pt in 1:36
print("\npt $pt:")
for sq1 in 1:sq_len
if pt_in_rect(a[pt],map(x->[po[x][2],po[x][3]],sq[sq1]))==1
print(" ",sq1)
end
end
end

从而可以得到与某个编号的形状不相容的形状编号

先任选一个编号最小的形状，得到它覆盖的点，也得到还允许选的形状编号，再从这些编号中选最小的1个，扩大黑点，再次缩小可选范围
利用这个思路递归下去，直到八边形内所有黑点都被覆盖，就输出了一个解，如果没有可用形状，也退出。
类似的思路参见http://www.ituring.com.cn/article/274754

〇〇

〇〇 发表于 2017-4-8 20:57
把每个单元格用对角线划分成4个三角形,在每个三角形中各选择1点,如果某个编号的正方形或平行四边形包含了 ...

s=r
--->
s=r[i   ]