Solving the Sudoku Puzzle using Quantum Annealing
Date Issued
September 6, 2023
Type
Πτυχιακή Εργασία
Abstract
This thesis focuses on studying the Sudoku puzzle on D-Wave quantum systems. We
have developed a new matrix formulation for the Sudoku problem, which allows
for easy integration of benchmark instances in quantum platforms. Our mathemat-
ical analysis determines the exact number of constraints needed to express Sudoku
puzzles as Ising and QUBO formulations. Additionally, we have created a technique
for generating QUBO models for Sudoku puzzles of different sizes. Our extensive
experiments show that the D-Wave Advantage_system6.2 can handle smaller Su-
doku instances, but larger ones are still not possible. Furthermore, our experi-
ments confirm that the D-Wave hybrid solvers always produce valid solutions with-
out violating the given constraints.
Subjects