Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$?
Long question:
Edit: This question is not about p = np. I am searching for a way to calculate the numbers of Self-avoiding circuit paths in TSP. It's not a typical Self-avoiding circuit but it have my own definition, I call it: non-intersecting path, and it's defined by my pseudo code that is use both for Euclidean and not Euclidean graphs.
I am trying to solve Hamiltonian Circuit Problem (HCP) by converting it to TSP, then finding non-intersecting paths (see my definition on the bottom of the page). Then keeping the path with the shortest weight, randomly ruined it by swapping random vertices along the path(I am storing the path in array and randomly swapping indexes), then fix it by converting it to non-interacting path again, and doing this again until I solve the HCP(I gave the wight 1 to all the edges that I got and weight 2 for all the rest when converting to TSP, so when I find a route where all the weights are 1 I know that I found the solution).
Using this method I been able to solve HCP passels with 300 vertexes and around 800 edges. I suspect that the reason that I been able to do that, is that the number of non-intersecting paths is very small. So I did a test, I created a brute force program and test it on inputs of 20 cities, I found that there wasn't any input(from my random generations) with more than 300 non-intersecting paths. This "evidence" makes me very optimistic about my suspicious that the number of non-intersecting paths in compare to number of vertices is not big, how ever a proof is required.
So please help me to find a proof for whether my suspicious is true or not.
non-intersecting path: In Euclidean graph where each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that TSP solution cannot have any interactions. And I used this code to convert any given path to non-interacting path
Read input into cities array
do
iterate over cities from i = 0
iterate over cities from j = i
if swapIfBetter(i, j) then set swapFound to true
while not swapFound
function swapIfBetter(index1, index2)
if index1 equals 0 and index2 equals cities size - 1
return false
initialize cities a,b,c,d
set a to cities at index index1
set b to cities at index (index1 - 1) unless index1 equals 0 in that case set it to (cities size - 1)
set c to cities at index index2
set d to cities at index (index2 + 1) unless index2 equals (cities size - 1) in that case set it to 0
initialize currentDistance1 to distance between a and b
initialize currentDistance2 to distance between c and d
initialize newDistance1 to distance between b and c
initialize newDistance2 to distance between a and d
if currentDistance1 + currentDistance2 < newDistance1 + newDistance2
swap(index1, index2)
return true
end if
return false
end function swapIfBetter
function swap(i, j):
while i < j:
cities[i], cities[j] = cities[j], cities[i]
i += 1
j -= 1
end loop
end function swap
*the swap function is taken from my other question here, created by Yuval Filmus.
The most interesting thing is when I used this code on not Euclidean graph it also worked. So I define non-interacting path, by path that been converted this way.