텐타이쇼

Tentai Show
풀리지 않은 텐타이쇼 퍼즐.
똑같은 퍼즐이 풀렸어요.그 지역들은 고양이의 사진을 보여주기 위해 색을 입혔다.

텐타이쇼(天臺),)는 니콜리가 [1]출판한 2진 결정 논리 퍼즐이다.

규칙.

텐타이쇼는 직사각형의 정사각형 격자 위에서 진행된다.그리드에는 별을 나타내는 점이 있으며, 셀의 중심, 가장자리 또는 모서리에 있는 그리드에서 찾을 수 있습니다.

퍼즐의 목적은 파선을 따라 선을 그려 그리드를 은하를 나타내는 영역으로 나누는 것입니다.

결과 그리드에서 모든 은하는 180° 회전 대칭을 가져야 하며 중심에 정확히 하나의 점이 있어야 합니다.

점의 색상은 퍼즐의 논리에 영향을 주지 않으며 풀 때 무시할 수 있습니다.복수의 색상의 도트가 있는 퍼즐에서는, 완성된 그리드의 영역을 대응하는 도트색으로 채색해 [2]화상을 나타내도 좋다.

솔루션 방법

Tentai Show 퍼즐은 다음과 같은 순서로 풀 수 있습니다.

  1. 점 또는 점의 일부를 포함하는 인접 셀 사이에 벽을 그립니다.이 세포들은 서로 다른 은하에 속해 있을 것입니다.
  2. 회전 대칭에 따라 점 주위에 벽을 그립니다.그리드의 테두리도 벽으로 간주됩니다.
  3. 점으로 '캡처'된 영역에서 셀을 찾습니다.다른 점으로는 도달할 수 없는 셀입니다.이 세포들은 그 점의 은하에만 속할 수 있습니다.

퍼즐이 풀릴 때까지 위의 단계를 반복할 수 있습니다.

더 고급 퍼즐에서는 회전 대칭의 이미지를 고려해야 할 수 있습니다.회전 대칭 셀을 고려할 때 유효한 점이 하나만 있는 셀을 찾습니다.대칭 세포도 은하에 [3]속할 수 있다면 세포는 은하에 속할 수 있다.

역사

퍼즐의 이름인 '텐타이쇼'는 일본어로 해석하면 이중의 의미를 갖는다."텐"은 점을 나타내고 "타이쇼"는 대칭을 나타냅니다.천태(天臺)는 천체를 가리키는 데 쓰인다.'텐타이쇼'는 둘 다 회전대칭과 천문쇼를 [2]의미한다.

계산의 복잡성

NP-완전성

Tentai Show 퍼즐에 해답이 있는지 확인하는 것은 NP-complete로 알려져 있습니다.이것은 임의 부울 회로에 해당하는 퍼즐을 구성하여 프리드먼(2002)에 의해 입증되었으며, 부울 만족도 [4]문제로 인해 NP-완전성을 보여준다.

페르틴, 잠시디, 그리고 코무시에비치(2015)는 모든 은하가 최대 7개의 크기를 가지고 있을 때 퍼즐이 NP-완성임을 증명함으로써 이 결과를 강화했다.이 증명은 퍼즐을 [5]NP-완전이라고 알려진 양의 평면 1-in-3-SAT로 감소시킵니다.

Demaine, Löffler, Schmidt(2021)는 모든 은하가 1×1, 1×3, 또는 3×1 크기의 직사각형으로 제한되더라도 NP-완전성을 증명함으로써 이 점을 더욱 강화했습니다.

그들은 또한 주어진 모양을 정확히 덮는 최소한의 은하 집합을 찾는 것이 [6]NP-완전하다는 것을 보여주었다.

솔루션 알고리즘

Tentai Show 퍼즐은 그리드의 모든 가능한 부분을 살펴보고 유효한 해결책인지 확인함으로써 기하급수적으로 빠르게 해결할 수 있습니다.

페르틴, 잠시디, 코무시에비치(2015)는 (a) 모든 은하의 크기가 최대 2개일 때, (b) 모든 은하의 크기가 정사각형일 때, (c) 모든 은하가 3차적으로 [5]연결되어 있을 때 등 다양한 경우에 대한 퍼즐을 풀 수 있는 다항식 시간 알고리즘을 보여주었다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Puzzle of Nikoli". Nikoli. Retrieved 18 August 2021.
  2. ^ a b "Rules of Tentai Show". Nikoli. Retrieved 18 August 2021.
  3. ^ "Sym-a-Pix techniques". Conceptis puzzles. Retrieved 19 August 2021.
  4. ^ Friedman, Erich. "Spiral Galaxies Puzzles are NP-complete" (PDF). Retrieved 18 August 2021.
  5. ^ a b Fertin, Guillaume; Jamshidi, Shahrad; Komusiewicz, Christian (June 2015). "Towards an Algorithmic Guide to Spiral Galaxies". Theoretical Computer Science. 586: 26–39. doi:10.1016/j.tcs.2015.01.051. Retrieved 18 August 2021.
  6. ^ Demaine, Erik; Löffler, Maarten; Schmidt, Christiane. "Rectangular Spiral Galaxies are Still Hard" (PDF). Retrieved 18 August 2021.


Stub icon

이 퍼즐/로직 게임 관련 기사는 스텁입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.