A Simple QUBO Formulation of Sudoku
Author:
Open Access
- 14 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1958-1962
Abstract
This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO). To this end, a QUBO instance with 729 variables is constructed, encoding a Sudoku grid with all constraints in place, which is then partially assigned to account for clues. The resulting instance can be solved with a Quantum Annealer, or any other strategy, to obtain the fully filled-out Sudoku grid. Moreover, as all valid solutions have the same energy, the QUBO instance can be used to sample uniformly from the space of valid Sudoku grids. We demonstrate the described method using both a heuristic solver and a Quantum Annealer.Keywords
All Related Versions
Funding Information
- Bundesministerium für Forschung, Technologie und Raumfahrt (LAMARR24B)
This publication has 14 references indexed in Scilit:
- Optimal Flight-Gate Assignment on a Digital Quantum ComputerPhysical Review Applied, 2023
- Towards Bundle Adjustment for Satellite Imaging via Quantum Machine Learning2022
- On the challenges of using D-Wave computers to sample Boltzmann Random Variables2022
- Adiabatic Quantum Computing for Max-Sum Diversification2020
- Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problemsEuropean Journal of Operational Research, 2018
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set EnumerationExperimental Mathematics, 2014
- Using the unconstrained quadratic program to model and solve Max 2-SAT problemsInternational Journal of Operational Research, 2005
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Applications of pseudo-Boolean methods to economic problemsTheory and Decision, 1971