BoxPush· 고급

게임 목표

모든 상자를 목표 지점(점선 사각형)에 밀어 넣으세요.

규칙

  • 상자는 밀기만 가능합니다. 당길 수 없습니다.
  • 한 번에 상자 하나만 밀 수 있습니다.
  • 벽이나 다른 상자에 막히면 이동할 수 없습니다.
  • 상자가 코너에 끼면 되돌리기가 필요합니다.
  • 상자를 코너로 밀지 마세요. 빠져나올 수 없습니다.
  • 목표에서 가까운 상자부터 배치하세요.
  • Undo를 적극 활용하세요. 무제한입니다.

이 퍼즐은 PSPACE-complete 문제로, 계획 수립(planning)과 공간 추론(spatial reasoning) 능력을 동시에 요구합니다.

  • Culberson, J. (1997). "Sokoban is PSPACE-complete." Fun with Algorithms.
  • Dor, D. & Zwick, U. (1999). "Sokoban and other motion planning problems." Computational Geometry.