pith. sign in

arxiv: 2410.06429 · v3 · submitted 2024-10-08 · 🪐 quant-ph · cs.ET· physics.pop-ph

A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game

Alejandro Mata Ali , Edgar Mencia This is my paper

Pith reviewed 2026-05-23 19:10 UTC · model grok-4.3

classification 🪐 quant-ph cs.ETphysics.pop-ph
keywords QUBOquantum annealingQAOAN-queensTakuzuTangocombinatorial optimizationlogic puzzles
0
0 comments X

The pith

QUBO formulations encode LinkedIn Queens, Takuzu, and Tango puzzles for solution on quantum hardware.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs QUBO models that turn generalizations of the LinkedIn Queens game, Takuzu, and Tango into quadratic unconstrained binary optimization problems. These models are adapted to specific cases such as Tents and Trees while reducing variable count and interactions. Two new puzzle variants, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, receive their own QUBO encodings. The work targets practical use with quantum annealing or QAOA by keeping the instances small enough for current devices.

Core claim

We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game, a version of the N-queens problem, for the Takuzu game (or Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We adapt this formulation for several particular cases of the problem, as Tents & Trees, by trying to optimise the number of variables and interactions, improving the possibility of applying it on quantum hardware by means of Quantum Annealing or the Quantum Approximated Optimization Algorithm (QAOA). We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations

What carries the argument

The QUBO formulation that encodes puzzle constraints as a quadratic unconstrained binary optimization problem with minimized variables and interactions.

If this is right

  • The same encoding applies directly to Tents and Trees puzzles.
  • The Coloured Chess Piece Problem and Max Chess Pieces Problem become solvable by the same quantum methods.
  • Reduced variable counts make larger grid sizes potentially accessible on near-term hardware.
  • The approach supplies a template for turning other placement or balance constraints into QUBO form.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar QUBO reductions could map other single-player logic puzzles such as Sudoku variants onto quantum solvers.
  • If the variable-optimization step generalizes, it may shorten the path from classical puzzle rules to quantum-ready Hamiltonians for broader combinatorial tasks.
  • Performance on these games could serve as a benchmark suite for comparing QAOA circuit depth against classical solvers on constraint problems.

Load-bearing premise

The constructed QUBO instances will have sufficiently few variables and interactions to be practically solvable on current quantum annealing or QAOA hardware.

What would settle it

Solve a concrete 5-by-5 Tango instance with the published QUBO on a quantum annealer and verify whether every returned bit string satisfies the row and column balance rules.

Figures

Figures reproduced from arXiv: 2410.06429 by Alejandro Mata Ali, Edgar Mencia.

Figure 1
Figure 1. Figure 1: Constraints on a 5 × 5 problem, such that no queens can be placed in any of the cells marked in red. a) Column constraint, b) Row constraint, c) Diag￾onal constraint on N-queens, d) Diagonal constraint on LQueens, e) Region constraint. • Rows condition: there can only be one queen per row ( [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: a) Solution of an 8-queen problem, b) Solution [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: a) Irregular shaped board. b) Regular board [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Toroidal board with a queen, where we mark [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: a) Solution of a rectangular Coloured Chess [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Solution for a problem a) Takuzu/0h h1 6×6, b) Tango • There are cells between which there is an ’=’ symbol, which indicates that in both cells there must be the same icon. • There are cells between which there is an ’x’ symbol, which indicates that there must be a different icon in both cells. A solution to this problem can be seen in [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Boards with restrictions. The blue cells have [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Generalized cases. a) Takuzu with colored [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
read the original abstract

In this paper, we present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game, a version of the N-queens problem, for the Takuzu game (or Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We adapt this formulation for several particular cases of the problem, as Tents \& Trees, by trying to optimise the number of variables and interactions, improving the possibility of applying it on quantum hardware by means of Quantum Annealing or the Quantum Approximated Optimization Algorithm (QAOA). We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper presents QUBO formulations for generalizations of the LinkedIn Queens game (an N-queens variant), the Takuzu (Binairo) and Tango games and their generalizations, as well as Tents & Trees. It introduces two new problems—the Coloured Chess Piece Problem and the Max Chess Pieces Problem—along with corresponding QUBO encodings, with explicit efforts to minimize the number of variables and interactions to improve applicability on quantum annealing or QAOA hardware.

Significance. If the encodings are shown to be correct, the work supplies compact, hardware-oriented QUBO mappings for a family of logic and placement puzzles, which could serve as benchmarks or test cases for quantum optimization algorithms. The variable-count optimizations and the new problem variants are concrete contributions to the catalog of QUBO-representable combinatorial tasks.

major comments (1)
  1. [Abstract and formulation sections] The central claim requires that every valid board configuration is a ground state of the constructed QUBO and every invalid configuration has strictly higher energy. The manuscript presents the penalty terms and reports variable counts but supplies neither a formal proof that the penalties are sufficient nor an exhaustive check on small instances (e.g., 4-queens or 4×4 Takuzu) confirming that the minimum-energy assignments coincide exactly with the legal solutions.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and for highlighting the need for explicit verification of the QUBO encodings. We address the single major comment below and will revise the manuscript to incorporate additional checks.

read point-by-point responses

  1. Referee: [Abstract and formulation sections] The central claim requires that every valid board configuration is a ground state of the constructed QUBO and every invalid configuration has strictly higher energy. The manuscript presents the penalty terms and reports variable counts but supplies neither a formal proof that the penalties are sufficient nor an exhaustive check on small instances (e.g., 4-queens or 4×4 Takuzu) confirming that the minimum-energy assignments coincide exactly with the legal solutions.

    Authors: We agree that a formal proof of correctness for the penalty terms and an explicit verification on small instances would strengthen the central claim. The manuscript derives the QUBO penalties by standard one-hot and pairwise constraint encodings and states that they enforce the rules, but does not include a mathematical proof that the combined Hamiltonian has the desired ground-state property or an exhaustive enumeration for small boards. In the revised version we will add a new appendix containing (i) a brief argument showing that each individual penalty term is zero precisely on the allowed configurations and strictly positive otherwise, and (ii) exhaustive numerical checks for the 4-queens and 4×4 Takuzu cases (enumerating all 2^{N^2} assignments or using an exact solver) confirming that the minimum-energy states coincide exactly with the legal solutions. These additions will be referenced from the formulation sections. revision: yes

Circularity Check

0 steps flagged

Direct QUBO construction from game rules with no self-referential reductions.

full rationale

The paper constructs QUBO penalty terms directly from the stated rules of the generalized queens, Takuzu, Tango and related problems. No parameters are fitted on a data subset and then called predictions; no self-citations supply uniqueness theorems or load-bearing premises; the mapping from constraints to quadratic interactions is presented as an explicit ansatz without prior-work smuggling. The central claim therefore remains externally checkable by verifying that the constructed Hamiltonians have ground states exactly at the valid boards, and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The formulations rest on the standard assumption that any constraint satisfaction problem can be encoded as a QUBO; no free parameters, new physical entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Any set of logical constraints on binary variables can be represented by a quadratic cost function whose minimum encodes valid solutions.
    This is the foundational premise of all QUBO mappings for combinatorial problems and is invoked implicitly when the authors state they have produced QUBO formulations.

pith-pipeline@v0.9.0 · 5654 in / 1247 out tokens · 24822 ms · 2026-05-23T19:10:20.732246+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

    cs.ET 2025-03 unverdicted novelty 3.0

    The paper reviews QUDO, T-QUDO and HOBO formulations, provides explicit encodings between them, discusses limitations, and gives examples for knapsack, TSP and games including N-Queens and Peg Solitaire.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · cited by 1 Pith paper

  1. [1]

    The n-queens problem, 2021

    Candida Bowtell and Peter Keevash. The n-queens problem, 2021. URL https:// arxiv.org/abs/2109.08083

    work page arXiv 2021

  2. [2]

    Agent having quan- tum properties: The superposition states and the entanglement

    Alain-Jérôme Fougères. Agent having quan- tum properties: The superposition states and the entanglement. In Ngoc Thanh Nguyen, George A. Papadopoulos, Piotr Ję- drzejowicz, BogdanTrawiński, andGottfried Vossen, editors, Computational Collective Intelligence, pages 389–398, Cham, 2017. Springer International Publishing. ISBN 978-3-319-67074-4

    work page 2017

  3. [3]

    Balagbis and Orven E

    Rachel Anne B. Balagbis and Orven E. Llantos. Solving the binary puzzle with ge- netic algorithm.Procedia Computer Science, 234:954–961, 2024. ISSN 1877-0509. DOI: https://doi.org/10.1016/j.procs.2024.03.084. URL https://www.sciencedirect. com/science/article/pii/ S1877050924004423. Seventh Informa- tion Systems International Conference (ISICO 2023)

    work page doi:10.1016/j.procs.2024.03.084 2024

  4. [4]

    Chakrabarti

    Atanu Rajak, Sei Suzuki, Amit Dutta, and Bikas K. Chakrabarti. Quantum anneal- ing: an overview. Philosophical Transac- tions of the Royal Society A: Mathemati- cal, Physical and Engineering Sciences , 381 (2241), December 2022. ISSN 1471-2962. DOI: 10.1098/rsta.2021.0417. URL http: //dx.doi.org/10.1098/rsta.2021.0417

    work page doi:10.1098/rsta.2021.0417 2022

  5. [5]

    Figueroa

    Sheir Yarkoni, Elena Raponi, Thomas Bäck, and Sebastian Schmitt. Quantum anneal- ing for industry applications: introduc- tion and review. Reports on Progress in Physics, 85(10):104001, September 2022. ISSN 1361-6633. DOI: 10.1088/1361- 6633/ac8c54. URL http://dx.doi.org/ 10.1088/1361-6633/ac8c54

    work page doi:10.1088/1361- 2022

  6. [6]

    A quantum approximate opti- mization algorithm, 2014

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate opti- mization algorithm, 2014

    work page 2014

  7. [7]

    A tutorial on formulating and us- ing qubo models, 2019

    Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and us- ing qubo models, 2019

    work page 2019

  8. [8]

    A simple qubo formula- tion of sudoku

    Sascha Mücke. A simple qubo formula- tion of sudoku. In Proceedings of the Ge- netic and Evolutionary Computation Con- ference Companion, GECCO ’24 Compan- ion, page 1958–1962, New York, NY, USA, 2024. Association for Computing Ma- chinery. ISBN 9798400704956. DOI: 10.1145/3638530.3664106. URL https:// doi.org/10.1145/3638530.3664106

    work page doi:10.1145/3638530.3664106 1958

  9. [9]

    A quan- tum n-queens solver

    Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner. A quan- tum n-queens solver. Quantum, 3:149, June

    work page

  10. [10]

    Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware,

    ISSN 2521-327X. DOI: 10.22331/q- 2019-06-03-149. URL http://dx.doi.org/ 10.22331/q-2019-06-03-149

    work page doi:10.22331/q- 2019

  11. [11]

    Panigrahi

    Santhosh G S, Piyush Joshi, Ayan Barui, and Prasanta K. Panigrahi. A quan- tum approach to solve n-queens problem, Accepted in Quantum 9999-99-99, click title to verify. Published under CC-BY 4.0. 15

    work page

  12. [12]

    URLhttps://arxiv.org/abs/2312. 16312

    work page

  13. [13]

    Solving the n-queens puzzle by a qubo model with quadratic size

    Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito, Takashi Yazane, Junko Yano, Takumi Kato, ShiroOzaki, RieMori, andRyotaKat- suki. Solving the n-queens puzzle by a qubo model with quadratic size. In2023 Eleventh International Symposium on Computing and Networking (CANDAR), pages 59–67, 2023. DOI: 10.1109/CANDAR60563.2023.00015

    work page doi:10.1109/candar60563.2023.00015 2023

  14. [14]

    Encoding the at-most- one constraint for qubo and quantum an- nealing: Experiments with the n-queens problem

    Philippe Codognet. Encoding the at-most- one constraint for qubo and quantum an- nealing: Experiments with the n-queens problem. In Proceedings of the Com- panion Conference on Genetic and Evolu- tionary Computation , GECCO ’23 Com- panion, page 2195–2202, New York, NY, USA, 2023. Association for Computing Ma- chinery. ISBN 9798400701207. DOI: 10.1145/358...

    work page doi:10.1145/3583133.3596394 2023

  15. [15]

    de Leceta

    Iñigo Perez Delgado, Beatriz García Markaida, Alejandro Mata Ali, and Aitor Moreno Fdez. de Leceta. Qubit num- ber optimization for restriction terms of qubo hamiltonians, 2023. URL https://arxiv.org/abs/2306.06943

    work page arXiv 2023

  16. [16]

    Lov K. Grover. A fast quantum mechan- ical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Comput- ing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Comput- ing Machinery. ISBN 0897917855. DOI: 10.1145/237814.237866. URL https:// doi.org/10.1145/237814.237866. Accepted in Quantum 999...

    work page doi:10.1145/237814.237866 1996