HONet: Data-Efficient Learning for Exact Cover Tasks via Hypergraph Optimization

Deep learning approaches typically require prohibitive amounts of data to approximate known-constraint Exact Cover tasks, while existing neuro-symbolic methods often face training infeasibility and scalability bottlenecks. To bridge this divide, we propose the Hypergraph Optimization Network (HONet), an end-to-end framework integrating a structure-preserving Deep Residual Hypergraph Encoder with a differentiable fixed-constraint Quadratic Programming layer. By adopting a ``Fixed Polytope'' paradigm guided by the Geometric Consistency Loss, HONet explicitly shapes the objective landscape, encouraging the valid discrete solution to align with the global energy minimum. Empirical results show that HONet rapidly achieves 100\% accuracy on $9 \times 9$ Sudoku using limited samples, exhibiting superior data efficiency over baselines while maintaining exceptional robustness in highly sparse regimes and additional tasks.

Many problems require a computer to choose answers that satisfy strict rules, such as filling a Sudoku board without breaking row, column, or box constraints. In this type of problem, the rule structure is not only known in advance, but also fixed across examples; what changes from one puzzle to another are the clues or observations. Standard deep learning methods may still spend many examples learning patterns that reflect these fixed rules, which can make learning data-hungry. We introduce HONet, a learning system that separates the fixed rules of the problem from the information that must be learned from each example. Instead of asking the neural network to rediscover the rules, HONet uses a fixed rule-based optimization layer and trains the network to guide this layer toward the correct solution. This makes learning more data-efficient because the model can focus on choosing among rule-satisfying candidates. On Sudoku benchmarks, HONet reaches perfect accuracy with a small training set and remains robust when clues are very sparse. We also test it on image-based Sudoku and a related puzzle with extra inequality rules, showing both the usefulness of this division of labor and its current limits.