A Simple QUBO Formulation of Sudoku

• URL: http://arxiv.org/abs/2403.04816v1
• Date: Thu, 7 Mar 2024 09:54:06 GMT
• Title: A Simple QUBO Formulation of Sudoku
• Authors: Sascha M\"ucke
• Abstract summary: This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO) 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• A QUBO Formulation for the Generalized Takuzu/LinkedIn Tango Game [49.1574468325115]
  We present a QUBO formulation for the Takuzu game ( Binaor Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We optimize the number of variables needed to solve the problem, making it suitable to be solved by quantum devices with fewer resources.
  arXiv  Detail & Related papers  (2024-10-13T13:49:56Z)
• A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game [49.1574468325115]
  We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game. We adapt this formulation for several particular cases of the problem, as Tents & Trees. We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.
  arXiv  Detail & Related papers  (2024-10-08T23:54:54Z)
• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  We develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization problems. With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets.
  arXiv  Detail & Related papers  (2024-09-09T11:29:46Z)
• Quantum Backtracking in Qrisp Applied to Sudoku Problems [0.52197339162908]
  We provide a detailed instruction on implementing the quantum step operator for arbitrary backtracking instances. For a single controlled diffuser of a binary backtracking tree with depth n, our implementation requires only $6n+14$ CX gates. This is the first instance of a compilable implementation of this generality, marking a significant and exciting step forward in quantum software engineering.
  arXiv  Detail & Related papers  (2024-02-15T16:29:44Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• TBA Equations and Quantization Conditions [0.0]
  We develop a graphical procedure due to Toledo to study the wall-crossing behavior of the TBA equations. We compute the quantum corrections to the all-order WKB periods in many examples. In particular, we show how this method can be used to determine resonances in potentials.
  arXiv  Detail & Related papers  (2020-08-31T15:42:01Z)
• SudoQ -- a quantum variant of the popular game [1.5229257192293197]
  We introduce SudoQ, a quantum version of the classical game Sudoku. The solution set of SudoQ puzzles can be much larger than in the classical (commutative) setting.
  arXiv  Detail & Related papers  (2020-05-21T19:19:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.