论文标题
所有路径通向罗马
All Paths Lead to Rome
论文作者
论文摘要
所有的道路通向罗马是益智游戏罗马的核心思想。它是在由二次细胞组成的$ n \ times n $网格上播放的。将这些单元格分为最多四个相邻单元的盒子，要么被填充，要么被填充，并用指向基本方向的箭头。游戏的目的是用箭头填充空单元格，以便每个框最多都包含每个方向的一个箭头，无论我们从哪里开始，如果我们遵循单元格中的箭头，我们将始终进入特殊的Roma-cell。在这项工作中，我们研究了益智游戏的计算复杂性，并表明，根据规则完成Roma板是一项\ np完成的任务，计数有效完成的数量是＃PTIME-COMPLETE，并且确定使实例\ emph {onireply}可溶解}可溶解的预设箭头的数量是$ $σ_2^p $ -comcomple。我们进一步表明，在ETH下，无法在$ n \ times n $板上完成给定的ROMA实例的问题$ \ Mathcal {O} \ left（2^{{o}（n）} \ right）$，并根据Catalan结构的概念提供匹配的动态编程算法。
All roads lead to Rome is the core idea of the puzzle game Roma. It is played on an $n \times n$ grid consisting of quadratic cells. Those cells are grouped into boxes of at most four neighboring cells and are either filled, or to be filled, with arrows pointing in cardinal directions. The goal of the game is to fill the empty cells with arrows such that each box contains at most one arrow of each direction and regardless where we start, if we follow the arrows in the cells, we will always end up in the special Roma-cell. In this work, we study the computational complexity of the puzzle game Roma and show that completing a Roma board according to the rules is an \NP-complete task, counting the number of valid completions is #Ptime-complete, and determining the number of preset arrows needed to make the instance \emph{uniquely} solvable is $Σ_2^P$-complete. We further show that the problem of completing a given Roma instance on an $n\times n$ board cannot be solved in time $\mathcal{O}\left(2^{{o}(n)}\right)$ under ETH and give a matching dynamic programming algorithm based on the idea of Catalan structures.
