DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 18--------------------------------------------------
       exact cover problem
       By: gsgs Date: June 25, 2023, 4:00 am
       ---------------------------------------------------------
       you can convert a Hamiltonian Cycle problem to an exact cover
       problem,
       which would not be equivalent but gives all the Hamiltonian
       Cycles
       as solutions but also the partitions of the vertex-set with
       multiple
       disjoint cycles.
       As the set to be covered take S = V x {in,out} as universe
       and for each edge (u,v) in E take the two subsets
       {(u,out,(v,in)},{(v,out),(u,in)}
       this gives 2*|E| sets with two elements to cover S .
  HTML http://magictour.free.fr/adj2dlx.c
       You can use Knuth's "Dancing Links" to solve the
       exact cover problem and check which of the solutions
       correspond to Hamiltonian Cycles.
       (the 2017-improvement with ZDDs is here
  HTML https://www-cs-faculty.stanford.edu/~knuth/programs/dlx6.w)
       This discards the connectivity-pruning opportunitie
       and should be slower than specialized Hamiltonian Cycle Solvers,
       but still good to compare benchmarks
       for random cubic graphs this gives ...
       for the FHCP-challenge set ...
       ---------edit-------------
       well, this is probably very inefficient in general,
       only useful in some special cases that I tried,
       106172416 solutions for the 6x6 knight's graph , found in 10min.
       313600 solutions for the 5x6 knight's graph.
       Apparently it's this :
  HTML https://oeis.org/A263568
       > T(n,k)=Number of (n+2)X(k+2) arrays of permutations of
       > 0..(n+2)*(k+2)-1 with each element moved 0 or 1 knight moves
       > and no more than 1 element left unmoved.
       I don't understand this. I'd call it the number of partitions of
       the
       m*n knight's graph into (directed) cycles of lengths > 1.
       here the same for Wazir-graphs = grid-graphs :
  HTML https://oeis.org/A189245
       *****************************************************