Doing so, a little rebuild of Paul's code gives
Clear[dulgerciSquareSequence]
dulgerciSquareSequence[n_Integer] :=
Module[{b = Subsets[Range[n], {2}], s, ns, o, g, g1, c, p, bFound = False},
s = Select[b, IntegerQ[Sqrt[Plus @@ #]] &];
ns = Complement[b, s];
(* try every from the ns non-square vertices *)
For[o = 1, o <= Length[ns], ++o,
g = Graph[Join[s, {ns[[o]]}]];
g1 = UndirectedGraph[g];
c = FindHamiltonianCycle[g1];
If[Length[c] > 0,
bFound = True;
c = ToString /@ Flatten[c];
c = StringReplace[c, "\[UndirectedEdge]" .. -> ","];
p = DeleteDuplicates[Flatten[StringCases[c, RegularExpression["\\d+"]]]];
(* should cut the non-square vertex *)
Print[p]
]
];
If[! bFound, Print["No sequence found for n = ", n]]
] /; n > 5
lets test this
dulgerciSquareSequence[15]
{1,15,10,6,3,13,12,4,5,11,14,2,7,9 | 8}
this is your solution for n=15 in reverse order: 9+8=17, here is the split.
dulgerciSquareSequence[16]
{1,15,10,6,3,13,12,4,5,11,14,2,7,9,16 | 8}
dulgerciSquareSequence[17]
{1,15,10,6,3,13,12,4,5,11,14,2,7,9,16 | 17,8}
dulgerciSquareSequence[18]
No sequence found for n = 18
dulgerciSquareSequence[19]
No sequence found for n = 19
dulgerciSquareSequence[20]
No sequence found for n = 20
dulgerciSquareSequence[21]
No sequence found for n = 21
dulgerciSquareSequence[22]
No sequence found for n = 22
dulgerciSquareSequence[23]
{1,3,22,14,11,5,20,16,9,7,18 | 2,23,13,12,4,21,15,10,6,19,17,8}
{1,3,22,14,11,5,20,16,9 | 18,7,2,23,13,12,4,21,15,10,6,19,17,8}
{1,3,22 | 18,7,9,16,20,5,11,14,2,23,13,12,4,21,15,10,6,19,17,8}
dulgerciSquareSequence[24]
No sequence found for n = 24
dulgerciSquareSequence[25]
{1,3,22,14,11,25,24,12,13,23,2 | 18,7,9,16,20,5,4,21,15,10,6,19,17,8}
{1,24,25,11,5,20,16,9,7,18 | 3,22,14,2,23,13,12,4,21,15,10,6,19,17,8}
{1,3,22,14,2,23,13,12,24,25,11,5,20,16,9,7,18 | 4,21,15,10,6,19,17,8}
{1,3,22,14,2,23,13,12,4,21,15,10,6,19,17,8 | 18,7,9,16,20,5,11,25,24}
{1,3,22,14,11,25,24,12,13,23,2,7,18 | 9,16,20,5,4,21,15,10,6,19,17,8}
{1,8,17,19,6,3,22,14,2,23,13,12,4,21,15,10 | 18,7,9,16,20,5,11,25,24}
{1,3,22,14,2,23,13,12,24,25,11 | 18,7,9,16,20,5,4,21,15,10,6,19,17,8}
{1,3,22,14,2,23,13 | 18,7,9,16,20,5,11,25,24,12,4,21,15,10,6,19,17,8}
{1,3,13,23,2,14,22 | 18,7,9,16,20,5,11,25,24,12,4,21,15,10,6,19,17,8}
{1,8,17,19,6,10,15,21,4,12,13,3,22,14,2,23 | 18,7,9,16,20,5,11,25,24}
the 18 is the at one end of a sequence.
There are many solutions for 25 < n < 32. So experimentally the situation is clear (mod errors).