DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 13--------------------------------------------------
       Andrew Chalaturnyk's 2008 program
       By: gsgs Date: April 23, 2023, 1:20 am
       ---------------------------------------------------------
       is here :
  HTML https://github.com/aachalat/hamilton_cycle
       It's from his 2008 thesis
  HTML https://github.com/aachalat/hamilton_cycle/raw/master/chalaturnykthesis.pdf
       improving a program from William Kocay from 1998, which goes
       back
       to a program from Frank Rubin, 1975.
       "multipath-method"
       Apparently not the method with pathstructures and borders
       as in the 2015-Pettersson thesis.
       -----------------------------
       on page 88 he gives some benchmarks for knight graphs.
       Apparently using the same decomposition of the 8x8 into
       41790 subproblems as on my and Yann Denef's webpage !
       But without comment, without calculating all closed 8x8 tours.
       However it's ~10 times faster than my program.
       -------------------------------
       It is quite fast.
       But it has a "triangle problem", which may increase the running
       time a lot
       when all but one neighbors of a (small) cycle are included
       but none of the cycle vertices yet.
       This can't become Hamiltonian.
       Another problem is with forced edges : better replace them by
       one new vertex of degree 2 and edges to the endpoints.
       It often benefits from random restart, when some node-limit is
       exceeded,
       this may be due to the triangle-problem.
       It also benefits from initial resorting of the vertices
       for small border-size.
       With this reordering and random restarts after 100000 nodes,
       it solves 500 of the 1001 FHCP-challenge-graphs in ca. 5 hours
  HTML https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/fhcp-challenge-set/
       *****************************************************