Learning sudoku by doing gradient descent on a linear program (mxkopy.github.io)

Researchers reimplemented OptNet-style differentiable optimization with cvxpy/cvxpylayers to train a model that “learns” Sudoku by placing a linear program as a neural-network layer. The board is one-hot encoded as a 9×9×9 boolean tensor and the solver enforces standard Sudoku constraints (each digit appears once per row, column, cell and 3×3 block). Given incomplete clues as a cvxpy Parameter, the LP objective minimizes sum_squares(board − clues) so the solver returns the closest valid completion. The notebook demonstrates exact solving, uses the LP to search for counterexamples (e.g., showing diagonals can have ≥3 distinct digits), and constructs puzzles uniquely determined by small hint sets via additional combinatorial constraints (e.g., forcing a cell to have 8 neighbors fixes it). This work highlights a practical, technical bridge between constraint programming and deep learning: cvxpylayers plus PyTorch lets you backpropagate through the argmin of an LP (OptNet/KKT-based differentiation) so you can learn constraint parameters end-to-end. Key implementation notes: the one-hot 729-variable encoding, objective = sum_squares(board − input), and using boolean CVX variables. A brute-force dense parameterization would be a 729×729 matrix (~531k elements) which cvxpy struggled to compile, so the author parallelized/split the workload across multiple LP layers and added trainable masks/parameters in PyTorch. The result shows differentiable optimization can embed exact logical structure into learned models, but solver-scaling and compiler limits remain practical hurdles for larger combinatorial domains.