A QUBO Formulation for the Generalized Takuzu/LinkedIn Tango Game

• URL: http://arxiv.org/abs/2501.00002v2
• Date: Sun, 09 Feb 2025 17:58:33 GMT
• Title: A QUBO Formulation for the Generalized Takuzu/LinkedIn Tango Game
• Authors: Alejandro Mata Ali, Edgar Mencia,
• Abstract summary: 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.
• Score: 49.1574468325115
• License:
• Abstract: In this paper we present a QUBO formulation for the Takuzu game (or Binairo), for the most recent LinkedIn game, Tango, and for its generalizations. We optimize the number of variables needed to solve the combinatorial problem, making it suitable to be solved by quantum devices with fewer resources.

Related papers

• 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)
• Sinkhorn algorithms and linear programming solvers for optimal partial transport problems [1.8130068086063336]
  We introduce what we term generalized optimal partial transport'' problems. We then discuss the dual formulation of these problems and the associated Sinkhorn solver.
  arXiv  Detail & Related papers  (2024-07-09T01:08:21Z)
• A Simple QUBO Formulation of Sudoku [0.0]
  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.
  arXiv  Detail & Related papers  (2024-03-07T09:54:06Z)
• Open Ad Hoc Teamwork with Cooperative Game Theory [28.605478081031215]
  Ad hoc teamwork poses a challenging problem, requiring the design of an agent to collaborate with teammates without prior coordination or joint training. One promising solution is leveraging the generalizability of graph neural networks to handle an unrestricted number of agents. We propose a novel algorithm named CIAO, based on the game's framework, with additional provable implementation tricks that can facilitate learning.
  arXiv  Detail & Related papers  (2024-02-23T11:04:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A Variational Inequality Approach to Bayesian Regression Games [90.79402153164587]
  We prove the existence of the uniqueness of a class of convex and generalize it to smooth cost functions. We provide two simple algorithms of solving them with necessarily strong convergence.
  arXiv  Detail & Related papers  (2021-03-24T22:33:11Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• 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)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)

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.