A Simple QUBO Formulation of Sudoku
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.
- Veröffentlicht in:
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion - Typ:
Inproceedings - Autoren:
Mücke, Sascha - Jahr:
2024 - Source:
https://dl.acm.org/doi/10.1145/3638530.3664106
Informationen zur Zitierung
Mücke, Sascha: A Simple QUBO Formulation of Sudoku, GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 2024, https://dl.acm.org/doi/10.1145/3638530.3664106, Muecke.2024a,
@Inproceedings{Muecke.2024a,
author={Mücke, Sascha},
title={A Simple QUBO Formulation of Sudoku},
booktitle={GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion},
url={https://dl.acm.org/doi/10.1145/3638530.3664106},
year={2024},
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...}}
