This algorithm written in Python solves at least a subset of the Hamilton Circuit problem, which is NP complete, in n^3 time.

[Martin]

This algorithm written in Python solves at least a subset of the
Hamilton Circuit problem, which is NP complete, in n^3 time.

#!/usr/bin/env python
#
#       hamiltoncircuit.python
#
#       Copyright 2011 Martin Musatov <musatov at att.net>
#
#       This program is free software; you may redistribute it and/or
modify
#       it under the terms of the GNU General Public License as
published by
#       the Free Software Foundation; either version 2 of the License,
or
#       (at your option) any later version.
#
#       This program is distributed in the hope it is useful,
#       but WITHOUT ANY WARRANTY; without even the implied warranty of
#       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#       GNU General Public License for more details.
#
#       You may obtain a copy of the GNU General Public License
#       with this program from the Free Software
#       Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
#       MA 02110-1301, USA.

  //  numnodes=10
  //
  //  import random
  //
  //  class allnodes():
  //      connect = []
  //      gridpos = []
  //      initpos = []
  //      def __init__(self, numnodes):
  //          for i in range(0, numnodes):
  //              self.gridpos.append(i)
  //              self.initpos.append(i)
  //              self.connect.append([])
  //
  //  nodes=allnodes(numnodes)
  //  def swapref(n, a, b):
  //      t = nodes.initpos[a]
  //      nodes.initpos[a] = nodes.initpos[b]
  //      nodes.initpos[b] = t
  //      for i in range(0, len(n)):
  //          for j in range(0, len(n[i])):
  //              if n[i][j] == a:
  //                  n[i][j] = b
  //              elif n[i][j] == b:
  //                  n[i][j] = a
  //      return n
  //  def makeswap(grida, gridb):
  //      ascore = 0
  //      aswapscore = 0
  //      bscore = 0
  //      bswapscore = 0
  //      if grida > 1 and grida < numnodes-1:
  //          for i in range(0, len(nodes.connect[grida])):
  //              if nodes.connect[grida][i] == grida - 2 or
nodes.connect[grida][i] == grida + 2:
  //                  ascore+=1
  //
  //      elif grida == 0:
  //          for i in range(0, len(nodes.connect[grida])):
  //              if nodes.connect[grida][i] == grida + 1 or
nodes.connect[grida][i] == grida + 2:
  //                  ascore+=1
  //      elif grida == 1:
  //          for i in range(0, len(nodes.connect[grida])):
  //              if nodes.connect[grida][i] == grida - 1 or
nodes.connect[grida][i] == grida + 2:
  //                  ascore+=1
  //      elif grida == numnodes:
  //          for i in range(0, len(nodes.connect[grida])):
  //              if nodes.connect[grida][i] == grida - 1 or
nodes.connect[grida][i] == grida - 2:
  //                  ascore+=1
  //      elif grida == numnodes-1:
  //          for i in range(0, len(nodes.connect[grida])):
  //              if nodes.connect[grida][i] == grida + 1 or
nodes.connect[grida][i] == grida - 2:
  //                  ascore+=1
  //      if gridb > 1 and gridb < numnodes-1:
  //          for i in range(0, len(nodes.connect[gridb])):
  //              if nodes.connect[gridb][i] == gridb - 2 or
nodes.connect[gridb][i] == gridb + 2:
  //                  bscore+=1
  //      elif gridb == 0:
  //          for i in range(0, len(nodes.connect[gridb])):
  //              if nodes.connect[gridb][i] == gridb + 1 or
nodes.connect[gridb][i] == gridb + 2:
  //                  bscore+=1
  //      elif gridb == 1:
  //          for i in range(0, len(nodes.connect[gridb])):
  //              if nodes.connect[gridb][i] == gridb - 1 or
nodes.connect[gridb][i] == gridb + 2:
  //                  bscore+=1
  //      elif gridb == numnodes:
  //          for i in range(0, len(nodes.connect[gridb])):
  //              if nodes.connect[gridb][i] == gridb - 1 or
nodes.connect[gridb][i] == gridb - 2:
  //                  bscore+=1
  //      elif gridb == numnodes-1:
  //          for i in range(0, len(nodes.connect[gridb])):
  //              if nodes.connect[gridb][i] == gridb + 1 or
nodes.connect[gridb][i] == gridb - 2:
  //                  bscore+=1
  //      tempnodes = []
  //      tempnodes.extend(nodes.connect)
  //      t = tempnodes[grida]
  //      tempnodes[grida]=tempnodes[gridb]
  //      tempnodes[gridb]=t
  //
  //      if grida > 1 and grida < numnodes-1:
  //          for i in range(0, len(tempnodes[grida])):
  //              if tempnodes[grida][i] == grida - 2 or
tempnodes[grida][i] == grida + 2:
  //                  aswapscore+=1
  //
  //      elif grida == 0:
  //          for i in range(0, len(tempnodes[grida])):
  //              if tempnodes[grida][i] == grida + 1 or
tempnodes[grida][i] == grida + 2:
  //                  aswapscore+=1
  //      elif grida == 1:
  //          for i in range(0, len(tempnodes[grida])):
  //              if tempnodes[grida][i] == grida - 1 or
tempnodes[grida][i] == grida + 2:
  //                  aswapscore+=1
  //      elif grida == numnodes:
  //          for i in range(0, len(tempnodes[grida])):
  //              if tempnodes[grida][i] == grida - 1 or
tempnodes[grida][i] == grida - 2:
  //                  aswapscore+=1
  //      elif grida == numnodes-1:
  //          for i in range(0, len(tempnodes[grida])):
  //              if tempnodes[grida][i] == grida + 1 or
tempnodes[grida][i] == grida - 2:
  //                  aswapscore+=1
  //      if gridb > 1 and gridb < numnodes-1:
  //          for i in range(0, len(tempnodes[gridb])):
  //              if tempnodes[gridb][i] == gridb - 2 or
tempnodes[gridb][i] == gridb + 2:
  //                  bswapscore+=1
  //      elif gridb == 0:
  //          for i in range(0, len(tempnodes[gridb])):
  //              if tempnodes[gridb][i] == gridb + 1 or
tempnodes[gridb][i] == gridb + 2:
  //                  bswapscore+=1
  //      elif gridb == 1:
  //          for i in range(0, len(tempnodes[gridb])):
  //              if tempnodes[gridb][i] == gridb - 1 or
tempnodes[gridb][i] == gridb + 2:
  //                  bswapscore+=1
  //      elif gridb == numnodes:
  //          for i in range(0, len(tempnodes[gridb])):
  //              if tempnodes[gridb][i] == gridb - 1 or
tempnodes[gridb][i] == gridb - 2:
  //                  bswapscore+=1
  //      elif gridb == numnodes-1:
  //          for i in range(0, len(tempnodes[gridb])):
  //              if tempnodes[gridb][i] == gridb + 1 or
tempnodes[gridb][i] == gridb - 2:
  //                  bswapscore+=1
  //
  //      if (ascore+bscore) < (aswapscore+bswapscore):
  //          return True
  //      else:
  //          return False
  //
  //  def gengraph(numnodes):
  //      connectedness = False
  //      connectfail = False
  //      while(connectedness == False):
  //          connectfail=False
  //          same = True
  //          while(same == True):
  //              m = random.randrange(0, numnodes)
  //              p = random.randrange(0, numnodes)
  //              if m != p:
  //                  check = False
  //                  for i in range(0, len(nodes.connect[m])):
  //                      if nodes.connect[m][i] == p:
  //                          check=True
  //                  if check==False:
  //                      same = False
  //                      nodes.connect[m].append(p)
  //                      nodes.connect[p].append(m)
  //          for i in range(0, numnodes):
  //              if len(nodes.connect[i]) < 2:
  //                  connectfail=True
  //          if connectfail == False:
  //              connectedness = True
  //  def swapall():
  //      cont = True
  //      foundswap=False
  //      while (cont == True):
  //          foundswap = False
  //          for i in range(0, numnodes-1):
  //              for j in range(i+1, numnodes):
  //                  if makeswap(i, j) == True:
  //                      foundswap = True
  //                      t = nodes.connect[i]
  //                      nodes.connect[i]=nodes.connect[j]
  //                      nodes.connect[j]=t
  //                      nodes.connect=swapref(nodes.connect, i, j)
  //                      break
  //              if foundswap==True:
  //                  break
  //          if foundswap == False:
  //              cont = False
  //  def pathify():
  //
  //      for i in range(0, numnodes-2, 2):
  //          check = False
  //          print(nodes.initpos[i])
  //          for j in range(0, len(nodes.connect[i])):
  //              if nodes.connect[i][j] == i+2:
  //                  check = True
  //                  print("-")
  //                  break
  //          if check == False :
  //              print("x")
  //      print(nodes.initpos[numnodes-2])
  //      check = False
  //      for j in range(0, len(nodes.connect[numnodes-2])):
  //          if nodes.connect[numnodes-2][j] == numnodes-1:
  //              check = True
  //              print(".")
  //              break
  //      if check == False:
  //          print("x")
  //
  //      for i in range(numnodes -1,1 , -2):
  //          check = False
  //          print(nodes.initpos[i])
  //          for j in range(0, len(nodes.connect[i])):
  //              if nodes.connect[i][j] == i-2:
  //                  check = True
  //                  print("-")
  //                  break
  //          if check == False:
  //              print("x")
  //      print(nodes.initpos[1])
  //      check = False
  //      for j in range(0, len(nodes.connect[1])):
  //          if nodes.connect[1][j] == 0:
  //              check = True
  //              print("-")
  //              break
  //      if check == False:
  //          print("x")
  //
  //
  //  def main():
  //      gengraph(numnodes)
  //
  //      for i in range(0, numnodes):
  //          print(nodes.initpos[i], nodes.connect[i])
  //      swapall()
  //      print("Best path")
  //      pathify()
  //
  //  main()