The Square-Diff problem
 

To entertain myself, I decide to tackle a few example of ssquare diff . any square is valid except if b-a=1
min solution seem to be 13.
there is a solution for 14, but not for 15-19... ( or maybe i was too tired to find it).

I found a solution for upto 43 ( it was done manually so no the most efficient manner).
with graphviz I obtained the image below .
I doubt there is any gap further up

[code]
graph gray { graph[center=true, margin=0.2, nodesep=0.1, ranksep=0.3]
node[fontname="Courier-Bold", fontsize=9, width=0.4, height=0.4, fixedsize=false]

//*1--17--13--4--8--12--3--7--16--20--11--2--6--15--19--10--14--18--9--5 long 20
//*21--17--1--5--9--18--14--10--19--15--6--2--11--20--16--7--3--12--8--4--13--22 long 22
//*21--17--1--5--9--18--22--13--4--8--12--3--7--16--20--11--2--6--15--19--10--14--23 long 23
//*24--8--4--13--22--18--9--5--1--17--21--12--3--7--16--20--11--2--6--15--19--10--14--23 long 24
//*25--9--18--22--13--4--8--24--15--19--23--14--10--6--2--11--20--16--7--3--12--21--17--1--5 long 25
//*5--1--26--17--21--12--28--3--7--16--20--11--27--2--6--10--14--23--19--15--24--8--4--13--22--18--9--25
//*29--25--9--18--22--13--4--8--24--15--19--23--14--10--1--5--30--26--17--21-12--28--3--7--32--16--20--11--27--2--6--31 long 32
node [shape = doublecircle]; 38 43;
node [shape = circle];
38--29 [label="start",color=red]
29--25--34--9--18--22--13--4--8--33--24--40--15--19--23--14--10--1--5--30--26--42--17--21--37--12--28--3--7--32--41--16--20--36--11--27--2--6--31--35--39[color=red];
39--43[color=red,label="end"];
9--5[color=gray];
11 -- 7 [color=gray];
13 -- 9[color=gray] ;
15 -- 11[color=gray];
16 -- 12[color=gray];
17--13[color=gray];
24--20[color=gray];
25--21[color=gray];
26--22[color=gray];
27--23[color=gray];
28--24[color=gray];
31--27[color=gray];
32--28[color=gray];
33--29[color=gray];
34--30[color=gray];
36--32[color=gray];
37--33[color=gray];
38--34[color=gray];
40--36[color=gray];
42--38[color=gray];
44--40;
14 -- 5[color=gray];
17 -- 8[color=gray];
25--16[color=gray];
27--18[color=gray];
28--19[color=gray];
29--20[color=gray];
30--21[color=gray];
31--22[color=gray];
32--23[color=gray];
35--26[color=gray];
36--27[color=gray];
37--28[color=gray];
39--30[color=gray];
40--31[color=gray];
42--33[color=gray];
43--34[color=gray];
44--35;
17--1[color=gray];
18 -- 2[color=gray];
19 -- 3[color=gray];
20 -- 4[color=gray];
21 -- 5[color=gray];
22 -- 6[color=gray];
23 -- 7[color=gray];
26--10[color=gray];
29--13[color=gray];
30--14[color=gray];
31--15[color=gray];
33--17[color=gray];
34--18[color=gray];
35--19[color=gray];
38--22[color=gray];
39--23[color=gray];
43--27[color=gray];
44--28;

35--10[color=gray];
38--13[color=gray];
39--14[color=gray];
43--18[color=gray];
44--19;
overlap=false;
splines=true;
}
[/code]

The starting node is 38,end is 43... and I didn't manage to put arrow instead of simple lines

[QUOTE=firejuggler;478218]To entertain myself, I decide to tackle a few example of ssquare diff . any square is valid except if b-a=1
min solution seem to be 13.
there is a solution for 14, but not for 15-19... ( or maybe i was too tired to find it).

I found a solution for upto 43 ( it was done manually so no the most efficient manner).
with graphviz I obtained the image below .
I doubt there is any gap further up

[code]
graph gray { graph[center=true, margin=0.2, nodesep=0.1, ranksep=0.3]
node[fontname="Courier-Bold", fontsize=9, width=0.4, height=0.4, fixedsize=false]

//*1--17--13--4--8--12--3--7--16--20--11--2--6--15--19--10--14--18--9--5 long 20
//*21--17--1--5--9--18--14--10--19--15--6--2--11--20--16--7--3--12--8--4--13--22 long 22
//*21--17--1--5--9--18--22--13--4--8--12--3--7--16--20--11--2--6--15--19--10--14--23 long 23
//*24--8--4--13--22--18--9--5--1--17--21--12--3--7--16--20--11--2--6--15--19--10--14--23 long 24
//*25--9--18--22--13--4--8--24--15--19--23--14--10--6--2--11--20--16--7--3--12--21--17--1--5 long 25
//*5--1--26--17--21--12--28--3--7--16--20--11--27--2--6--10--14--23--19--15--24--8--4--13--22--18--9--25
//*29--25--9--18--22--13--4--8--24--15--19--23--14--10--1--5--30--26--17--21-12--28--3--7--32--16--20--11--27--2--6--31 long 32
node [shape = doublecircle]; 38 43;
node [shape = circle];
38--29 [label="start",color=red]
29--25--34--9--18--22--13--4--8--33--24--40--15--19--23--14--10--1--5--30--26--42--17--21--37--12--28--3--7--32--41--16--20--36--11--27--2--6--31--35--39[color=red];
39--43[color=red,label="end"];
9--5[color=gray];
11 -- 7 [color=gray];
13 -- 9[color=gray] ;
15 -- 11[color=gray];
16 -- 12[color=gray];
17--13[color=gray];
24--20[color=gray];
25--21[color=gray];
26--22[color=gray];
27--23[color=gray];
28--24[color=gray];
31--27[color=gray];
32--28[color=gray];
33--29[color=gray];
34--30[color=gray];
36--32[color=gray];
37--33[color=gray];
38--34[color=gray];
40--36[color=gray];
42--38[color=gray];
44--40;
14 -- 5[color=gray];
17 -- 8[color=gray];
25--16[color=gray];
27--18[color=gray];
28--19[color=gray];
29--20[color=gray];
30--21[color=gray];
31--22[color=gray];
32--23[color=gray];
35--26[color=gray];
36--27[color=gray];
37--28[color=gray];
39--30[color=gray];
40--31[color=gray];
42--33[color=gray];
43--34[color=gray];
44--35;
17--1[color=gray];
18 -- 2[color=gray];
19 -- 3[color=gray];
20 -- 4[color=gray];
21 -- 5[color=gray];
22 -- 6[color=gray];
23 -- 7[color=gray];
26--10[color=gray];
29--13[color=gray];
30--14[color=gray];
31--15[color=gray];
33--17[color=gray];
34--18[color=gray];
35--19[color=gray];
38--22[color=gray];
39--23[color=gray];
43--27[color=gray];
44--28;

35--10[color=gray];
38--13[color=gray];
39--14[color=gray];
43--18[color=gray];
44--19;
overlap=false;
splines=true;
}
[/code]

The starting node is 38,end is 43... and I didn't manage to put arrow instead of simple lines[/QUOTE]
Has the same logic constraints I listed in the sum problem. Maybe you can use a setup similar to the one used there.