번호 링크

Numberlink
숫자 링크 퍼즐의 간단한 예
Numberlink 퍼즐의 해결책

Numberlink는 그리드 내의 숫자를 연결하는 경로를 찾는 논리 퍼즐의 한 종류입니다.

규칙.

플레이어는 그리드의 모든 일치하는 숫자를 연속된 단일 라인(또는 경로)으로 페어링해야 합니다.선은 서로 분기하거나 교차할 수 없으며 숫자는 각 선의 끝에 있어야 합니다(즉, 중간이 아님).

일부 Numberlink 설계자는 이를 규정하지 않지만, 문제는 고유한[1] 솔루션을 가지고 있고 그리드 내의 모든 셀이 채워진 경우에만 잘 설계된 것으로 간주됩니다.

역사

1897년, 약간 다른 형태의 퍼즐이 브루클린 데일리 이글에 샘 로이드의 [2]칼럼으로 인쇄되었다.번호 연결의 또 다른 초기 인쇄 버전은 헨리 어니스트 두데니의 수학의 오락 (1917)[3]에서 운전자를 위한 퍼즐로 찾을 수 있다.이 퍼즐 타입은 니콜리에 의해 아루코네와 난바린쿠로 일본에서 보급되었다.아루코네와 난바린쿠의 유일한 차이점은 아루코네에서는 두데니의 퍼즐과 같이 단서가 글자 쌍이고, 난바린쿠에서는 단서가 숫자 쌍이라는 것이다.

2006년 현재 Numberlink 퍼즐로 구성된 세 권의 책이 Nikoli에 의해 출판되었다.

와이어 스톰, 플로우 프리, 알파벳 커넥션으로 알려진 이 버전은 iOS, 안드로이드 및 Windows [4][5][6][7][8][9]Phone용 앱으로 출시되었습니다.

계산의 복잡성

계산상의 문제로서 주어진 숫자 링크 퍼즐에 대한 해답을 찾는 [10]것은 NP-완전입니다.「지그재그」패스가 허가되어 있어도, NP 완전성은 유지됩니다.비공식적으로 이는 경로에 "불필요한 굴곡"이 있을 수 있음을 의미합니다(자세한 기술적 [11]설명은 참조).

「 」를 참조해 주세요.

레퍼런스

  1. ^ Thomas Snyder (19 November 2010). "Dr. Sudoku Prescribes: Numberlink Puzzles". Wired. Retrieved November 23, 2010.
  2. ^ Pegg Jr., Ed (2007). "Beyond Sudoku" (PDF). Mathematica Journal. 10 (3): 469–73. Archived from the original (PDF) on 3 March 2016. Retrieved 11 September 2011.
  3. ^ Dudeney, Henry (1917). "Problem 252 – A Puzzle for Motorists". Amusements in mathematics. Thomas Nelson.
  4. ^ "Wire Storm - Fun and Addicting Logic Flow Puzzle Game for bigst4t22,…". Archive.today. 20 June 2013. Archived from the original on 20 June 2013. Retrieved 22 November 2018.
  5. ^ "Flow Free". App Store. Retrieved 22 November 2018.
  6. ^ "Flow Free - Apps on Google Play". Play.google.com. Retrieved 22 November 2018.
  7. ^ "Archived copy". Archived from the original on 2015-03-22. Retrieved 2015-03-17.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  8. ^ "Archived copy". Archived from the original on 2015-04-07. Retrieved 2013-10-29.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  9. ^ "Get Flow Free - Microsoft Store en-GB". Microsoft Store. Retrieved 22 November 2018.
  10. ^ Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), "NP-Completeness and Enumeration of Number Link Puzzle", IEICE Technical Report. Theoretical Foundations of Computing, 109 (465): 1–7
  11. ^ Adcock, Aaron; Demaine, Erik D.; Demaine, Martin L; O’Brien, Michael P.; Villaamil, Fernando S{\'a}nchez; D. Sullivan, Blair (October 23, 2014), "Zig-Zag Numberlink is NP-Complete", Journal of Information Processing, 23 (3): 239–245, arXiv:1410.5845, doi:10.2197/ipsjjip.23.239, S2CID 15735280

외부 링크