How to solve the travelling salesman problem using linear least squares? Do there exist any algorithms only using linear least squares to try and solve the travelling salesman problem? It somehow seems like such a hard problem it would not be possible to do...

No, because assuming $P \
eq NP$, TSP is not poly-time reducible to linear regression, because the former is $NP-HARD$ and the latter is in $P$.

If you drop the poly-time constraint, then you can make the reduction do all the work without needing to use the regression. In other words, you can make all the $y$ coordinates the same, encoding the solution to the problem.