On A Generalization of "Eight Blocks to Madness" puzzle
On A Generalization of "Eight Blocks to Madness" puzzle
复制标题
论“疯狂八块”谜题的概括
DOI：
10.1016/j.disc.2015.12.014
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Kazuya Haraguchi
中科院分区：
文献类型：
--
作者：
Kazuya Haraguchi
我们考虑这样一个难题，一组彩色立方体作为一个例子。每个立方体的每一条边都有单位长度，并且它的表面被着色，这样我们就满足了所谓的表面颜色条件。给定一个六种颜色的调色板，该条件要求每个面都应该有一种颜色，并且所有面都应该有彼此不同的颜色。谜题要求从实例中的八个合适的立方体中组合一个满足表面颜色条件的2× 2× 2立方体。请注意，立方体和解决方案分别有30个品种。在本文中，我们给出了三个问题的答案的难题：（i）对于30个解决方案的每个子集，是否有一个实例，有一个子集正好是它的解决方案集？(ii)创建一个最大大小的不可行实例（即没有解决方案的实例）。(iii)创建一个最小大小的通用实例（即一个具有所有30个解决方案的实例）。我们在计算机搜索的帮助下解决了这些问题。对于（ii）和（iii），我们给出了所需实例的例子，它们的大小分别为23和12。的答案（ii）解决了一个开放的问题，提出了在Berkove等人。（2008年）。
We consider a puzzle such that a set of colored cubes is given as an instance. Each cube has unit length on each edge and its surface is colored so that what we call the Surface Color Condition is satisfied. Given a palette of six colors, the condition requires that each face should have exactly one color and all faces should have different colors from each other. The puzzle asks to compose a 2× 2× 2 cube that satisfies the Surface Color Condition from eight suitable cubes in the instance. Note that cubes and solutions have 30 varieties respectively. In this paper, we give answers to three problems on the puzzle:(i) For every subset of the 30 solutions, is there an instance that has the subset exactly as its solution set?(ii) Create a maximum sized infeasible instance (ie, one having no solution).(iii) Create a minimum sized universal instance (ie, one having all 30 solutions). We solve the problems with the help of a computer search. We show that the answer to (i) is no. For (ii) and (iii), we show examples of the required instances, where their sizes are 23 and 12, respectively. The answer to (ii) solves one of the open problems that were raised in Berkove et al.(2008).