Data-Efficient Learning for Constraint Satisfaction Problems via Relational Biases and Hard Axiom Clamping

Constraint satisfaction problems (CSPs) serve as critical benchmarks for neural algorithmic reasoning, requiring accurate multi-step constraint propagation to determine variable values that satisfy all specified constraints. Existing neural solvers often rely on extensive training datasets, struggle with distribution shifts, or allow fixed clues to drift in continuous spaces. We introduce CSP-RSB, a data-efficient recurrent Transformer that directly incorporates constraint topology into the attention mechanism through a learnable relational bias. Additionally, we propose a hard axiom clamping strategy that fixes clues after each recurrence constraint projection and uses the QK-Norm to stabilize a two-layer block. In 9 \times 9 Sudoku, CSP-RSB achieves 99.94\% board accuracy on the RRN-test, 99.13\% on unfiltered Kaggle, and 99.78\% on filtered Kaggle, surpassing the previous best, Trial & Error 2025, which reported accuracies of 99.40\%, 98.90\%, and 99.50\%, respectively. Furthermore, it successfully solves Erd\H{o}s--R\'enyi graph coloring with 100\% accuracy in 9 epochs and maintains 99.5-100\% accuracy on 10 \times 10 binary puzzles. By incorporating explicit topological structure, CSP-RSB reduces the need for depth and data requirements for effective algorithmic reasoning.