Solving Generalized Polyomino Puzzles Using the Ising Model.
Ontology highlight
ABSTRACT: In the polyomino puzzle, the aim is to fill a finite space using several polyomino pieces with no overlaps or blanks. Because it is an NP-complete combinatorial optimization problem, various probabilistic and approximated approaches have been applied to find solutions. Several previous studies embedded the polyomino puzzle in a QUBO problem, where the original objective function and constraints are transformed into the Hamiltonian function of the simulated Ising model. A solution to the puzzle is obtained by searching for a ground state of Hamiltonian by simulating the dynamics of the multiple-spin system. However, previous methods could solve only tiny polyomino puzzles considering a few combinations because their Hamiltonian designs were not efficient. We propose an improved Hamiltonian
SUBMITTER: Takabatake K
PROVIDER: S-EPMC8947422 | biostudies-literature | 2022 Feb
REPOSITORIES: biostudies-literature
ACCESS DATA