Hamiltonian cycle taking too long

I have to find out if there is Hamiltonian cycle in a giant graph (1000 vertices in the smallest instance and 5000 vertices in the largest).

My initial idea was to do backtracking, and in small instances, it worked right. But for instance of 1000 vertices, I left 6 hours and no response.

My idea was to take a code from the ready traveling clerk (only found using array) and put the edges that exist with weight 1, and those that do not exist with weight 9.

If the result of the execution of the function gives the number of vertices, there is a Hamiltonian cycle.

If it does not, then there is no Hamiltonian cycle (as it had to use some edge of weight 9 to find the way).

For small instances, it continued to work, but with the 1000 Vertex instance, it also crashed.

Nobody in the class has the knowledge to do something that escapes much of the backtracking, therefore, it is assumed that we find some code already implemented on the internet. At most, we will have to make some small changes.

Does anyone have any traveling clerk or a code that would detect a Hamiltonian loop with adjacency list? Or instances up to 5000 in less than 3 hours?

Would someone try to help me by giving at least one hint?

Links with the codes and entries I used:

• Follow the link of the code I used (in C): http://ideone.com/qyEipK

• Instances I need to pass: https://www.dropbox.com/sh/50ij1m5w5b1mfca/AADzt3XsE9cVg6OlW6SDTygQa?dl=0

• Follow the link for an adjacency list: http://ideone.com/Ib9i0P

• Following is the link from a code I made to turn the adjacency list into an array file: http://ideone.com/7stdkJ

• Follows the link of a small matrix N=18 which contains a Hamiltonian cycle: http://ideone.com/M8PfTu

• Follows the link of a small matrix N = 18 that does not contain a Hamiltonian cycle: http://ideone.com/GBlyZ5