On a generalization of “Eight Blocks to Madness” puzzle

详细信息    查看全文

• 作者：Kazuya Haraguchi ^{haraguchi@res.otaru-uc.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Combinatorial puzzle ; MacMahon&rsquo ; s colored cube puzzle ; Eight Blocks to Madness ; Computer-assisted proof
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 April 2016
• 年：2016
• 卷：339
• 期：4
• 页码：1400-1409
• 全文大小：496 K

文摘

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$2\times 2\times 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 (i.e., one having no solution). (iii) Create a minimum sized universal instance (i.e., 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).