Synthesis takes two inputs: constraints and code. The first step is to determine which is the problem.
If you have existing constraints then try removing them all (leaving only the chosen part that you want) and just let Quartus synthesize the design. If it routes, then you should start to suspect the constraints that you removed.
If the problem is not existing constraints, then the problem must be with your code. First thing would be to locate which logic is being implemented at the locations of high interconnect using the netlist viewer and track that back to at least a general area of your code. Once you have that you'll have to put your thinking cap on to see if there is another way to implement your function. Using the netlist viewer to get an idea of how your code is translated into actual hardware might help but expect that it could be a tedious task until you get to the 'ah ha' moment.
Trying to leap to a solution such as wanting to put more distance between used LUTs is pointless if you don't understand the root cause problem. In addition to the informational message that you posted, there must have been some actual error message when the routing failed. There is possibly a clue in there.
Kevin Jennings