International audience

Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fill a grid with numbers between 1 and 5 while respecting three simple constraints. We first prove the NP-completeness of Suguru puzzle. For this we design gadgets to encode the PLANAR-CIRCUIT-SAT in a Suguru grid. We then design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. This ZKP protocol allows a prover to prove that he knows a solution of a Suguru grid to a verifier without leaking any information on the solution. To construct such a physical ZKP protocol, we only rely on a few physical cards and adapted encoding. For a Suguru grid with n cells, we only use 5n+5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.

This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.

We study several generic tree search techniques applied to the Sequential Ordering Problem.This study enables us to propose a simple yet competitive tree search.It consists of an iterative beam search that favors search over inference and integrates prunings that are inspired by dynamic programming.The resulting method proves optimality on half of the SOPLIB instances, 10 to 100 times faster than other existing methods.Furthermore, it finds new best-known solutions on 6 among 7 open instances of the benchmark in a small amount of time.These results highlight that there is a category of problems (containing at least SOP) where an anytime tree search is extremely efficient (compared to classical meta-heuristics) but was underestimated.