论文标题
1 x 1的高峰小时带固定块是pspace complete
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
论文作者
论文摘要
考虑$ n^2-1 $ $单位方块中的$ n \ times n $平板板，每个块都标记为可移动的（仅），垂直移动（仅）或不可移动 - 仅需$ 1 \ times $ 1 \ times 1 $ $的汽车和固定块。我们证明，通过从非确定的约束逻辑通过2彩色的地铁随机降低，确定给定块是否可以到达板的左边缘是Pspace complete。相比之下，多项式时间算法以决定是否可以通过一个空间移动或每个块不可移动或可以水平和垂直移动时而闻名。我们的结果通过Tromp和Cilibrasi回答了15年历史的开放问题，并通过垂直$ 1 \ times 2 $和水平$ 2 \ times 1 $移动块和4色的地铁造型增强了先前的PSPACE完整性结果。
Consider $n^2-1$ unit-square blocks in an $n \times n$ square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variation of Rush Hour with only $1 \times 1$ cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical $1 \times 2$ and horizontal $2 \times 1$ movable blocks and 4-color Subway Shuffle.
