2020-02-18T12:56:55Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000956932017-03-31T05:36:57Z05471:07004:07295
The Complexity of Tantrix Match Puzzles with Four ColorsThe Complexity of Tantrix Match Puzzles with Four Colorseng[Special Issue on Mathematics of Puzzles] puzzles, Tantrix, computational complexity, NP-completenesshttp://id.nii.ac.jp/1001/00095671/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=95693&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of JapanOsaka Electro-Communication UniversityOsaka Electro-Communication UniversityOsaka Electro-Communication UniversityAkihiro, UejimaFuhito, YanagitaniShohei, TsukamotoTantrix Match is a puzzle in which hexagonal tiles are arranged within a hexagonal lattice board in which there are some fixed tiles. Each tile has painted lines in three of four possible colors, and it is required that all lines that touch on adjacent tiles must match in color. The aim of this research is to determine the computational complexity of this puzzle, and we prove that the generalized Tantrix Match is NP-complete by reduction from the circuit-satisfiability problem (Circuit-SAT).Tantrix Match is a puzzle in which hexagonal tiles are arranged within a hexagonal lattice board in which there are some fixed tiles. Each tile has painted lines in three of four possible colors, and it is required that all lines that touch on adjacent tiles must match in color. The aim of this research is to determine the computational complexity of this puzzle, and we prove that the generalized Tantrix Match is NP-complete by reduction from the circuit-satisfiability problem (Circuit-SAT).AA00700121Journal of information processing2134054122013-07-151882-66522013-10-21