NP-complete한 펜슬 퍼즐들

노노그램(네모네모로직)같이 주어진 보드에서 연역적으로 푸는 펜슬 퍼즐들이 있다. 많은 펜슬 퍼즐들은 일본의 계간지 니코리에서 등장하는데, 팬층이 두터워서 팬들이 새로운 퍼즐 포맷을 창안해 투고하고 몇 호씩 창작 문제들을 실으면서 인기가 있을지 없을지 검증하기도 함. 2012년 나고야에 갔을 때 서점에서 처음 알게된 이후로 계속 사서 즐기고 있다. 니코리 홈페이지에서 매월 일정 금액 결제해서 온라인으로도 몇 문제씩 정해진 퍼즐 포맷의 새로운 문제들을 출제하고 있다. (무료 샘플 문제 있음) 또한 “니코리계 퍼즐의 역습”이란 블로그에서도 매일 3개씩 많은 종류의 퍼즐들이 나옴. (옛날 옛적 니코리에 등장했다가 사라진 퍼즐들도 많다)

비슷한 종류의 펜슬 퍼즐들은 일본뿐만 아니라 해외에서도 많이 풀리고 있는데, Conceptis puzzle같은 사이트에서도 노노그램이나 일부 니코리계 퍼즐들이 등장한다. 다만 푸는 재미로 치자면 개인적으로는 니코리 계간지, 홈페이지, 혹은 니코리계 퍼즐의 역습 등을 더 좋아하는게 이쪽에서는 주로 어떤 컨셉의 기믹을 쓰는지가 명확히 드러나서 흥미를 유발하는 경우가 많다. 반면 Conceptis 쪽은 좀 machine-generated된 느낌이라 계속 풀다보면 단조롭고 질리게 되기 쉬움.

이런 니코리계 퍼즐들이 NP-complete한지를 묻는 것은 자연스러운데, “펜슬”퍼즐은 아니지만 지뢰찾기에 부울 회로를 implement해서 SAT에서 지뢰찾기로 reduce한 결과가 있었다.[1]

다른 니코리계 퍼즐들도 SAT 같이 이미 알려진 NP-complete 문제를 풀게끔 하는 보드를 건설할 수 있다면 비슷하게 NP-completeness를 보일 수 있게 된다. 일단 아래와 같이 찾아는 봤는데 아직 읽지는 못했고 일단 링크만 모아둠.

트윗 타래를 정리. (2017/10/12)

References

[1] R. Kaye, “Minesweeper is NP-complete” Mathematical Ingelligencer, 22(2), 9-15 (2000). http://simon.bailey.at/random/kaye.minesweeper.pdf

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중