DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 27--------------------------------------------------
       clingo
       By: gsgs Date: November 12, 2023, 4:42 am
       ---------------------------------------------------------
       easiest way to install clingo under ubuntu :
       sudo apt install clingo
       (with internet connection, during German business hours)
       clingo solved 934 of the 1001 fhcp graphs with 30 min per graph
       ,
       840 with 5min per graph :
  HTML http://magictour.free.fr/fhcp23.PNG
       on my laptop clingo solved 493 of the 1001 in 74000 sec.
       I'll try it on 8 threads with 3MHz and 64GB RAM later
       #Post#: 28--------------------------------------------------
       Re: clingo
       By: gsgs Date: November 12, 2023, 11:48 pm
       ---------------------------------------------------------
       the clingo syntax is hard for me to understand.
       I didn't find a good,short description yet.
       below some examples of ASP-programs using normal
       mathematical syntax.
       Now, is there a program which converts these to clingo
       or directly creates SAT-instances from it ?
       --------------------------------------
       n-queens
       {S<=JnxJn| fa x in Jn |{y in Jn : (x,y) in S}|=1}
       /\
       {S<=JnxJn| fa x in Jn |{y in Jn : (y,x) in S}|=1}
       /\
       {S<=JnxJn| fa x in Jn |{y in Jn : (y,x-1+y) in S|<2}
       /\
       {S<=JnxJn| fa x in Jn |{y in Jn : (x-1+y,y) in S|<2}
       ---------------------------------------------
       Hamiltonian cycle in a simple,undirected graph
       given V,E
       for v in V let N{v) be the set of all edges reaching v
       HC := {H<=E : fa v in V : |N(v)/\H|=2 }
       /\
       {H<=E : fa H_<H ti v in V : |N(v)/\H_|>0 and
       |N(v)/\(H-H_)|>0}
       --------------------------------------------
       // sets corresponding to Hamiltonian cycles in a xor9-graph
       given S={0..k-1} [k stations] , let V=Sx{0,1,2,3} [4*k
       track-switches]
       given E<=VxV , such that fa (s0,i0),(s1,i1) in E : s0!=s1
       [out-station-rail-connections]
       let N(v) , v=0..4*k-1 be the sets of all edges adjacent to v [
       multi-end-targets of switches ]
       the set of all cycle-coverings is =
       {H<=E | ti P:S-->{0,1} fa s in S fa i in {0..3}:
       |N(4s+2P(s)+i)/\H| = i/2 }
       [i/2=track/terminal number in the station, here every station
       has 2 terminals ]
       the set of all Hamiltonian cycles is
       {H<=E | ti P:S-->{0,1} fa s in S fa i in {0..3}:
       |N(4s+2P(s)+i)/\H| = i/2 }
       /\
       {H<=E | fa H_<H ti s in V :
       |N(4s)/\H_|+|N(4s+1)/\H|+|N(4s+2)/\H_|+|N(4s+3)/\H=2 }
       #Post#: 39--------------------------------------------------
       Re: clingo
       By: gsgs Date: September 8, 2025, 8:44 am
       ---------------------------------------------------------
       here is a recent paper to describe the Hamiltonian Cycle
       algorithm used by clingo.
       This is IMO the best program currently, to determine
       whether a graph is Hamiltonian or not.
       For most of the practically occuring hard problems, but not for
       the x9s.
       Well, also except for graphs of low treewidths which can quickly
       be solved with special programs for such graphs.
  HTML https://drops.dagstuhl.de/storage/00lipics/lipics-vol341-sat2025/LIPIcs.SAT.2025.24/LIPIcs.SAT.2025.24.pdf
       *****************************************************