Title :
Solving E-Squaro through SAT-Coding
Author :
Gregoire, Eric ; Hasni, Atef ; Mazure, Bertrand ; Piette, Cedric
Author_Institution :
Univ. Artois, Lens, France
Abstract :
In this paper, we show that the E-SquarO puzzle, which is an extension of the popular SquarO game, is NP-complete. We propose a SAT encoding of E-SquarO and investigate its practical computational properties.
Keywords :
computability; computational complexity; E-SquarO puzzle; NP-complete problems; SAT encoding; Artificial intelligence; Conferences; Distance measurement; Encoding; Games; Lenses; Polynomials; NP-complete problems; SAT solving; SquarO;
Conference_Titel :
Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on
Conference_Location :
Herndon, VA
Print_ISBN :
978-1-4799-2971-9
DOI :
10.1109/ICTAI.2013.145
