denis_berthier wrote:Could you say a word about the two techniques, the main results and why you compare them only for the hardest instances?
Our technique is aimed at constraint satisfaction problems in general (but slightly more aimed at graph coloring problems). It is based on the belief propagation techniques found in https://arxiv.org/ftp/arxiv/papers/1212/1212.2463.pdf with some extra insights from sources such as https://ieeexplore.ieee.org/document/4454429, https://uol.de/f/5/inst/physik/ag/compphys/download/talks/heiko_bauke.pdf, http://www.ece.ualberta.ca/~madjid/Files/Publications/TR081231.pdf, https://research.ee.sun.ac.za/pgms/Resources/graphcoloring.pdf, combined with a form of sequential variable elimination https://en.wikipedia.org/wiki/Variable_elimination to ensure that the system will either always converge or blow up the memory for problems too hard (it wouldn't get "stuck" in a loop or converge to an incorrect result, it is proven to retain the solution space).
We compare this combined-family of techniques to previous Sudoku Attempts (we use their 2010 Gordon Royle 17-entry dataset for exact comparison), and also to the ACE system http://reasoning.cs.ucla.edu/ace/moreInformation.html as recommended by a previous review cycle. For our system and the ACE system, the much-referenced 17-entry set is too easy (from reading the Sudoku literature it seems like the general consensus stops at thinking that 17-entries is what is required of a Sudoku to be most-difficult, e.g. https://www.dcc.fc.up.pt/~acm/sudoku.pdf; which seems to be proven wrong by this Champagne set). With this said, we were looking for some nice, fairly-difficult but well-understood graph coloring problems to use as a comparison metric. We also used a ton of Killer Sudokus, Calcudokus, Kakuros and Fill-a-Pix for further colouring in our puzzle database.
Thanks for the reply, since there seems to be no other papers where Champagne is references, I'll go with your explanation (with maybe a reference to https://pdfs.semanticscholar.org/87cc/6591845d4023aeeec8121aa20f72dc4d32c7.pdf to show the Sudoku Explainer metric). I'll post the paper here after all is done, but it might not be that interesting to this thread, since there are better Sudoku-specific techniques out there.